A config language writes arithmetic as nested function calls instead of infix operators. Write evaluate(expr: str) -> int that computes the value of such an expression.
Grammar
expr := integer | name "(" expr ("," expr)* ")"
name := "add" | "sub"
- An
integeris one or more digits, optionally preceded by a single-(e.g.7,-12,0). add(a, b, ...)takes two or more arguments and returns their sum.sub(a, b)takes exactly two arguments and returnsa - b.- Spaces may appear anywhere between tokens (never inside a number or a name).
The input is always valid. Every number, and every intermediate and final result, fits in a signed 64-bit integer. The input can be up to 200,000 characters long, and calls can be nested thousands of levels deep, so don't recurse once per nesting level (Python's default limit is about 1,000 frames). Aim for one left-to-right pass; re-scanning the string for the innermost call over and over is quadratic.
evaluate("42") # 42
evaluate("add(1, 2)") # 3
evaluate("sub(10, add(3, 4))") # 3
evaluate("add(sub(0, 5), -6, 20)") # 9
evaluate(" sub( sub(1,2) , sub(3 ,-4) ) ") # -8
Show hint
Keep a stack of open calls, each holding its name and the arguments collected so far. A number becomes an argument of the call on top; a ) finishes the top call and its value becomes an argument of the call below it.