Evaluate Postfix Expression Using Stack in DSA Python - Execution Trace

Concept Flow - Evaluate Postfix Expression Using Stack

Start with empty stack

↓

Read next token from postfix

↓

Is token a number?

Yes→Push number onto stack

No↓

Pop two numbers from stack

↓

Apply operator to popped numbers

↓

Push result back onto stack

↓

More tokens?

Yes→Read next token

No↓

Final result is top of stack

↓

End

We read each token from the postfix expression. If it's a number, push it on the stack. If it's an operator, pop two numbers, apply the operator, and push the result back. Repeat until done.

Execution Sample

DSA Python

expression = "231*+9-"
stack = []
for token in expression:
    if token.isdigit():
        stack.append(int(token))
    else:
        b = stack.pop()
        a = stack.pop()
        if token == '+': stack.append(a + b)
        elif token == '-': stack.append(a - b)
        elif token == '*': stack.append(a * b)
        elif token == '/': stack.append(a // b)
print(stack[-1])

This code evaluates the postfix expression "231*+9-" step-by-step using a stack.

Execution Table

Step	Operation	Token	Stack Before	Action	Stack After	Visual State
1	Read token	2	[]	Push 2	[2]	2
2	Read token	3	[2]	Push 3	[2, 3]	2 -> 3
3	Read token	1	[2, 3]	Push 1	[2, 3, 1]	2 -> 3 -> 1
4	Read token	*	[2, 3, 1]	Pop 1 and 3, multiply 3*1=3, push 3	[2, 3]	2 -> 3
5	Read token	+	[2, 3]	Pop 3 and 2, add 2+3=5, push 5	[5]	5
6	Read token	9	[5]	Push 9	[5, 9]	5 -> 9
7	Read token	-	[5, 9]	Pop 9 and 5, subtract 5-9=-4, push -4	[-4]	-4
8	End		[-4]	Final result is top of stack	[-4]	-4

💡 All tokens processed; final result is -4 on top of stack

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	Final
stack	[]	[2]	[2, 3]	[2, 3, 1]	[2, 3]	[5]	[5, 9]	[-4]	[-4]
token		2	3	1	*	+	9	-

Key Moments - 3 Insights

Why do we pop two numbers from the stack when we see an operator?

Because postfix operators apply to the two most recent numbers. The execution_table rows 4, 5, and 7 show popping two numbers before applying the operator.

Why do we push the result back onto the stack after applying the operator?

The result becomes a new operand for future operations. See execution_table rows 4, 5, and 7 where after calculation, the result is pushed back.

What happens if the expression has only numbers and no operators?

All numbers get pushed onto the stack, and the final result is the last number pushed. The execution_table rows 1-3 show pushing numbers without popping.

Visual Quiz - 3 Questions

Look at the execution_table, what is the stack after step 5?

A [2, 3]

B [5]

C [5, 9]

D [-4]

💡 Hint

Check the 'Stack After' column in row 5 of execution_table.

At which step does the operator '*' get applied?

A Step 3

B Step 5

C Step 4

D Step 6

💡 Hint

Look at the 'Token' and 'Operation' columns in execution_table to find when '*' is processed.

If the token '9' was replaced by '4', what would be the final stack value after step 7?

A [1]

B [5]

C [-4]

D [4]

💡 Hint

Refer to variable_tracker and execution_table for step 7 calculation; replace 9 with 4 and recalculate 5 - 4.

Concept Snapshot

Evaluate Postfix Expression Using Stack:
- Read tokens left to right
- Push numbers onto stack
- On operator, pop two numbers, apply operator, push result
- Final stack top is result
- Works because postfix order ensures operands before operators

Full Transcript

To evaluate a postfix expression, we use a stack. We read each token from left to right. If the token is a number, we push it onto the stack. If it is an operator, we pop the top two numbers from the stack, apply the operator, and push the result back. We repeat this until all tokens are processed. The final result is the single number left on the stack. For example, for the expression '231*+9-', we push 2, 3, and 1, then multiply 3 and 1, push the result, add 2 and the result, push 9, then subtract 9 from the previous result. The final answer is -4.

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