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:
- If character is
operand
push on theoperand stack
, if character is(
, push on theoperator stack
. - Else if character is
operator
- While the top of the
operator stack
is not of smaller precedence than this character. - Pop
operator
fromoperator stack
. - Pop two
operands
(op1
andop2
) fromoperand stack
. - Store
op1 op op2
on theoperand stack
back to 2.1.
- While the top of the
- 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
andpush op1 op op2
on theoperand stack
.
return the top value from operand stack
.