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.