Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Expression conversion and postfix evaluation

Stacks for converting infix ↔ postfix/prefix, operator precedence and associativity, and evaluating postfix expressions correctly.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

  • Mastering stacks for conversion/evaluation strengthens your understanding of how parsers and virtual machines execute programs.

Key ideas

  • Operand: A value or variable upon which an operator acts. Example: 3, x, 42.5.
  • Operator: A symbol that specifies an operation on operands. Example: +, −, ×, ÷, ^.
  • Parentheses: Grouping symbols that override default precedence. Example: (a + b) * c.
  • Notation (fix): The position of operator relative to operands.
    • Infix: Operator between operands: a + b.
    • Postfix (Reverse Polish): Operator after operands: a b +.
    • Prefix (Polish): Operator before operands: + a b.
  • Operator precedence: A ranking determining the order in which different operators are applied in the absence of parentheses.
    • Exact statement (typical arithmetic precedence used in DS textbooks): ^ has higher precedence than *, /; and *, / have higher precedence than +, −.
  • Associativity: A tie-breaking rule deciding order when two adjacent operators have the same precedence.
    • Exact statement: +, −, *, / are left-associative; ^ is right-associative. That is, a ^ b ^ c = a ^ (b ^ c); a − b − c = (a − b) − c.
  • Stack: A Last-In-First-Out (LIFO) abstract data type supporting push and pop, used here to hold operators (and sometimes operands) during conversion and evaluation.

Exact definition (university style):

  • Definition: In an infix expression involving binary operators with known precedence and associativity, the value is obtained by applying, at each step, either (i) the parenthesized subexpression first, or (ii) if no parentheses, the operator with the highest precedence; ties are resolved by associativity.

Stack-based algorithm (infix to postfix) — statement and assumptions:

  • Statement: Given a valid infix expression over binary operators {+, −, *, /, ^} and parentheses, its equivalent postfix expression can be produced in one left-to-right scan using a stack of operators and an output list.
  • Assumptions: Operands are atomic tokens (identifiers or numbers), parentheses are balanced, operator precedence and associativity are known as above, unary operators either not present or preprocessed (see notes below for unary −).

Algorithm (Shunting-yard style) for infix → postfix (commonly required steps):

  1. Initialize empty operator stack S and empty output list O.
  2. For each token t in the infix expression from left to right:
    • If t is an operand, append t to O.
    • If t is an operator op1:
      • While S not empty and top of S is an operator op2 and either (a) precedence(op2) > precedence(op1), or (b) precedence(op2) = precedence(op1) and op1 is left-associative, pop op2 from S and append to O.
      • Push op1 onto S.
    • If t is '(', push it onto S.
    • If t is ')', pop from S and append to O until '(' is at top of S; pop and discard the '('.
  3. After the input ends, pop all remaining operators from S to O.
  • The resulting sequence O is the postfix expression.

Correctness sketch (what to write):

  • Precedence and associativity are enforced by the while condition when pushing an operator, so higher-precedence and left-tied operators are output before later lower-precedence or same-precedence (left-assoc) operators. Parentheses delay output until the matching ')' is seen, guaranteeing grouped subexpressions become contiguous in O.

Algorithm for postfix evaluation using a stack:

  1. Initialize empty operand stack V.
  2. Scan postfix tokens from left to right.
    • If token is an operand, push its value onto V.
    • If token is a binary operator op, pop the top two values b then a from V, compute a op b, and push the result back onto V.
  3. After the scan, the single value on V is the result.
  • Assumptions: Expression is well-formed; no division by zero; operators defined as usual; exponent ^ is right-associative in infix but in postfix evaluation no associativity ambiguity exists.

Infix to prefix conversion (two standard methods):

  • Method A (reverse-transform-reverse):
    1. Reverse the infix expression token sequence.
    2. Swap '(' with ')' everywhere.
    3. Convert the resulting expression to postfix using the infix→postfix algorithm, keeping the same precedences but REVERSING associativity when comparing equal-precedence operators in the while-condition (treat +, −, *, / as right-associative and ^ as left-associative for this step).
    4. Reverse the resulting postfix to get the prefix.
  • Method B (direct using stacks of operators and operands): Maintain two stacks (operators and operand-strings) and reduce when precedence dictates. Universities usually accept either; Method A is easier to remember and derive.

Handling unary minus (exam note):

  • If unary minus appears (e.g., −a or −(b+c)), treat it as a distinct operator u− with higher precedence than ^ and right-associative during conversion, or preprocess by inserting 0: −a → 0 − a; −(b+c) → 0 − (b+c). Clearly state the assumption in your answer/code.

What to draw in a diagram (trace table):

  • For infix→postfix: Draw a table with columns labeled: Step, Input token, Operator stack (top on right), Output list. Fill each row as you process tokens, showing pushes, pops, and outputs. Mark when '(' is pushed and when operators are popped on ')'.
  • For postfix evaluation: Draw columns: Step, Token, Operand stack (top on right), Action (push value / compute a op b = result).

Complexity:

  • For both conversion and evaluation, each token is pushed to and popped from a stack at most once. Time: O(n). Space: O(n) for the stack and output.

Formulas

  • Operator precedence order (highest to lowest): ^, then * and /, then + and -.
  • Associativity: ^ is right-associative; *, /, +, - are left-associative.
  • Postfix evaluation step: a b op → (a op b) where a is the older stack value and b is the newer (popped last) value.
  • Infix→Postfix pop condition for operator op1: while prec(op2) > prec(op1) or (prec(op2) = prec(op1) and op1 is left-associative) → pop op2.
  • Parentheses rule: push (; on ), pop until ( is found and discard (.

Worked examples

Example 1 — Model answer: Convert the infix expression 3 + 4 * 2 / ( 1 − 5 ) ^ 2 ^ 3 to postfix and prefix. Show the stack trace.

  • Precedence: ^ > * = / > + = − ; Associativity: ^ right, others left.
  • Trace (what to write in table):
    1. Read 3 → output: 3
      • → push +
    2. 4 → output: 3 4
      • → stack top + has lower precedence → push *
    3. 2 → output: 3 4 2
    4. / → stack top * has equal precedence and / is left-assoc → pop * to output; push / Output now: 3 4 2 *
    5. ( → push (
    6. 1 → output: 3 4 2 * 1
    7. − → push − (top is '(' so no popping)
    8. 5 → output: 3 4 2 * 1 5
    9. ) → pop until '(' → pop − to output, discard '(' Output now: 3 4 2 * 1 5 −
    10. ^ → push ^ (top is + or /? Actually top is /; ^ has higher precedence, so push)
    11. 2 → output: 3 4 2 * 1 5 − 2
    12. ^ → top is ^ with equal precedence, but ^ is right-assoc → do NOT pop; push ^
    13. 3 → output: 3 4 2 * 1 5 − 2 3
    14. End → pop remaining operators in order: ^, ^, /, +
  • Postfix result: 3 4 2 * 1 5 − 2 3 ^ ^ / +
  • Prefix (reverse-swap-reverse method):
    1. Reverse tokens: 3 ^ 2 ^ ) 5 − 1 ( / 2 * 4 + 3
    2. Swap parentheses: 3 ^ 2 ^ ( 5 − 1 ) / 2 * 4 + 3
    3. Convert to postfix (with reversed associativity as noted) → gives: 3 2 ^ 5 1 − ^ 2 4 * / 3 +
    4. Reverse that sequence for prefix: + 3 / * 4 2 ^ − 1 5 ^ 2 3 Using either the reverse-swap-reverse method (with reversed associativity in step 3) or the direct two-stack method yields the same prefix: + 3 / * 4 2 ^ − 1 5 ^ 2 3.

Example 2 — Python program: Infix to Postfix converter (supports +, −, *, /, ^, parentheses; numbers and identifiers)

# infix_to_postfix.py
# Assumption: tokens may be numbers (integers/decimals), identifiers (letters, digits, underscores),
# operators + - * / ^, and parentheses (). Unary minus is NOT handled specially; write it as 0 - x if needed.

def precedence(op):
    return {"^": 3, "*": 2, "/": 2, "+": 1, "-": 1}.get(op, 0)

def is_left_assoc(op):
    return op in {"*", "/", "+", "-"}  # ^ is right-associative

def tokenize(expr):
    tokens = []
    i = 0
    while i < len(expr):
        c = expr[i]
        if c.isspace():
            i += 1
        elif c.isdigit() or c == '.':
            j = i
            dot = (c == '.')
            i += 1
            while i < len(expr) and (expr[i].isdigit() or (expr[i] == '.' and not dot)):
                dot = dot or expr[i] == '.'
                i += 1
            tokens.append(expr[j:i])
        elif c.isalpha() or c == '_':
            j = i
            i += 1
            while i < len(expr) and (expr[i].isalnum() or expr[i] == '_'):
                i += 1
            tokens.append(expr[j:i])
        elif c in "+-*/^()":
            tokens.append(c)
            i += 1
        else:
            raise ValueError(f"Unexpected character: {c}")
    return tokens

def infix_to_postfix(expr):
    tokens = tokenize(expr)
    out = []
    stack = []
    for t in tokens:
        if t.isidentifier() or t.replace('.', '', 1).isdigit():
            out.append(t)
        elif t in "+-*/^":
            while stack and stack[-1] in "+-*/^" and (
                precedence(stack[-1]) > precedence(t) or (
                    precedence(stack[-1]) == precedence(t) and is_left_assoc(t)
                )
            ):
                out.append(stack.pop())
            stack.append(t)
        elif t == '(':
            stack.append(t)
        elif t == ')':
            while stack and stack[-1] != '(':
                out.append(stack.pop())
            if not stack:
                raise ValueError("Mismatched parentheses")
            stack.pop()  # discard '('
        else:
            raise ValueError(f"Bad token: {t}")
    while stack:
        if stack[-1] in '()':
            raise ValueError("Mismatched parentheses")
        out.append(stack.pop())
    return ' '.join(out)

if __name__ == "__main__":
    expr = input().strip()
    print(infix_to_postfix(expr))

Sample input

3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3

Exact output

3 4 2 * 1 5 - 2 3 ^ ^ / +

Example 3 — Python program: Postfix evaluator (supports +, −, *, /, ^; space-separated tokens)

# evaluate_postfix.py
# Assumption: tokens are space-separated; numbers are integers/decimals; operators + - * / ^ are binary.

def apply_op(a, b, op):
    if op == '+':
        return a + b
    if op == '-':
        return a - b
    if op == '*':
        return a * b
    if op == '/':
        return a / b
    if op == '^':
        return a ** b  # exponentiation
    raise ValueError(f"Unknown operator: {op}")

def evaluate_postfix(postfix):
    stack = []
    for tok in postfix.split():
        if tok.replace('.', '', 1).lstrip('+-').isdigit():
            stack.append(float(tok))
        elif tok in "+-*/^":
            if len(stack) < 2:
                raise ValueError("Insufficient operands")
            b = stack.pop()
            a = stack.pop()
            stack.append(apply_op(a, b, tok))
        else:
            raise ValueError(f"Unexpected token: {tok}")
    if len(stack) != 1:
        raise ValueError("Malformed postfix expression")
    return stack[0]

if __name__ == "__main__":
    expr = input().strip()
    print(evaluate_postfix(expr))

Sample input

3 4 2 * 1 5 - 2 3 ^ ^ / +

Exact output

3.0001220703125

Common mistakes

  • Forgetting to pop operators on encountering ')' or forgetting to discard the '(' after popping.
  • Reversing operand order during postfix evaluation: computing b op a instead of a op b.
  • Ignoring unary minus; writing −x directly without handling, which breaks conversion/evaluation. State assumption or preprocess (0 − x).
  • Losing multi-digit numbers or identifiers due to character-by-character output; always tokenize properly.
  • Not checking for mismatched parentheses or insufficient operands, leading to runtime errors.

For your exam

  • Short notes: Why stacks are used in parsing; advantages of postfix; complexity analysis O(n) time and space.
  • Derivations/algorithms: Write the step-by-step infix→postfix algorithm with the exact while condition that encodes precedence and associativity; write the postfix evaluation algorithm with clear stack actions.
  • Conversions: Convert given infix to postfix/prefix (show full stack trace table with Input token, Operator stack, Output list). If asked for prefix, you can use reverse-swap-reverse and show intermediate forms.
  • Programs: Python/C/Java program to convert infix to postfix and/or to evaluate postfix; must handle multi-digit numbers and parentheses; include operator precedence and associativity. Show sample I/O.
  • Diagrams: Draw annotated stack evolution for both conversion and evaluation. Label top of stack and each action (push/pop/output/compute).
  • Full-marks answers: State assumptions (operator set, associativity, unary minus handling), present algorithm or code clearly, and verify the final expression or value.

Quick check

  1. What is the associativity of the exponent operator ^ in standard data-structures treatment, and how does it affect infix→postfix conversion?
  2. Convert the infix a + b * c to postfix.
  3. Evaluate the postfix expression 5 1 2 + 4 * + 3 −.

Answers: (1) ^ is right-associative; when reading a ^ and top is ^, do not pop the top ^, so b c ^ comes before combining with a. (2) a b c * +. (3) 14 (since 1 2 + = 3; 3 4 * = 12; 5 12 + = 17; 17 3 − = 14).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?