Expression Evaluation

Dijkstra's Shunting Yard algorithm converts infix expressions to postfix using a stack for operators; a second stack then evaluates the result in one pass.

6 min read Level 4/5 #dsa#stack#expression-evaluation

What you'll learn

Convert an infix expression to postfix (RPN) using the Shunting Yard algorithm
Evaluate a postfix expression with a single operand stack in O(n)
Handle operator precedence and left/right associativity correctly

Humans write 3 + 4 * 2 (infix); computers evaluate 3 4 2 * + (postfix / Reverse Polish Notation) more easily because postfix needs no parentheses and no precedence rules — a single left-to-right scan with an operand stack is enough. Dijkstra’s Shunting Yard algorithm is the bridge between them.

Step 1 — Evaluate Postfix (RPN)

Before tackling conversion, let’s see how clean postfix evaluation is:

function evalPostfix(tokens) {
  const stack = [];

  for (const tok of tokens) {
    if (!isNaN(tok)) {
      stack.push(Number(tok));
    } else {
      const b = stack.pop();
      const a = stack.pop();
      switch (tok) {
        case "+": stack.push(a + b); break;
        case "-": stack.push(a - b); break;
        case "*": stack.push(a * b); break;
        case "/": stack.push(Math.trunc(a / b)); break;
        default: throw new Error("Unknown operator: " + tok);
      }
    }
  }

  return stack[0];
}

// "3 4 2 * +" → 3 + (4 * 2) = 11
console.log(evalPostfix(["3", "4", "2", "*", "+"])); // 11

Each operator pops its two operands, computes a result, and pushes it back. One pass, one stack, O(n) time.

Step 2 — Infix to Postfix (Shunting Yard)

The algorithm uses an operator stack and produces an output queue:

Number → push directly to output.
Operator → pop operators from the stack to output while they have higher or equal precedence (and are left-associative), then push the new operator.
( → push to operator stack.
) → pop to output until ( is found; discard both parens.
End of input → flush remaining operators to output.

const PREC = { "+": 1, "-": 1, "*": 2, "/": 2, "^": 3 };
const RIGHT_ASSOC = new Set(["^"]);

function toPostfix(tokens) {
  const output = [];
  const ops = [];

  for (const tok of tokens) {
    if (!isNaN(tok)) {
      output.push(tok);
    } else if (tok in PREC) {
      while (
        ops.length &&
        ops.at(-1) !== "(" &&
        (PREC[ops.at(-1)] > PREC[tok] ||
          (PREC[ops.at(-1)] === PREC[tok] && !RIGHT_ASSOC.has(tok)))
      ) {
        output.push(ops.pop());
      }
      ops.push(tok);
    } else if (tok === "(") {
      ops.push(tok);
    } else if (tok === ")") {
      while (ops.length && ops.at(-1) !== "(") {
        output.push(ops.pop());
      }
      ops.pop(); // discard "("
    }
  }

  while (ops.length) output.push(ops.pop());
  return output;
}

const tokens = ["3", "+", "4", "*", "2"];
console.log(toPostfix(tokens)); // ["3", "4", "2", "*", "+"]

Putting It Together

function calculate(expr) {
  const tokens = expr.match(/\d+|[+\-*/^()]/g);
  return evalPostfix(toPostfix(tokens));
}

console.log(calculate("3 + 4 * 2"));      // 11
console.log(calculate("(3 + 4) * 2"));    // 14
console.log(calculate("2 ^ 3 ^ 2"));      // 512  (right-associative: 2^(3^2))

Complexity

Phase	Time	Space
Shunting Yard	O(n)	O(n)
Postfix eval	O(n)	O(n)
Total	O(n)	O(n)

Each token is pushed and popped at most once in each phase.

Precedence Table

Operator	Precedence	Associativity
+, -	1	Left
*, /	2	Left
^	3	Right

Extending to unary minus, functions (sin, max), and comma-separated arguments follows the same framework — push function names onto the operator stack and handle commas like a low-precedence separator.

Up Next

Stack and queue mastery opens the door to recursion, where the call stack does the bookkeeping for you.

Recursion Intro →