Evaluate Postfix Expression Using Stack in DSA Python

Mental Model

Use a stack to keep numbers until an operator appears, then combine the last two numbers using that operator.

Analogy: Imagine a stack of plates where you add plates with numbers. When you see a math sign, you take the top two plates, do the math, and put the result back on top.

Stack (top at right): []
Postfix expression: 2 3 + 4 *
Numbers push in order, operators combine top two numbers.

Dry Run Walkthrough

Input: Postfix expression: 2 3 + 4 *

Goal: Calculate the final result of the postfix expression using a stack

Step 1: Push 2 onto stack

Stack: [2]

Why: Numbers are pushed to stack to wait for operators

Step 2: Push 3 onto stack

Stack: [2, 3]

Why: Keep numbers until operator appears

Step 3: Operator '+' found: pop 3 and 2, add them (2+3=5), push 5

Stack: [5]

Why: Apply operator to last two numbers and push result

Step 4: Push 4 onto stack

Stack: [5, 4]

Why: Push next number to stack

Step 5: Operator '*' found: pop 4 and 5, multiply (5*4=20), push 20

Stack: [20]

Why: Apply operator to last two numbers and push result

Result:

Stack: [20]
Final result: 20

Annotated Code

DSA Python

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        return None

    def is_empty(self):
        return len(self.items) == 0


def evaluate_postfix(expression):
    stack = Stack()
    operators = {'+', '-', '*', '/'}

    for token in expression.split():
        if token not in operators:
            stack.push(int(token))  # push number
        else:
            right = stack.pop()  # pop right operand
            left = stack.pop()   # pop left operand
            if token == '+':
                stack.push(left + right)  # add and push result
            elif token == '-':
                stack.push(left - right)  # subtract and push result
            elif token == '*':
                stack.push(left * right)  # multiply and push result
            elif token == '/':
                stack.push(int(left / right))  # divide and push result (integer division)

    return stack.pop()  # final result


# Driver code
expr = "2 3 + 4 *"
result = evaluate_postfix(expr)
print(result)

stack.push(int(token)) # push number

push number tokens onto stack to wait for operators

right = stack.pop() # pop right operand

pop right operand for operation

left = stack.pop() # pop left operand

pop left operand for operation

stack.push(left + right) # add and push result

apply operator and push result back to stack

stack.push(left - right) # subtract and push result

apply operator and push result back to stack

stack.push(left * right) # multiply and push result

apply operator and push result back to stack

stack.push(int(left / right)) # divide and push result (integer division)

apply operator and push result back to stack

return stack.pop() # final result

pop final result from stack after processing all tokens

Output

20

Complexity Analysis

Time: O(n) because we process each token in the expression once

Space: O(n) because in worst case all tokens are numbers pushed to stack

vs Alternative: Compared to evaluating infix expressions which require operator precedence handling, postfix evaluation is simpler and faster using a stack

Edge Cases

Empty expression

Returns None or error because no tokens to process

DSA Python

return stack.pop()  # final result

Single number expression like '5'

Returns the number itself as result

DSA Python

stack.push(int(token))  # push number

Division by zero in expression

Raises runtime error (ZeroDivisionError)

DSA Python

stack.push(int(left / right))  # divide and push result (integer division)

When to Use This Pattern

When you see an expression without parentheses and operators after operands, use the Evaluate Postfix Expression pattern with a stack to compute the result easily.

Common Mistakes

Mistake: Popping operands in wrong order causing wrong results
Fix: Always pop right operand first, then left operand before applying operator

Mistake: Trying to evaluate infix expression directly without converting
Fix: Use postfix expression or convert infix to postfix before evaluation

Summary

It calculates the value of a postfix expression using a stack.

Use it when you need to evaluate postfix expressions efficiently without worrying about operator precedence.

The key insight is to push numbers and apply operators immediately to the last two numbers on the stack.

Practice

1. What does evaluating a postfix expression using a stack mainly involve?

easy

A. Using recursion to evaluate the expression

B. Converting the postfix expression to infix before evaluation

C. Pushing operands onto the stack and popping two operands for each operator to apply the operation

D. Ignoring operators and only summing operands

Solution

1. Step 1: Understand postfix evaluation process

   In postfix evaluation, operands are pushed onto a stack. When an operator is encountered, two operands are popped, the operation is applied, and the result is pushed back.

2. Step 2: Identify correct method

   Pushing operands onto the stack and popping two operands for each operator to apply the operation correctly describes this stack-based process. Other options describe unrelated or incorrect methods.

3. Final Answer:

   Pushing operands onto the stack and popping two operands for each operator to apply the operation -> Option C

4. Quick Check:

   Postfix evaluation uses stack push/pop [OK]

Hint: Remember: push operands, pop two for operator, push result [OK]

Common Mistakes:

• Thinking postfix needs conversion to infix first
• Trying to evaluate from left to right without stack
• Ignoring the order of operands when popping

2. Which of the following Python code snippets correctly pushes operands and evaluates a postfix expression using a stack?

easy

A. stack.append(int(char)) when char is digit; pop two, apply operator, push result

B. stack.push(char) for operands; pop one operand for operator

C. Use stack.pop() to push operands; stack.append() to pop

D. Directly evaluate expression without stack

Solution

1. Step 1: Check correct stack operations

   In Python, list's append() adds elements (push), pop() removes last element (pop). For postfix, push operands as integers, pop two for operator.

2. Step 2: Match with options

   stack.append(int(char)) when char is digit; pop two, apply operator, push result correctly uses stack.append(int(char)) for digits and pops two operands for operators. Others misuse push/pop or skip stack.

3. Final Answer:

   stack.append(int(char)) when char is digit; pop two, apply operator, push result -> Option A

4. Quick Check:

   Use append to push, pop to remove [OK]

Hint: Use append() to push and pop() to remove from stack [OK]

Common Mistakes:

• Using stack.push() which is not a Python list method
• Popping only one operand for operator
• Not converting char to int before pushing

3. What is the output of the following Python code that evaluates the postfix expression '231*+9-'?

def evaluate_postfix(expr):
    stack = []
    for char in expr:
        if char.isdigit():
            stack.append(int(char))
        else:
            b = stack.pop()
            a = stack.pop()
            if char == '+':
                stack.append(a + b)
            elif char == '-':
                stack.append(a - b)
            elif char == '*':
                stack.append(a * b)
            elif char == '/':
                stack.append(a // b)
    return stack.pop()

print(evaluate_postfix('231*+9-'))

medium

A. -4

B. -2

C. -3

D. 4

Solution

1. Step 1: Evaluate expression step-by-step

   Expression: '2 3 1 * + 9 -' - Push 2, 3, 1 - '*' operator: pop 1 and 3, multiply 3*1=3, push 3 - '+' operator: pop 3 and 2, add 2+3=5, push 5 - Push 9 - '-' operator: pop 9 and 5, subtract 5-9=-4, push -4

2. Step 2: Final result

   Pop final value from stack: -4

3. Final Answer:

   -4 -> Option A

4. Quick Check:

   Postfix '231*+9-' = -4 [OK]

Hint: Evaluate stepwise: push digits, apply operators on last two [OK]

Common Mistakes:

• Mixing operand order when popping (a, b vs b, a)
• Using float division instead of integer division
• Misreading the expression order

4. The following code is intended to evaluate a postfix expression but throws an error. What is the error and how to fix it?

def eval_postfix(expr):
    stack = []
    for char in expr:
        if char.isdigit():
            stack.append(char)
        else:
            a = stack.pop()
            b = stack.pop()
            if char == '+':
                stack.append(a + b)
            elif char == '-':
                stack.append(a - b)
    return stack.pop()

print(eval_postfix('23+'))

medium

A. SyntaxError due to missing colon; fix by adding colon after if

B. TypeError due to adding strings; fix by converting char to int before pushing

C. IndexError due to popping from empty stack; fix by checking stack size

D. No error; output is '5'

Solution

1. Step 1: Identify error cause

   The code pushes characters as strings onto stack. When popping, it tries to add strings, causing TypeError.

2. Step 2: Fix by converting to int

   Convert char to int before pushing: stack.append(int(char)) to allow arithmetic operations.

3. Final Answer:

   TypeError due to adding strings; fix by converting char to int before pushing -> Option B

4. Quick Check:

   Push integers, not strings, to avoid TypeError [OK]

Hint: Always convert digit chars to int before pushing [OK]

Common Mistakes:

• Pushing strings instead of integers
• Swapping operand order when popping
• Ignoring operator cases other than '+' and '-'

5. Given the postfix expression '56+82/-', what is the result after evaluating it using a stack? Show the step-by-step evaluation.

hard

A. 5

B. 1

C. 9

D. 7

Solution

1. Step 1: Evaluate postfix expression stepwise

   Expression: '5 6 + 8 2 / -' - Push 5, 6 - '+' operator: pop 6 and 5, add 5+6=11, push 11 - Push 8, 2 - '/' operator: pop 2 and 8, integer divide 8//2=4, push 4 - '-' operator: pop 4 and 11, subtract 11-4=7, push 7

2. Step 2: Final result

   Pop final value from stack: 7

3. Final Answer:

   7 -> Option D

4. Quick Check:

   Postfix '56+82/-' = 7 [OK]

Hint: Process operators on last two stack values in order [OK]

Common Mistakes:

• Dividing operands in wrong order (2/8 instead of 8/2)
• Using float division instead of integer division
• Mixing operand order when subtracting