Implement a basic calculator: evaluate a string arithmetic expression over integers without using Python's eval. Each part adds a feature to the same evaluate function.
Write evaluate(expr), returning an int.
expr holds non-negative integer literals, the operators + - * /, parentheses, and spaces.* and / bind tighter than + and -; operators of equal precedence apply left to right (10 - 4 - 3 is 3).- with no value before it (at the start, after (, or after another operator) is unary minus: -5, 3 * -2, -(2 + 3)./ is integer division that rounds toward zero: 7 / 2 is 3, -7 / 2 is -3. Python's // rounds -7 // 2 to -4, so it is not enough on its own.Every expression in this part is valid. Do not use eval.
7 3 2 26
print(evaluate("1 + 2 * 3"))
print(evaluate("10 - 4 - 3"))
print(evaluate("100 / 10 / 5"))
print(evaluate("2*3+4*5"))Evaluate an integer arithmetic string with + - * /, parentheses and unary minus, then nested add/sub/mul/div calls, then variables defined by other expressions, then raise ValueError on bad input.
Also known as: Basic Calculator II, Expression evaluator, Arithmetic expression parser
Expression evaluation and interpreters shows up in 6.1% of the 1,447 coding interview reports we studied, at 8 companies. Evaluate formulas or small programs, often where values depend on other values and cycles must be caught.
Reported at: Databricks, Roblox, OpenAI, Snowflake, Amazon, xAI, Cursor, Robinhood, Waymo, Harvey AI.
This is an original practice problem written by AceOffer to train the pattern. It is not a question any company asked.
Follow-ups candidates reported on questions with this pattern, in our words. Parts marked “from reports” below are built on them.
Implement a basic calculator: evaluate a string arithmetic expression over integers without using Python's eval. Each part adds a feature to the same evaluate function.
Write evaluate(expr), returning an int.
expr holds non-negative integer literals, the operators + - * /, parentheses, and spaces.* and / bind tighter than + and -; operators of equal precedence apply left to right (10 - 4 - 3 is 3).- with no value before it (at the start, after (, or after another operator) is unary minus: -5, 3 * -2, -(2 + 3)./ is integer division that rounds toward zero: 7 / 2 is 3, -7 / 2 is -3. Python's // rounds -7 // 2 to -4, so it is not enough on its own.Every expression in this part is valid. Do not use eval.
Expressions may now also contain function calls written as a name, an open parenthesis, comma-separated arguments and a close parenthesis: add(1, 2).
add, sub, mul and div. Each takes two or more arguments, and each argument is a full expression, so calls nest to any depth and mix freely with operators: add(1, mul(2, 3)) * 2, sub(10, 2 * 3).add sums all arguments and mul multiplies them. sub and div work left to right: sub(10, 2, 3) is (10 - 2) - 3 and div(100, 3, 2) is (100 / 3) / 2, where each / step rounds toward zero as in Part 1.Every expression in this part is valid.
Add variables: evaluate(expr, variables), where variables is a dict from name to value (it may be omitted or None, meaning no variables).
_ and continues with letters, digits or _. A name followed by ( is a function call; any other name is a variable. Names are case sensitive.int or a string holding another expression, which may use other variables and functions: {"base": 10, "total": "base * 3 + bonus", "bonus": "add(base, 5)"}. A string value is evaluated the first time it is needed, with the same variables dict, and reused after that within the same evaluate call.{"a": "b + 1", "b": "a"}, or {"x": "x"}), raise ValueError.Every variable used in this part is defined.
Make evaluate reject bad input. Raise ValueError (any message) when:
_, space, operator, comma or parenthesis,3 +, * 2), two values are side by side (2 3, (1)(2)), a pair of parentheses is empty, or a comma appears outside a call,add(1)),variables (also inside a variable's own definition),/ or div.No other exception type should escape for these cases (in particular not ZeroDivisionError).
Open this page on a laptop or desktop to write and run your code against the tests in the browser.
Spoilers: try each part before reading its walkthrough.
Split the work into a tokenizer and a recursive descent parser. The tokenizer turns the string into numbers (all consecutive digits at once) and single-character operators, dropping spaces. The parser has one function per precedence level: parse_sum handles + and -, parse_product handles * and /, and parse_factor handles a number, a parenthesised sub-expression, or a unary minus that negates the next factor. Each binary level loops rather than recursing on its right side, which is what makes 10 - 4 - 3 group as (10 - 4) - 3. Division divides absolute values with // and then reapplies the sign, giving truncation toward zero. Every token is consumed once, so evaluation is O(n), and the recursion depth equals the nesting depth.
Treat a call as one more kind of factor rather than a separate parser. In parse_factor, after reading a name, look at the next token: if it is (, parse one full parse_sum() for the first argument, then keep consuming , followed by another parse_sum() until you reach ). Because each argument goes through the whole grammar, nesting such as add(add(1, 1), 2) and mixing like sub(10, 2 * 3) need no special handling. This is the key improvement over splitting the string on commas, which breaks once an argument contains its own comma. Folding the argument list with functools.reduce gives left-to-right sub and div, and div reuses the same truncating helper as /. The cost stays O(n).
Names that are not followed by ( are variables. An int value is returned directly. A string value is itself an expression, so resolve it by running the same evaluator on that string, which handles definitions that use other variables or calls. Two pieces of state make this safe: a done dict that remembers each resolved name so a shared definition is evaluated once per call, and an active set of names currently being resolved. Seeing a name that is already active means the definitions loop back on themselves, so raise ValueError. This is depth-first search with cycle detection over the dependency graph of names, and only names actually reached are evaluated. Work is linear in the total size of the expressions visited.
Recursive descent makes error detection fall out of the structure. The tokenizer raises ValueError on any character it does not recognise. parse_factor raises when a token cannot start a value, which covers 3 +, * 2, empty input, () and a leading comma. A ( must be matched by ), both for grouping and for calls. After the top-level parse_sum(), any unused token means a stray ), a comma outside a call, or two values side by side such as 2 3. _apply rejects unknown function names and calls with fewer than two arguments, lookup rejects undefined variables, and the shared division helper raises on a zero divisor, so ZeroDivisionError never escapes. None of this changes the O(n) cost.
Tokenize first, then use one function per precedence level: sum handles + and -, product handles * and /, factor handles numbers, unary minus and parentheses. Loops inside sum and product give left-to-right grouping.
For rounding toward zero, divide the absolute values with // and then apply the sign.
A call is just another kind of factor: after reading a name, if the next token is '(', parse a sum, then keep parsing sums while you see a comma. Splitting on the first comma breaks as soon as an argument is itself a call.
Resolve string definitions recursively with two sets: names finished (with their values) and names in progress. Meeting a name that is still in progress means a cycle.
After parsing the top-level sum, check that every token was used. That single check catches stray ')' and values side by side.
Tokenizing and parsing are O(n) for an expression of length n; each token is looked at a constant number of times. Each variable definition is evaluated at most once per call thanks to the memo, so the total work is linear in the size of the expression plus all definitions it reaches. Recursion depth grows with nesting of parentheses, calls, unary minus and chains of variable definitions.
The company guides collect the questions candidates report, with every part, the follow-ups interviewers added, and how often each one comes up.
Browse the interview guides