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?
a. get the next token in the infix string.
b. if the next is an operand, place it on the operand stack.
c. if the next token is an operator
Quite late, but here is the answer.
Take two stacks:
operator stack
{ for operators and parentheses }.operand stack
.Algorithm
If character exists to be read:
operand
push on theoperand stack
, if character is(
, push on theoperator stack
.operator
operator stack
is not of smaller precedence than this character.operator
fromoperator stack
.operands
(op1
andop2
) fromoperand stack
.op1 op op2
on theoperand stack
back to 2.1.)
, do the same as 2.2 - 2.4 till you encounter(
.Else (no more character left to read):
operator stack
is not empty.operands
andpush op1 op op2
on theoperand stack
.return the top value from
operand stack
.The method given in the link is really good.
Let me quote the source:
I hope this helps!
Below is my attempt at infix expression evaluation in java. Please let me know if you find any bugs :)