Evaluate Postfix Expression Using Stack in DSA Go

Mental Model

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

Analogy: Imagine a pile of plates where you add plates (numbers) on top. When you get a special instruction (operator), you take the top two plates, combine them, and put the result back on top.

Stack (top at right): []
Expression: 2 3 + 4 *

Initial stack empty:
[]

After pushing 2:
[2]

After pushing 3:
[2 -> 3]

After '+' operator:
[5]

After pushing 4:
[5 -> 4]

After '*' operator:
[20]

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 the stack

[2]

Why: Numbers are pushed to stack to wait for operators

Step 2: Push 3 onto the stack

[2 -> 3]

Why: Keep numbers on stack until operator appears

Step 3: Pop 3 and 2, add them (2 + 3 = 5), push result 5

[5]

Why: Operator '+' means combine last two numbers by addition

Step 4: Push 4 onto the stack

[5 -> 4]

Why: Push next number to stack

Step 5: Pop 4 and 5, multiply them (5 * 4 = 20), push result 20

[20]

Why: Operator '*' means combine last two numbers by multiplication

Result:

[20] Final result is 20

Annotated Code

DSA Go

package main

import (
	"fmt"
	"strconv"
	"strings"
)

// Stack type to hold integers
type Stack []int

// Push adds an element to the stack
func (s *Stack) Push(val int) {
	*s = append(*s, val)
}

// Pop removes and returns the top element of the stack
func (s *Stack) Pop() int {
	val := (*s)[len(*s)-1]
	*s = (*s)[:len(*s)-1]
	return val
}

// EvaluatePostfix evaluates a postfix expression and returns the result
func EvaluatePostfix(expr string) int {
	tokens := strings.Fields(expr) // split expression by spaces
	var stack Stack

	for _, token := range tokens {
		// Try to convert token to integer
		val, err := strconv.Atoi(token)
		if err == nil {
			stack.Push(val) // push number to stack
		} else {
			// token is operator, pop two numbers
			right := stack.Pop() // second operand
			left := stack.Pop()  // first operand

			var res int
			switch token {
			case "+":
				res = left + right
			case "-":
				res = left - right
			case "*":
				res = left * right
			case "/":
				res = left / right
			}

			stack.Push(res) // push result back
		}
	}

	return stack.Pop() // final result
}

func main() {
	expr := "2 3 + 4 *"
	result := EvaluatePostfix(expr)
	fmt.Println(result)
}

val, err := strconv.Atoi(token)

Check if token is a number to push onto stack

stack.Push(val)

Push number token onto stack

right := stack.Pop()

Pop second operand for operator

left := stack.Pop()

Pop first operand for operator

switch token { ... }

Apply operator to operands

stack.Push(res)

Push result of operation back onto stack

return stack.Pop()

Return final result after processing all tokens

Output

20

Complexity Analysis

Time: O(n) because we process each token 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 0 or error depending on implementation; here it will panic on Pop

DSA Go

No explicit guard; stack.Pop() assumes non-empty stack

Single number expression like '5'

Returns that number as result

DSA Go

stack.Push(val) when token is number

Expression with division by zero

Runtime panic or error due to division by zero

DSA Go

No explicit guard for division by zero

When to Use This Pattern

When you see expressions without parentheses and operators after operands, use stack evaluation of postfix expressions because it simplifies calculation by removing precedence rules.

Common Mistakes

Mistake: Popping operands in wrong order causing incorrect results
Fix: Always pop right operand first, then left operand to maintain correct order

Mistake: Not splitting expression correctly by spaces
Fix: Use strings.Fields to split tokens properly

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 by popping the last two numbers from the stack.

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