Evaluate Postfix Expression Using Stack in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Postfix Expression Evaluation

What is the output of the following Go code that evaluates a postfix expression using a stack?

DSA Go

package main

import (
	"fmt"
	"strconv"
)

func evaluatePostfix(expr string) int {
	stack := []int{}
	for _, ch := range expr {
		if ch >= '0' && ch <= '9' {
			num, _ := strconv.Atoi(string(ch))
			stack = append(stack, num)
		} 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)
			case '*':
				stack = append(stack, a*b)
			case '/':
				stack = append(stack, a/b)
			}
		}
	}
	return stack[0]
}

func main() {
	expr := "231*+9-"
	result := evaluatePostfix(expr)
	fmt.Println(result)
}

A 9

B 2

C 7

D -4

💡 Hint

Trace the stack operations step-by-step for each character in the expression.

The postfix expression "231*+9-" is evaluated as follows:

• Push 2
• Push 3
• Push 1
• Pop 1 and 3, multiply: 3*1=3, push 3
• Pop 3 and 2, add: 2+3=5, push 5
• Push 9
• Pop 9 and 5, subtract: 5-9=-4, push -4

Final result is -4.

🧠 Conceptual

intermediate

Stack Behavior in Postfix Evaluation

During the evaluation of a postfix expression using a stack, what happens when an operator is encountered?

A Two operands are popped from the stack, the operator is applied, and the result is pushed back.

B Only one operand is popped and the operator is applied to it.

C The stack is cleared and the operator is ignored.

D The operator is pushed onto the stack to be used later.

💡 Hint

Think about how operators combine numbers in postfix notation.

In postfix evaluation, when an operator is found, the last two numbers are taken from the stack, the operation is performed, and the result is pushed back onto the stack.

🔧 Debug

advanced

Identify the Error in Postfix Evaluation Code

What error will the following Go code produce when evaluating the postfix expression "82/"? func evaluatePostfix(expr string) int { stack := []int{} for _, ch := range expr { if ch >= '0' && ch <= '9' { num, _ := strconv.Atoi(string(ch)) stack = append(stack, num) } 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) case '*': stack = append(stack, a*b) case '/': stack = append(stack, a/b) } } } return stack[0] }

A No error, outputs 4

B Division by zero panic

C Index out of range panic

D Syntax error

💡 Hint

Check the order of popping operands from the stack.

The code pops operands in wrong order: it pops 'a' first then 'b', but for division, the second popped should be the divisor. This causes incorrect stack access and panic.

❓ Predict Output

advanced

Result of Complex Postfix Expression

What is the output of the following Go code evaluating the postfix expression "562+*84/-"?

DSA Go

package main

import (
	"fmt"
	"strconv"
)

func evaluatePostfix(expr string) int {
	stack := []int{}
	for _, ch := range expr {
		if ch >= '0' && ch <= '9' {
			num, _ := strconv.Atoi(string(ch))
			stack = append(stack, num)
		} 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)
			case '*':
				stack = append(stack, a*b)
			case '/':
				stack = append(stack, a/b)
			}
		}
	}
	return stack[0]
}

func main() {
	expr := "562+*84/-"
	result := evaluatePostfix(expr)
	fmt.Println(result)
}

A 20

B 10

C 30

D 14

💡 Hint

Evaluate step-by-step, carefully applying each operator.

Stepwise evaluation:

• Push 5,6,2
• Pop 2 and 6, add: 6+2=8, push 8
• Pop 8 and 5, multiply: 5*8=40, push 40
• Push 8,4
• Pop 4 and 8, subtract: 8-4=4, push 4
• Pop 4 and 40, divide: 40/4=10, push 10

Final result is 10.

🧠 Conceptual

expert

Why Use Stack for Postfix Evaluation?

Why is a stack the ideal data structure for evaluating postfix expressions?

A Because it allows easy access to the last operands needed for operations in LIFO order.

B Because it stores all operands in sorted order automatically.

C Because it prevents any errors during evaluation.

D Because it can store operators and operands separately.

💡 Hint

Think about how postfix expressions require the most recent operands first.

Stacks follow Last-In-First-Out order, which matches the need to use the most recent operands first when an operator is encountered in postfix evaluation.

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