Is this Shunting Yard's fault or my own?

Question

Given the expression:

 1/2/3/4*5 

It reaches the end of the expression and attempts to multiply out the 4 and 5 first WHICH IS WRONG because it begins to pop off the stack. I'm not necessarily doing RPN but just evaluating on the spot. How can I prevent this?

// Expression was completely read - so we should try and make sense of
// this now
while (operatorStack.size() != 0) {
    ApplyOperation(operatorStack, operandStack);
}

At this point, I begin to pop off operators and operations. Since multiplication and division have the same presence, they start with multiplication.

A trace:

1/2/3/4*5
Applying * to 5 and 4
Result: 20
Applying / to 20 and 3
Result: 3/20
Applying / to 3/20 and 2
Result: 40/3
Applying / to 40/3 and 1
Result: 3/40

Answer 1

There is a point in the shunting yard algorithm at which you compare the precedence of the operator at the top of the stack with the precedence of the operator in the input stream, and decide whether to pop the stack (evaluate the stacked operator, in your case), or push the new operator.

It makes a big difference if the comparison is < or <=. One of those will produce left-associativity, and the other will produce right-associativity. Since you're getting right-associativity and you want left-associativity, I'm guessing (without seeing your code) that you're using the wrong comparison operator.

By the way, your professor is quite correct. There is no need to explicitly produce RPN, and the evaluation algorithm will indeed pop the entire stack when it reaches the end of input. (The RPN algorithm would also do that; the evaluation algorithm is simply a shortcut.)

Answer 2

What operatorStack? The RPN resulting from the shunting-yard algorithm is a list, not a stack. It is processed from left to right, not FIFO,