How to evaluate an infix expression in just one scan using stacks?

Question

I want to know if there is a way to solve infix expressions in a single pass using 2 stacks? The stacks can be one for operator and the other for operands...

The standard way to solve by shunt-yard algorithm is to convert the infix expression to postfix(reverse polish) and then solve. I don't want to convert the expression first to postfix.

If the expression is like 2*3-(6+5)+8, how to solve?

Answer 1

Quite late, but here is the answer.

Take two stacks:

1. operator stack { for operators and parentheses }.
2. operand stack.

Algorithm

If character exists to be read:

1. If character is operand push on the operand stack, if character is (, push on the operator stack.
2. Else if character is operator
   1. While the top of the operator stack is not of smaller precedence than this character.
   2. Pop operator from operator stack.
   3. Pop two operands (op1 and op2) from operand stack.
   4. Store op1 op op2 on the operand stack back to 2.1.
3. Else if character is ), do the same as 2.2 - 2.4 till you encounter (.

Else (no more character left to read):

• Pop operators untill operator stack is not empty.
• Pop top 2 operands and push op1 op op2 on the operand stack.

return the top value from operand stack.