Evaluate Postfix Expression Using Stack in DSA Go - Build from Scratch

Evaluate Postfix Expression Using Stack

📖 Scenario: Imagine you are building a simple calculator that reads a math expression written in postfix form (also called Reverse Polish Notation). This calculator uses a stack to evaluate the expression step-by-step.

🎯 Goal: Build a Go program that evaluates a postfix expression using a stack and prints the final result.

📋 What You'll Learn

Create a slice of strings called postfix containing the postfix expression tokens

Create an empty slice of integers called stack to use as a stack

Write a loop to process each token in postfix

If the token is a number, convert it to int and push it onto stack

If the token is an operator (+, -, *, /), pop two numbers from stack, apply the operator, and push the result back

Print the final value left in stack after processing all tokens

💡 Why This Matters

🌍 Real World

Postfix expressions are used in calculators and compilers to evaluate math expressions without needing parentheses.

💼 Career

Understanding stack-based expression evaluation is important for software developers working on interpreters, calculators, and expression parsers.

1

Create the postfix expression slice

Create a slice of strings called postfix with these exact tokens: "2", "3", "1", "*", "+", "9", "-"

DSA Go

# Your code here

Hint

The postfix expression is a slice of strings with the exact tokens given.

2

Create an empty stack slice

Add a slice of integers called stack initialized as empty right after the postfix slice

DSA Go

package main

func main() {
    postfix := []string{"2", "3", "1", "*", "+", "9", "-"}
    
    // Your code here
}

Hint

Use stack := []int{} to create an empty integer slice.

3

Process each token and evaluate the expression

Write a for loop using for _, token := range postfix to process each token. Inside the loop, if token is a digit, convert it to int and append it to stack. If token is an operator (+, -, *, /), pop the last two numbers from stack, apply the operator, and append the result back to stack. Use strconv.Atoi(token) to convert string to int. Import strconv package.

DSA Go

package main

import "strconv"

func main() {
    postfix := []string{"2", "3", "1", "*", "+", "9", "-"}
    stack := []int{}

    // Use for _, token := range postfix to loop
    // Convert numbers and push to stack
    // For operators, pop two, compute, push result
}

Hint

Use a switch to check if token is operator or number. Pop last two from stack for operators, compute, then push result.

4

Print the final result from the stack

Add a fmt.Println(stack[0]) statement after the loop to print the final evaluated result from the stack slice.

DSA Go

package main

import (
    "fmt"
    "strconv"
)

func main() {
    postfix := []string{"2", "3", "1", "*", "+", "9", "-"}
    stack := []int{}

    for _, token := range postfix {
        switch token {
        case "+", "-", "*", "/":
            b := stack[len(stack)-1]
            a := stack[len(stack)-2]
            stack = stack[:len(stack)-2]
            var res int
            if token == "+" {
                res = a + b
            } else if token == "-" {
                res = a - b
            } else if token == "*" {
                res = a * b
            } else if token == "/" {
                res = a / b
            }
            stack = append(stack, res)
        default:
            num, _ := strconv.Atoi(token)
            stack = append(stack, num)
        }
    }

    // Print the final result
}

Hint

The final result is the only number left in the stack. Print stack[0].

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