062. Evaluate Postfix Notation

Foundation · Download this solution · All solutions and shared helpers

Problem

Evaluate a valid nonempty, space-separated postfix expression of signed integer literals and binary +, -, * or /. Division truncates toward zero, and divisors are nonzero. Return the integer result. The expression is guaranteed to reduce to one value.

Examples

Example 1

evaluate_postfix("2 3 4 * +")
=> 14

Multiplication combines three and four before addition.

Example 2

evaluate_postfix("-7 3 /")
=> -2

Truncation moves toward zero, not negative infinity.

Example 3

evaluate_postfix("9 4 -")
=> 5

The second pop is the left operand.

Reveal the worked solution and reasoning

Why this mechanism works

A postfix operator arrives after both operand expressions have been evaluated. Their results are the two most recent unresolved values. Pop the right operand first and the left operand second. For exact integer truncation, divide absolute magnitudes and restore the sign instead of converting through floating point.

State and boundaries

stack contains values of completed subexpressions not yet consumed by an operator.

Protocol

Push integer literals.
On an operator pop right then left.
Apply the operator in that order.
Push the combined result.
Return the sole remaining value.

Visualization

2 3 4 * +
[2] -> [2,3] -> [2,3,4]
* -> [2,12]
 -> [14]

Python implementation

def evaluate_postfix(expression):
    stack = []
    for token in expression.split():
        if token not in ('+', '-', '*', '/'):
            stack.append(int(token))
            continue
        right = stack.pop()
        left = stack.pop()
        if token == '+':
            value = left + right
        elif token == '-':
            value = left - right
        elif token == '*':
            value = left * right
        else:
            value = abs(left) // abs(right)
            if (left < 0) != (right < 0):
                value = -value
        stack.append(value)
    return stack[0]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

evaluate_postfix("2 3 4 * +")

L2 evaluate_postfix: stack = []
expression='2 3 4 * +'; stack=[]

L3 evaluate_postfix: for token in expression.split():
expression='2 3 4 * +'; stack=[]; token='2'

L5 evaluate_postfix: stack.append(int(token))
expression='2 3 4 * +'; stack=[2]; token='2'

L3 evaluate_postfix: for token in expression.split():
expression='2 3 4 * +'; stack=[2]; token='3'

L5 evaluate_postfix: stack.append(int(token))
expression='2 3 4 * +'; stack=[2, 3]; token='3'

L3 evaluate_postfix: for token in expression.split():
expression='2 3 4 * +'; stack=[2, 3]; token='4'

L5 evaluate_postfix: stack.append(int(token))
expression='2 3 4 * +'; stack=[2, 3, 4]; token='4'

L3 evaluate_postfix: for token in expression.split():
expression='2 3 4 * +'; stack=[2, 3, 4]; token='*'

... 5 intermediate state changes omitted ...

L7 evaluate_postfix: right = stack.pop()
expression='2 3 4 * +'; stack=[2]; token='+'; right=12; left=3; value=12

L8 evaluate_postfix: left = stack.pop()
expression='2 3 4 * +'; stack=[]; token='+'; right=12; left=2; value=12

L10 evaluate_postfix: value = left + right
expression='2 3 4 * +'; stack=[]; token='+'; right=12; left=2; value=14

L19 evaluate_postfix: stack.append(value)
expression='2 3 4 * +'; stack=[14]; token='+'; right=12; left=2; value=14

Result: 14. Multiplication combines three and four before addition.

evaluate_postfix("-7 3 /")

L2 evaluate_postfix: stack = []
expression='-7 3 /'; stack=[]

L3 evaluate_postfix: for token in expression.split():
expression='-7 3 /'; stack=[]; token='-7'

L5 evaluate_postfix: stack.append(int(token))
expression='-7 3 /'; stack=[-7]; token='-7'

L3 evaluate_postfix: for token in expression.split():
expression='-7 3 /'; stack=[-7]; token='3'

L5 evaluate_postfix: stack.append(int(token))
expression='-7 3 /'; stack=[-7, 3]; token='3'

L3 evaluate_postfix: for token in expression.split():
expression='-7 3 /'; stack=[-7, 3]; token='/'

L7 evaluate_postfix: right = stack.pop()
expression='-7 3 /'; stack=[-7]; token='/'; right=3

L8 evaluate_postfix: left = stack.pop()
expression='-7 3 /'; stack=[]; token='/'; right=3; left=-7

L16 evaluate_postfix: value = abs(left) // abs(right)
expression='-7 3 /'; stack=[]; token='/'; right=3; left=-7; value=2

L18 evaluate_postfix: value = -value
expression='-7 3 /'; stack=[]; token='/'; right=3; left=-7; value=-2

L19 evaluate_postfix: stack.append(value)
expression='-7 3 /'; stack=[-2]; token='/'; right=3; left=-7; value=-2

Result: -2. Truncation moves toward zero, not negative infinity.

Why the solution is correct

Each literal is a complete subexpression. An operator replaces its two operand results by their correct combined value, preserving the stack's interpretation. Valid postfix syntax ensures the process finishes with the value of the full expression.

Time and space

O(t) arithmetic operations and O(t) stack space for t tokens; big-integer operation costs depend on operand size.

Common mistakes

Reversing pops breaks subtraction and division. Python // floors negative results rather than truncating toward zero.

Reasoning card

State: stack contains values of completed subexpressions not yet consumed by an operator.

Invariant: Stack holds evaluated subexpressions awaiting use.

Decision to rehearse: Numbers push; operators pop right then left; final stack must contain one value.

Finish: Return the sole remaining value

Transfer exercise

Build an expression tree instead of immediately evaluating, using the same operand-stack protocol.