cf.completefrontend
STACKS & QUEUES · ADVANCED

Expression evaluation

Compute a math formula like 3 + 4 * 2 with two stacks, one for numbers and one for operators, respecting precedence and parentheses.

Time O(n)Space O(n)4 practice problemsStep-through picture

The idea

A formula such as 3 + 4 * 2 can't simply be computed left to right: * must happen before +, so the answer is 11, not 14. Which operators go first is called precedence. Parentheses override it.

The two-stack method reads the tokens (numbers, operators, and parentheses) once. Numbers go on a values stack. An operator waits on an ops stack until it is safe to run. Before pushing a new operator, any waiting operator with the same or higher precedence runs first, because it binds at least as tightly.

Running an operator pops two numbers, combines them, and pushes the result. A ( blocks operators below it from running; a ) runs everything back to its (. At the end, the remaining operators run and one number is left: the answer.

An everyday example

A kitchen with a ticket rail

A cook gets orders in sequence. Quick dishes can wait on the ticket rail, but if a more urgent ticket is already there, it gets cooked before the new one goes up. Parentheses are like a sealed bag of tickets: everything inside is finished before the bag counts as one dish.

How the example maps to the code
In the exampleIn the code
Finished dishes waiting to be combinedvalues
Tickets waiting on the railops
Cooking a ticket with the two latest dishesapply()
Urgency of a ticketprecedence[op]
A sealed bag of ticketsa ( ... ) pair

From the slow way to expression evaluation

  1. Start with the obvious way: read the formula left to right and apply each operator as soon as its right number arrives. For 2 + 3 * 4 that gives 20, but the right answer is 14, because * binds more tightly than +. Another obvious way is to find the tightest operator, compute it, rewrite the formula, and repeat. That is correct, but each round rescans the formula, so it can take O(n^2) time.
  2. Look at the moment an operator is read. You can't run it yet: its right side isn't known, and the next operator might bind more tightly, as * does after +. But you can now decide about the operator before it. If the waiting operator binds at least as tightly as the new one, its right side is complete, so it is safe to run now.
  3. Waiting operators are decided newest first: the most recent one is the one next to the new operator. That is last in, first out, so they go on a stack, ops. Numbers go on a second stack, values, because an operator always combines the two most recent results. Running an operator pops it and two numbers, right first, and pushes the result.
  4. Parentheses fit the same idea. A ( on ops is a wall: nothing below it may run until its ) arrives, and ) runs everything back to the wall. After the last token, every waiting operator can run. That loop is two-stack expression evaluation.

How it works

  1. Keep a values stack for numbers and an ops stack for operators and (.
  2. A number token is pushed onto values.
  3. A ( is pushed onto ops. A ) runs apply() until the top of ops is (, then pops that (.
  4. An operator first runs apply() while the top of ops is an operator with precedence greater than or equal to its own, then is pushed.
  5. apply() pops an operator and two numbers, right first, then left, and pushes left op right.
  6. After the last token, run apply() until ops is empty. values[0] is the answer.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function evaluate(tokens) {
  2. const precedence = { "+": 1, "-": 1, "*": 2, "/": 2 };
  3. const values = [];
  4. const ops = [];
  5. const top = () => ops[ops.length - 1];
  6. const apply = () => {
  7. const op = ops.pop();
  8. const right = values.pop();
  9. const left = values.pop();
  10. if (op === "+") values.push(left + right);
  11. else if (op === "-") values.push(left - right);
  12. else if (op === "*") values.push(left * right);
  13. else values.push(Math.trunc(left / right));
  14. };
  15. for (const token of tokens) {
  16. if (token === "(") {
  17. ops.push(token);
  18. } else if (token === ")") {
  19. while (top() !== "(") apply();
  20. ops.pop();
  21. } else if (token in precedence) {
  22. while (ops.length > 0 && top() !== "(" && precedence[top()] >= precedence[token]) apply();
  23. ops.push(token);
  24. } else {
  25. values.push(Number(token));
  26. }
  27. }
  28. while (ops.length > 0) apply();
  29. return values[0];
  30. }

How fast it is

TimeO(n)
Extra memoryO(n)

Each token is pushed once and each operator is applied once. In the worst case, such as deep parentheses, the stacks hold most of the tokens.

  • Best caseO(n)

    A flat formula like 1 + 2 + 3: each operator runs as soon as the next one arrives, so the stacks stay tiny.

  • Average caseO(n)

    Any valid formula. Each token is pushed once and each operator is applied once.

  • Worst caseO(n)

    Deep nesting like ((((4)))) or rising precedence like 1 + 2 * 3. Operators pile up and wait until the end, but each still runs once.

Common mistakes

  • Popping the operands in the wrong order, which computes right - left instead of left - right.
  • Using > instead of >= for equal precedence, which makes 8 - 3 - 2 come out as 8 - (3 - 2) = 7 instead of 3.
  • Using Math.floor for integer division, which gives the wrong answer for negative results.
  • Treating every - as subtraction, so a leading -5 or (-2) breaks the stacks.
  • Using eval on user input to skip writing this, which runs any code the user types.

When to use it

Look for these clues in a problem:

  • The input is a formula with +, -, *, /, and maybe parentheses.
  • The task mentions operator precedence or evaluating a string expression.
  • The input is in postfix form, such as 3 4 2 * +, where each operator follows its numbers (then one values stack is enough).
  • You need to convert an infix formula to postfix, or build a syntax tree for it.

Check yourself

Answer each one in your head first, then open it.

Why is right popped before left in apply?

The right number was pushed last, so it is on top. Popping in the other order would compute 3 - 18 instead of 18 - 3.

What does 9 - 4 - 3 give with > instead of >=?

8. Both - signs would wait and run from the right: 4 - 3 = 1, then 9 - 1 = 8, instead of the correct 2.

Why doesn't - run * when the top of ops is (?

The ( is a wall: the - is inside the parentheses, and the * outside must wait for the whole group's value. The while stops at top() !== "(".

How many times does apply run for a valid formula with p operators?

Exactly p times: each operator is pushed once and applied once. ( and ) are never applied.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 4 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps one rule about ops: between any two walls (( marks, or the bottom), the waiting operators have strictly rising precedence from bottom to top. A new operator first runs every waiting operator with precedence >= its own, so when it is pushed, everything below it up to the wall binds less tightly. Each waiting operator's left side is already a single number on values.

An operator only runs when its right side is finished. That happens when a new operator that binds no more tightly arrives, when a ) closes its group, or when the tokens run out. In each case nothing later can attach to its right side, so computing it now gives the same value as the formula's rules. Equal precedence also runs at once, which makes 9 - 4 - 3 compute (9 - 4) - 3 = 2, left to right.

Every token is handled once and every operator runs once, so the loop ends. At the end, ops is empty and each run turned two numbers into one, so a valid formula leaves exactly one number on values: the answer.

Going deeper

3 more ideas

Why waiting operators run first

When a new operator arrives, any waiting operator with higher precedence must happen before it, because it binds more tightly. A waiting operator with equal precedence must also run first, because operators like - and / work left to right: 8 - 3 - 2 is (8 - 3) - 2. Operators with lower precedence stay waiting, since the new operator must happen before them.

Cost

Every token is pushed once and every operator is applied once, so the time is O(n) for n tokens. The stacks can hold up to n items, for example with many nested parentheses.

Edge cases: division and unary minus

Integer division should usually truncate toward zero with Math.trunc(left / right), not round down with Math.floor, which gives -3 instead of -2 for -7 / 3. A minus sign at the start or right after ( means "negative", not subtraction; a common fix is to push a 0 first so -5 becomes 0 - 5.

Work it by hand

Every step in a table, with why

Evaluate a formula with parentheses, both precedence levels, and a division that must round toward zero.

tokens = 6 * ( 5 - 2 ) - 7 / 2

SteptokenAppliedvaluesopsWhy
16-[6][]Numbers go straight onto values.
2*-[6][*]ops is empty, so * just waits.
3(-[6][*, (]The ( blocks * from running until its ) arrives.
45-[6, 5][*, (]A number.
5--[6, 5][*, (, -]The top of ops is (, so the while stops at once and - waits on top of it, even though * binds more tightly.
62-[6, 5, 2][*, (, -]A number.
7)5 - 2 = 3[6, 3][*]Run everything back to (, which is just -, then pop the (. The parentheses now count as one number, 3.
8-6 * 3 = 18[18][-]* has precedence 2, at least the new -'s 1, so it runs first. Then - waits.
97-[18, 7][-]A number.
10/-[18, 7][-, /]- has precedence 1, lower than /'s 2, so it keeps waiting and / goes on top.
112-[18, 7, 2][-, /]The last token.
12end7 / 2 = 3, 18 - 3 = 15[15][]The final while runs what is left, top first. Math.trunc(7 / 2) is 3, then 18 - 3 is 15.

It returns 15: 6 * 3 is 18, 7 / 2 rounds toward zero to 3, and 18 - 3 is 15. The 11 tokens caused 4 operator runs, one per operator.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Expression evaluationO(n)O(n)You need to compute an infix formula with precedence and parentheses in one pass.
Repeatedly compute the tightest operatorO(n²)O(n)Short formulas typed by hand, where the clearest code matters more than speed.
Recursive descent parserO(n)O(n)The grammar will grow: functions, unary minus, comparisons. One function per level is easier to extend.

Extra memory: O(n): in the worst case, such as many nested parentheses, the two stacks hold most of the tokens at once.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Expression evaluation and the other approaches, on a scale where each line up is 10 times more steps.
  • Expression evaluation, Recursive descent parser O(n)
  • Repeatedly compute the tightest operator O(n²)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Expression evaluation101,0001 million
Repeatedly compute the tightest operator1001 million1 trillion
Recursive descent parser101,0001 million

Inputs that need care

6 tricky inputs
A single number: ["42"]
It is pushed onto values, no operator ever runs, and values[0] is 42.
A leading minus: ["-", "5"]
- is treated as subtraction, so at the end left is undefined and the answer is NaN. Push a 0 before a minus that starts the formula or follows (, so it becomes 0 - 5.
Negative division: 0 - 7 / 3
Math.trunc(-7 / 3) is -2, rounding toward zero as most languages do. Math.floor would give -3.
Division by zero: 7 / 0
7 / 0 is Infinity in JavaScript and Math.trunc keeps it, so the code returns Infinity instead of failing. Check right === 0 if the task wants an error.
A ) with no (, like 1 )
top() never equals (, so while (top() !== "(") apply() runs forever. Check that ops isn't empty inside that loop and report the error.
A ( that never closes, like ( 1 + 2
The final loop applies ( as if it were an operator and the result is NaN. Treat a ( left on ops at the end as an error.

Variations and follow-ups

Twists interviewers add

Postfix evaluation

In postfix form, such as 6 5 2 - *, every operator comes after its two numbers, so no operator ever waits. One values stack is enough: push numbers, and on an operator pop two, combine, and push the result.

Convert to postfix first

Instead of applying an operator, append it to an output list. The output is the postfix form of the formula, which can be stored and evaluated many times. This is Dijkstra's shunting-yard method.

Right-associative operators

Power, written ^, groups from the right: 2 ^ 3 ^ 2 is 2 ^ 9. For such an operator, run waiting operators only with strictly greater precedence, using > instead of >=.

Recursive descent

Write one function per precedence level: parseSum calls parseProduct, which calls parseFactor, and parseFactor handles numbers and parentheses. The call stack plays the role of ops. It is easier to extend with functions and unary operators.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "evaluate the expression", "basic calculator", "respect operator precedence", or a list of tokens with +, -, *, /, and parentheses.
  • Explain the waiting rule out loud: "an operator waits until the next operator arrives; if the waiting one binds at least as tightly, it runs first". Then explain why equal precedence runs: left to right order for - and /.
  • Test by hand on 9 - 4 - 3 (should be 2), 2 + 3 * 4 (should be 14), and one formula with parentheses. Then mention negative division and a leading minus.
  • Expect the follow-up "what if the input is a string with spaces and multi-digit numbers?". Tokenize first: read digits while they continue, skip spaces, and treat a - at the start or after ( as a sign.

Where frontend code uses it

The same idea in real UI code
  • Spreadsheet-like formula bars in dashboards and no-code tools evaluate user formulas with precedence, usually by parsing them this way rather than with eval.
  • JavaScript parsers such as Acorn parse binary operators like a + b * c by comparing operator precedence, the same rule this method uses.
  • CSS calc() expressions mix +, -, *, and / with normal precedence and parentheses, and the browser has to evaluate them while computing styles.

Related algorithms