Evaluate Postfix Expression Using Stack in DSA Go - Time & Space Complexity

Time Complexity: Evaluate Postfix Expression Using Stack

O(n)

Understanding Time Complexity

We want to understand how the time taken to evaluate a postfix expression changes as the expression gets longer.

Specifically, how does the number of steps grow with the size of the input expression?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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]
            a := stack[len(stack)-2]
            stack = stack[:len(stack)-2]
            switch ch {
            case '+': stack = append(stack, a+b)
            case '-': stack = append(stack, a-b)
            case '*': stack = append(stack, a*b)
            case '/': stack = append(stack, a/b)
            }
        }
    }
    return stack[0]
}
    

This code evaluates a postfix expression by scanning each character and using a stack to compute the result.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character of the expression once.
• How many times: Exactly once for each character in the input string.

How Execution Grows With Input

As the expression length grows, the number of steps grows directly with it.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The time grows linearly with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to evaluate grows directly in proportion to the length of the postfix expression.

Common Mistake

[X] Wrong: "Since there are nested operations inside the loop, the time complexity is quadratic O(n²)."

[OK] Correct: Each character is processed once, and stack operations are constant time, so no nested loops cause repeated passes.

Interview Connect

Understanding this linear time complexity helps you explain how stack-based evaluation is efficient and why it is preferred for expression evaluation in many real-world applications.

Self-Check

"What if the expression contained multi-digit numbers separated by spaces? How would the time complexity change?"

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