CODING CHALLENGE · N°39

Expression Calculator

Medium ParsingRecursionStack

Evaluate an arithmetic expression string — with operator precedence and parentheses — the way an interpreter or spreadsheet does. A tiny recursive-descent parser handles precedence naturally: expressions of terms, terms of factors. Solve it in Python or TypeScript, with hidden tests.

The problem

Implement calc(expr): evaluate a string containing non-negative integers, the operators + - * /, parentheses, and spaces, respecting the usual precedence (* and / bind tighter than + and -) and left-to-right associativity. / is real division. Return the numeric result.

EXAMPLE 1

Input expr = '2+3*4'

Output 14

multiplication first

EXAMPLE 2

Input expr = '(2+3)*4'

Output 20

parentheses override precedence

EXAMPLE 3

Input expr = '2*(3+(4-1))'

Output 12

nested parentheses

CONSTRAINTS

Operands are non-negative integers; the expression is well-formed.
Precedence: *// before +/-; associativity is left-to-right.
Spaces may appear anywhere and should be ignored.
Recommended: recursive descent — expr = term (("+"|"-") term)*, term = factor (("*"|"/") factor)*, factor = number | "(" expr ")".

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement calc(expr) as a recursive-descent parser over a position cursor: parse_expr handles + and −, parse_term handles * and /, and parse_factor reads a number or a parenthesised sub-expression. Precedence falls out of the grammar.

HINTS — 4 IDEAS

Strip spaces, then keep a moving index into the string. Each parse function advances it.
factor: if the next char is "(", consume it, parse a full expression, consume ")". Otherwise read a run of digits as an integer.
term: parse a factor, then while the next char is "*" or "/", consume it, parse another factor, and combine.
expr: parse a term, then while the next char is "+" or "-", consume and combine. The grammar gives you precedence for free.

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

Evaluate respecting operator precedence — you cannot just go left to right. Two clean ways: a two-stack evaluator (one stack of values, one of operators, applying a pending operator when one of lower-or-equal precedence arrives) or the shunting-yard algorithm that converts to RPN and then evaluates. Parentheses push a sub-context that resolves before you continue.

Complexity

Time O(n) in the expression length; space O(n) for the stacks.

Common mistakes

Ignoring precedence — evaluating 2 + 3 * 4 left to right gives 20 instead of 14.
Mishandling parentheses (unbalanced, or not resolving the inner expression first).
Forgetting multi-digit numbers or unary minus while tokenizing.

Where this shows up

This is a tiny parser-evaluator, and the same precedence-and-stack machinery scales up to real language interpreters, spreadsheet formula engines, database query parsers, and config expression languages. Getting precedence right by hand is the transferable skill.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA