Evaluate Postfix Expression Using Stack in DSA Go - Execution Trace

Concept Flow - Evaluate Postfix Expression Using Stack

Read next token

↓

Is token operand?

Yes→Push operand on stack

No↓

Pop two operands from stack

↓

Apply operator to operands

↓

Push result back on stack

↓

More tokens?

Yes→Repeat

No↓

Pop final result from stack

↓

Return result

The flow reads each token from the postfix expression, pushes operands on the stack, applies operators by popping two operands, and pushes the result back until all tokens are processed.

Execution Sample

DSA Go

tokens := []string{"2", "3", "1", "*", "+", "9", "-"}
stack := []int{}
for _, token := range tokens {
  // process token
}
result := stack[len(stack)-1]

This code evaluates the postfix expression 2 3 1 * + 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 -> null
2	Read token	3	[2]	Push 3	[2, 3]	2 -> 3 -> null
3	Read token	1	[2, 3]	Push 1	[2, 3, 1]	2 -> 3 -> 1 -> null
4	Read token	*	[2, 3, 1]	Pop 1 and 3, multiply 3*1=3, push 3	[2, 3]	2 -> 3 -> null
5	Read token	+	[2, 3]	Pop 3 and 2, add 2+3=5, push 5	[5]	5 -> null
6	Read token	9	[5]	Push 9	[5, 9]	5 -> 9 -> null
7	Read token	-	[5, 9]	Pop 9 and 5, subtract 5-9=-4, push -4	[-4]	-4 -> null
8	End		[-4]	Pop final result -4	[]	empty stack

💡 All tokens processed; final result popped from 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]	[]
token	""	"2"	"3"	"1"	"*"	"+"	"9"	"-"	""

Key Moments - 3 Insights

Why do we pop two operands when we see an operator?

Because postfix operators apply to the two most recent operands on the stack, as shown in steps 4, 5, and 7 in the execution_table where two values are popped before applying the operator.

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

The result becomes a new operand for future operations, so it must be pushed back as in steps 4, 5, and 7, maintaining the correct stack state for the next tokens.

What happens if the stack is empty when trying to pop operands?

This means the postfix expression is invalid or incomplete. The execution_table assumes a valid expression, so popping always succeeds before applying operators.

Visual Quiz - 3 Questions

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

A [2, 3, 1]

B [2, 3]

C [5]

D [2]

💡 Hint

Check the 'Stack After' column at step 5 in the execution_table.

At which step does the stack first contain only one element?

A Step 3

B Step 5

C Step 6

D Step 7

💡 Hint

Look for the first time the 'Stack After' column shows a single element.

If the token '*' at step 4 was replaced by '+', what would be the new stack after step 4?

A [2, 4]

B [2, 3]

C [2, 6]

D [2, 5]

💡 Hint

Adding 3 and 1 gives 4, but the original operands are 3 and 1; check the operation carefully.

Concept Snapshot

Evaluate Postfix Expression Using Stack:
- Read tokens left to right
- Push operands on stack
- On operator, pop two operands
- Apply operator and push result
- Final stack top is result
- Works only with valid postfix expressions

Full Transcript

To evaluate a postfix expression, we read each token from left to right. If the token is a number, we push it onto a stack. If the token is an operator, we pop the two most recent numbers from the stack, apply the operator, and push the result back. We repeat this until all tokens are processed. The last number left on the stack is the final result. This method uses a stack to keep track of operands and intermediate results.

Practice

1. What is the main purpose of using a stack to evaluate a postfix expression?

easy

A. To count the number of operators

B. To store operands and apply operators in correct order

C. To convert postfix to infix expression

D. To reverse the postfix expression

Solution

1. Step 1: Understand postfix evaluation process

   In postfix, operands come before operators. A stack helps store operands until an operator appears.

2. Step 2: Role of stack in evaluation

   When an operator is found, the top two operands are popped from the stack, the operation is performed, and the result is pushed back.

3. Final Answer:

   To store operands and apply operators in correct order -> Option B

4. Quick Check:

   Stack stores operands for operator application [OK]

Hint: Stack holds operands until operators appear [OK]

Common Mistakes:

• Thinking stack reverses the expression
• Confusing postfix with infix conversion
• Ignoring the order of operations

2. Which of the following Go code snippets correctly pushes an integer onto a stack represented by a slice?

easy

A. stack.add(value)

B. stack.push(value)

C. stack.insert(value)

D. stack = append(stack, value)

Solution

1. Step 1: Understand Go slice operations

   In Go, slices use append() to add elements at the end.

2. Step 2: Identify correct push operation

   stack = append(stack, value) correctly adds value to the stack slice.

3. Final Answer:

   stack = append(stack, value) -> Option D

4. Quick Check:

   Use append() to push in Go slices [OK]

Hint: Use append() to add elements to slice stack [OK]

Common Mistakes:

• Using non-existent push() method on slice
• Confusing slice with other data structures
• Trying to use insert() which is not a Go slice method

3. What is the output of the following Go code that evaluates the postfix expression "23+5*"?

func evaluatePostfix(expr string) int {
    stack := []int{}
    for _, ch := range expr {
        if ch >= '0' && ch <= '9' {
            stack = append(stack, int(ch-'0'))
        } else {
            b := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            a := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            switch ch {
            case '+':
                stack = append(stack, a+b)
            case '*':
                stack = append(stack, a*b)
            }
        }
    }
    return stack[0]
}

fmt.Println(evaluatePostfix("23+5*"))

medium

A. 25

B. 15

C. 10

D. Error

Solution

1. Step 1: Evaluate "23+" part

   Push 2, push 3, then '+' pops 3 and 2, adds to 5, pushes 5.

2. Step 2: Evaluate remaining "5*" part

   Push 5, then '*' pops 5 and 5, multiplies to 25, pushes 25.

3. Final Answer:

   25 -> Option A

4. Quick Check:

   (2+3)*5 = 25 [OK]

Hint: Calculate stepwise: operands first, then operator [OK]

Common Mistakes:

• Mixing operand order during pop
• Confusing '+' and '*' precedence
• Forgetting to push intermediate results

4. The following Go code attempts to evaluate a postfix expression but produces a runtime error. What is the error?

func evaluatePostfix(expr string) int {
    stack := []int{}
    for _, ch := range expr {
        if ch >= '0' && ch <= '9' {
            stack = append(stack, int(ch-'0'))
        } else {
            a := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            b := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            switch ch {
            case '+':
                stack = append(stack, a+b)
            case '*':
                stack = append(stack, a*b)
            }
        }
    }
    return stack[0]
}

What causes the error?

medium

A. Stack underflow due to popping before checking stack size

B. Operands are popped in wrong order causing wrong calculation

C. Invalid type conversion from rune to int

D. Missing case for '-' operator

Solution

1. Step 1: Analyze stack pop operations

   The code pops two operands without checking if stack has enough elements, risking empty slice access.

2. Step 2: Identify runtime error cause

   If expression is invalid or incomplete, popping causes stack underflow and runtime panic.

3. Final Answer:

   Stack underflow due to popping before checking stack size -> Option A

4. Quick Check:

   Always check stack size before popping [OK]

Hint: Check stack length before popping operands [OK]

Common Mistakes:

• Assuming stack always has enough operands
• Swapping operand pop order but no error
• Ignoring runtime panic messages

5. Given the postfix expression "82/3-4*", what is the final result after evaluation using a stack?

hard

A. 8

B. 2

C. 4

D. 6

Solution

1. Step 1: Evaluate "82/" part

   Push 8, push 2, '/' pops 2 and 8, divides 8/2 = 4, push 4.

2. Step 2: Evaluate "3-" part

   Push 3, '-' pops 3 and 4, subtracts 4-3 = 1, push 1.

3. Step 3: Evaluate "4*" part

   Push 4, '*' pops 4 and 1, multiplies 1*4 = 4, push 4.

4. Final Answer:

   4 -> Option C

5. Quick Check:

   (8/2 - 3) * 4 = 4 [OK]

Hint: Evaluate stepwise: divide, subtract, then multiply [OK]

Common Mistakes:

• Incorrect operand order in division or subtraction
• Forgetting operator precedence in postfix
• Mixing up intermediate stack values