Building a Calculator

[!NOTE] This module explores the core principles of Expression Evaluation, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Concept Definition

How does 3 + 4 * 2 equal 11 and not 14? Computers don’t understand “Order of Operations” (PEMDAS) intuitively. They need a structured way to process expressions.

Notation Types:

1. Infix: 3 + 4 (Human readable). Hard for machines due to parentheses and precedence.
2. Postfix (Reverse Polish Notation - RPN): 3 4 + (Machine friendly). No parentheses needed!

The Algorithm (Shunting-yard): Converts Infix → Postfix using a Stack.

---

2. Interactive Analysis

Convert 3 + 4 * 2 to 3 4 2 * + and evaluate it.

Expression: 3 + 4 * 2

Operator Stack

Output (Postfix)

Ready.

---

3. Intuition: RPN Evaluation

Once we have 3 4 2 * +, evaluating is easy with a Stack:

1. Scan: 3, Push. 4, Push. 2, Push. Stack: [3, 4, 2]
2. Scan *: Pop 2, Pop 4. Calc 4 * 2 = 8. Push 8. Stack: [3, 8]
3. Scan +: Pop 8, Pop 3. Calc 3 + 8 = 11. Push 11.
4. Result: 11.

---

4. Implementation

Java

Go

public int evalRPN(String[] tokens) {
  Deque<Integer> stack = new ArrayDeque<>();
  for (String t : tokens) {
    if ("+".equals(t)) {
      stack.push(stack.pop() + stack.pop());
    } else if ("*".equals(t)) {
      stack.push(stack.pop() * stack.pop());
    } else {
      stack.push(Integer.parseInt(t));
    }
  }
  return stack.pop();
}

func evalRPN(tokens []string) int {
  stack := []int{}
  for _, t := range tokens {
    if t == "+" {
      a, b := stack[len(stack)-1], stack[len(stack)-2]
      stack = stack[:len(stack)-2]
      stack = append(stack, a+b)
    } else if t == "*" {
      a, b := stack[len(stack)-1], stack[len(stack)-2]
      stack = stack[:len(stack)-2]
      stack = append(stack, a*b)
    } else {
      val, _ := strconv.Atoi(t)
      stack = append(stack, val)
    }
  }
  return stack[0]
}

---

5. Complexity Analysis

Strategy	Time	Space	Notes
Shunting-yard	O(N)	O(N)	Linear scan. Stack stores operators.
RPN Eval	O(N)	O(N)	Linear scan. Stack stores operands.