Evaluate Postfix Expression Using Stack in DSA C#

Mental Model

We use a stack to keep numbers until we find an operator, then we combine the last two numbers using that operator.

Analogy: Imagine a chef stacking ingredients on a plate. When the chef sees a cooking step (operator), they take the last two ingredients, cook them together, and put the result back on the plate.

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

Initial empty stack:
[]

Reading tokens left to right:
2 3 + 4 *

Dry Run Walkthrough

Input: postfix expression: 2 3 + 4 *

Goal: Calculate the final value of the postfix expression using a stack

Step 1: Read '2', push it onto the stack

Stack: [2]

Why: Numbers are pushed to wait for operators

Step 2: Read '3', push it onto the stack

Stack: [2, 3]

Why: Keep numbers until operator appears

Step 3: Read '+', pop 3 and 2, add them (2+3=5), push result back

Stack: [5]

Why: Operator applies to last two numbers

Step 4: Read '4', push it onto the stack

Stack: [5, 4]

Why: Push next number for future operation

Step 5: Read '*', pop 4 and 5, multiply them (5*4=20), push result back

Stack: [20]

Why: Apply operator to last two numbers

Result:

Stack: [20]
Final result: 20

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class PostfixEvaluator
{
    public static int Evaluate(string expression)
    {
        Stack<int> stack = new Stack<int>();
        string[] tokens = expression.Split(' ');

        foreach (string token in tokens)
        {
            if (int.TryParse(token, out int number))
            {
                stack.Push(number); // push number to stack
            }
            else
            {
                int right = stack.Pop(); // pop right operand
                int left = stack.Pop();  // pop left operand

                int result = token switch
                {
                    "+" => left + right,
                    "-" => left - right,
                    "*" => left * right,
                    "/" => left / right,
                    _ => throw new InvalidOperationException("Invalid operator")
                };

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

        return stack.Pop(); // final result
    }

    static void Main()
    {
        string expr = "2 3 + 4 *";
        int result = Evaluate(expr);
        Console.WriteLine(result);
    }
}

stack.Push(number); // push number to stack

push numbers onto stack to wait for operators

int right = stack.Pop(); // pop right operand

pop last number for right operand

int left = stack.Pop(); // pop left operand

pop second last number for left operand

int result = token switch { ... }

apply operator to left and right operands

stack.Push(result); // push result back

push computed result back to stack

return stack.Pop(); // final result

pop 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 on stack

vs Alternative: Compared to evaluating infix expressions which need operator precedence handling, postfix evaluation is simpler and faster using a stack

Edge Cases

Empty expression

Throws error or returns no result because no tokens to process

DSA C#

return stack.Pop(); // final result

Single number only

Returns that number as result

DSA C#

stack.Push(number); // push number to stack

Invalid operator

Throws InvalidOperationException

DSA C#

_ => throw new InvalidOperationException("Invalid operator")

When to Use This Pattern

When you see an expression with operators after operands and need to calculate result, use the Evaluate Postfix Expression Using Stack pattern because it handles operations in correct order without parentheses.

Common Mistakes

Mistake: Popping operands in wrong order (left and right swapped)
Fix: Pop right operand first, then left operand to maintain correct operation order

Mistake: Trying to evaluate infix expression directly without converting
Fix: Use postfix expression or convert infix to postfix before evaluation

Summary

Calculates the value of a postfix expression using a stack to store operands.

Use when you need to evaluate expressions where operators come after operands without parentheses.

Push numbers on stack, pop two for each operator, apply operator, and push result back until done.

Practice

1. What is the main data structure used to evaluate a postfix expression?

easy

A. Array

B. Queue

C. Stack

D. Linked List

Solution

1. Step 1: Understand postfix evaluation process

   Postfix expressions are evaluated by pushing operands onto a stack and popping them when an operator is encountered. The stack allows last-in, first-out access which is perfect for postfix evaluation.

2. Final Answer:

   Stack -> Option C

3. Quick Check:

   Postfix evaluation uses stack [OK]

Hint: Postfix needs last-in-first-out structure: stack [OK]

Common Mistakes:

• Confusing stack with queue
• Using array without stack logic
• Thinking linked list is primary structure

2. Which of the following C# code snippets correctly pushes an integer operand onto a stack named stack?

easy

A. stack.Push(operand);

B. stack.Add(operand);

C. stack.Insert(operand);

D. stack.Enqueue(operand);

Solution

1. Step 1: Recall C# Stack.Push method

   In C#, the method to add an element to a stack is Push. Enqueue is for queues; Add and Insert are not stack methods.

2. Final Answer:

   stack.Push(operand); -> Option A

3. Quick Check:

   Use Push() to add to stack [OK]

Hint: Use Push() to add items to stack in C# [OK]

Common Mistakes:

• Using Enqueue which is for queues
• Using Add or Insert which are not stack methods
• Confusing stack with list methods

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

string expr = "23+5*";
Stack<int> stack = new Stack<int>();
foreach (char c in expr)
{
    if (char.IsDigit(c))
        stack.Push(c - '0');
    else
    {
        int b = stack.Pop();
        int a = stack.Pop();
        if (c == '+') stack.Push(a + b);
        else if (c == '*') stack.Push(a * b);
    }
}
Console.WriteLine(stack.Pop());

medium

A. 25

B. 15

C. 10

D. Error

Solution

1. Step 1: Trace code execution

   Push 2, push 3; '+' pops b=3, a=2, push 5. Push 5; '*' pops b=5, a=5, push 25. Final pop prints 25.

2. Final Answer:

   25 -> Option A

3. Quick Check:

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

Hint: Calculate stepwise: operands pushed, operators pop two values [OK]

Common Mistakes:

• Mixing operand order when popping
• Confusing '+' and '*' operations
• Forgetting to convert char digits to int

4. Identify the error in the following C# code snippet that evaluates a postfix expression:

string expr = "82/";
Stack<int> stack = new Stack<int>();
foreach (char c in expr)
{
    if (char.IsDigit(c))
        stack.Push(c - '0');
    else
    {
        int a = stack.Pop();
        int b = stack.Pop();
        if (c == '/') stack.Push(b / a);
    }
}
Console.WriteLine(stack.Pop());

medium

A. Stack is not initialized

B. Operands are popped in wrong order

C. Division operator is not handled

D. Digits are not converted to integers

Solution

1. Step 1: Trace popping and computation for division

   Push 8, push 2 (top=2). For '/', b=Pop()=2 (right), a=Pop()=8 (left), but pushes b/a=2/8=0 instead of a/b=8/2=4. Operands popped correctly but used/applied in wrong order for non-commutative division.

2. Final Answer:

   Operands are popped in wrong order -> Option B

3. Quick Check:

   Pop right first (b), left second (a), compute a / b [OK]

Hint: Pop second operand first, then first operand for correct order [OK]

Common Mistakes:

• Swapping operand order causing wrong division
• Not handling division operator
• Forgetting to convert char to int

5. Given the postfix expression "6523+8*+3+*", what is the final result after evaluation using a stack?

hard

A. 2880

B. Incorrect expression

C. None (runtime error)

D. 288

Solution

1. Step 1: Evaluate postfix step-by-step

   Push 6,5,2,3; '+' pops 3&2 push 5 (stack:6,5,5); push 8; '*' pops 8&5 push 40 (6,5,40); '+' pops 40&5 push 45 (6,45); push 3 (6,45,3); '+' pops 3&45 push 48 (6,48); '*' pops 48&6 push 288.

2. Final Answer:

   288 -> Option D

3. Quick Check:

   Stepwise postfix evaluation = 288 [OK]

Hint: Evaluate postfix stepwise, push operands, apply operators [OK]

Common Mistakes:

• Misordering operands during pop
• Skipping steps in complex expressions
• Confusing operator precedence in postfix