A stack machine evaluates instructions by storing values in a last-in-first-out stack. In Reverse Polish Notation, numbers are pushed onto the stack and each operator consumes the previous two values, then places its result back on the stack. section 3.2
This model makes arithmetic evaluation direct:
- Process tokens strictly from left to right, without infix precedence rules. section 3.2
- Represent nested arithmetic by placing each operation in the order it should execute. section 3.2
- Parse a calculator more simply because operators always act on the two preceding stack values. section 3.2
RPN evaluation
The infix expression “(3 + 4) * 12” becomes “3 4 + 12 *” and evaluates to 84: push 3 and 4, add them, push 12, then multiply. section 3.2
Figure 3.2 RPN stack used to calculate 3 4 + 12 *
A stack diagram traces the intermediate values while evaluating a nested RPN expression. section 3.2
