C# Stack and Queue: evaluating postfix expressions

Before you start

C# generic collections and switch expressions.

Use a stack to evaluate expressions written in reverse Polish notation and a queue for first-in order.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

Stack<T> is last-in, first-out with Push, Pop, and Peek. Queue<T> is first-in, first-out with Enqueue and Dequeue. Both operations are O(1). Popping from an empty stack or queue throws InvalidOperationException.

In postfix notation the operator comes after its operands: 3 4 + means 3 + 4. A stack evaluates it in one pass. Push each number. For an operator, pop two numbers, the right operand first, apply the operator, and push the result. At the end the stack holds the answer. No parentheses or precedence rules are needed, which is why compilers and calculators use this form internally.

Code example

using System;
using System.Collections.Generic;

class Program {
  static int EvalPostfix(string expression) {
    var stack = new Stack<int>();
    foreach (string token in expression.Split(' ')) {
      if (int.TryParse(token, out int number)) {
        stack.Push(number);
      } else {
        int right = stack.Pop();
        int left = stack.Pop();
        stack.Push(token switch {
          "+" => left + right,
          "-" => left - right,
          "*" => left * right,
          "/" => left / right,
          _ => throw new ArgumentException("bad operator " + token),
        });
      }
    }
    return stack.Pop();
  }

  static void Main() {
    Console.WriteLine(EvalPostfix("3 4 + 2 *"));
    Console.WriteLine(EvalPostfix("5 1 2 + 4 * + 3 -"));
    try {
      EvalPostfix("2 3 ^");
    } catch (ArgumentException e) {
      Console.WriteLine(e.Message);
    }

    var line = new Queue<string>();
    line.Enqueue("Ada");
    line.Enqueue("Bo");
    line.Enqueue("Cy");
    Console.WriteLine(line.Dequeue() + " served, " + line.Count + " waiting, next is " + line.Peek());
  }
}

Output

14
14
bad operator ^
Ada served, 2 waiting, next is Bo

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1using System;

2using System.Collections.Generic;

4class Program {

5 static int EvalPostfix(string expression) {

6 var stack = new Stack<int>();

7 foreach (string token in expression.Split(' ')) {

8 if (int.TryParse(token, out int number)) {

9 stack.Push(number);

10 } else {

11 int right = stack.Pop();

12 int left = stack.Pop();

13 stack.Push(token switch {

14 "+" => left + right,

15 "-" => left - right,

16 "*" => left * right,

17 "/" => left / right,

18 _ => throw new ArgumentException("bad operator " + token),

19 });

20 }

21 }

22 return stack.Pop();

23 }

25 static void Main() {

26 Console.WriteLine(EvalPostfix("3 4 + 2 *"));

27 Console.WriteLine(EvalPostfix("5 1 2 + 4 * + 3 -"));

28 try {

29 EvalPostfix("2 3 ^");

30 } catch (ArgumentException e) {

31 Console.WriteLine(e.Message);

32 }

34 var line = new Queue<string>();

35 line.Enqueue("Ada");

36 line.Enqueue("Bo");

37 line.Enqueue("Cy");

38 Console.WriteLine(line.Dequeue() + " served, " + line.Count + " waiting, next is " + line.Peek());

39 }

40}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
A number goes onto the stack.	`—`	—
The right operand was pushed last, so it is popped first.	`—`	—
Order matters for subtraction and division, so the operands are named.	`—`	—
3 4 + gives 7, then 7 2 * gives 14.	`—`	14
1 + 2 = 3, 3 * 4 = 12, 5 + 12 = 17, 17 − 3 = 14.	`—`	14 14
An unknown operator is reported with an exception.	`—`	14 14 bad operator ^
The queue serves the person who arrived first.	`—`	14 14 bad operator ^ Ada served, 2 waiting, next is Bo

Behind the scenes

How C# processes this code

C# compiles to code for the .NET runtime, which invokes the program entry point.

Cost and common mistakes

O(n) time and O(n) space for n tokens.

A malformed expression such as 3 + makes Pop throw InvalidOperationException. A robust evaluator checks the stack size first.
Integer division by zero throws DivideByZeroException.
The tokens must be separated by single spaces here. A real tokenizer also handles multiple spaces and negative numbers.

Try it yourself

Write 2 + 3 * 4 in postfix.

Reveal answer and reasoning

2 3 4 * +: multiply 3 and 4 first, then add 2, which gives 14.