4.3.3.1 - Reverse Polish and infix expressions (Python)
Learn to convert between infix and Reverse Polish notation, evaluate expressions with a stack, and preserve operand order when implementing the evaluation in Python.
Infix and reverse Polish forms
An expression's notation determines where its operator appears relative to its operands.
Reverse Polish notation
Postfix notation in which an operator follows its operands, so the expression's evaluation order is encoded without brackets.
In infix, an operator sits between operands: a + b. In RPN, the same expression is a b +. Spaces separate tokens here, including multi-digit numbers. Convert each sub-expression first, then place its operator after both converted operands. For (a + b) * c, convert the bracketed sum to a b +, append c, then the multiplication: a b + c *. For a + b * c, multiplication has priority, so the result is a b c * +. These two RPN strings express different grouping.
RPN removes brackets without discarding their meaning: the operator positions carry that meaning. It also avoids needing precedence rules during evaluation. a b - means a minus b; reversing the operands changes subtraction and division. Not every string of operands and operators is valid: with binary operators each operator needs two available values, and a complete expression leaves exactly one final value.
A stack-based interpreter can read tokens left to right and act immediately on each operator. This is useful in systems such as PostScript and stack-based bytecode interpreters. RPN describes expression structure; it does not mean every language's bytecode uses literal textual RPN tokens.
Evaluating with a stack
A stack evaluator pushes each operand and replaces two top operands with their result when it encounters an operator.
For binary operators, pop the right operand first, then the left, and compute left operator right. The top is the rightmost item in this table.
Token in 12 3 2 + / | Stack after processing |
|---|---|
| 12 | 12 |
| 3 | 12, 3 |
| 2 | 12, 3, 2 |
| + | 12, 5 |
| / | 2.4 |
The expression is 12 / (3 + 2). After the plus, the evaluator pops 5 as the right operand and 12 as the left. Computing 5 / 12 would be a logic error even though the program might run.
Observe non-commutative operators
{"code":"tokens = '20 6 2 - /'.split()\nstack = []\nfor token in tokens:\n if token in ('+', '-', '', '/'):\n right = stack.pop()\n left = stack.pop()\n if token == '+':\n value = left + right\n elif token == '-':\n value = left - right\n elif token == '':\n value = left * right\n else:\n value = left / right\n stack.append(value)\n else:\n stack.append(float(token))\n print(token, stack)\nprint('Result:', stack[0])","instructions":"Predict each stack state before Run. Then change the token string to '20 6 2 / -'. Predict and Run again. Explain how moving the division changes the grouped expression and result.","files":[],"original_filename":"main.py","runtime_profile":"python-console-v1","file_mode":"fresh"}
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account