Building a Calculator

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.

1. Notation Types

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

2. The Algorithm: Shunting-yard

Created by Edsger Dijkstra. It converts Infix → Postfix using a Stack.

1. Number: Print it (Output).
2. Operator (+, *, -): Push to stack. Pop higher precedence operators first!
3. Left Paren: Push.
4. Right Paren: Pop until matching Left Paren.

Interactive: Calculator Logic

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

Expression: 3 + 4 * 2

Operator Stack

Output (Postfix)

Ready.

3. Evaluating Postfix (RPN)

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.

Java

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();
}

Go

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]
}