266. Arithmetic Expression Evaluation

Given a string containing a valid arithmetic expression made of non-negative integers, the operators + - * /, and parentheses (no spaces), evaluate it and print the result, respecting standard operator precedence (* and / before + and -) and parentheses. Division truncates toward zero, like integer division in C/Java.

Input: The input is a single line containing the expression string (non-negative integers, the operators + - * /, and parentheses, no spaces). Output: Print a single integer - the evaluated result of the expression.

1 <= |expression| <= 10^5, all intermediate and final values fit in a 64-bit signed integer

This is essentially the SAME two-stack technique used by full expression parsers and compilers (like the shunting-yard algorithm) - understanding it here builds real intuition for how programming languages parse arithmetic expressions under the hood.

Evaluate a standard infix arithmetic expression (with +, -, *, /, and parentheses), respecting normal operator precedence and grouping. Brute force: Convert the infix expression to postfix first (using the shunting-yard algorithm, itself stack-based) and then evaluate the postfix separately - this works and is a valid two-step approach, though the two-stack method achieves the same result in a single combined pass. Optimised: Maintaining number and operator stacks SIMULTANEOUSLY, resolving operators eagerly whenever precedence allows (and respecting parentheses as hard barriers), evaluates the expression correctly in a single pass without ever needing to build an explicit postfix intermediate representation.

Merge the two phases of the Shunting Yard approach into one pass, using a values stack and an operators stack simultaneously: read each token once, and whenever the next operator has lower-or-equal precedence than the operator on top of the stack, immediately pop and apply that pending operator to the top two values before pushing the new one, rather than first materializing a full postfix token list and evaluating it afterward. This produces the exact same result as the two-pass version but does it in one traversal of the input, avoiding the extra memory and pass needed to store an intermediate postfix sequence. Time: O(n) Space: O(n)

Repeatedly find the innermost parenthesized substring, evaluate it with a naive left-to-right scan that first resolves all * and / occurrences by splicing their result back into the string, then resolves all remaining + and -, and substitute that computed value back into the original string in place of the parenthesized substring; repeat this whole process until no parentheses remain, then do one final left-to-right reduction on the flat expression. This correctly respects both parentheses and precedence by construction, but rebuilding and rescanning the string after every substitution is expensive and wasteful for long expressions. Time: O(n^2) or worse due to repeated string rebuilding Space: O(n)

First convert the infix expression into postfix (Reverse Polish Notation) using an operator stack: push numbers straight to an output list, push operators onto the stack only after popping off any operators of equal or higher precedence first, and use parentheses to force pushes/pops appropriately, producing a fully precedence-and-parenthesis-resolved postfix token list in one linear pass. Then evaluate that postfix list in a second linear pass using a simple value stack, pushing operands and, on each operator, popping two values, applying the operator, and pushing the result. Splitting parsing from evaluation into two clean linear passes is far cheaper than the brute force's repeated string rewriting. Time: O(n) Space: O(n)

1. Use TWO stacks simultaneously: one for numbers, one for operators. 2. Before pushing a new operator, resolve (pop and apply) every operator already on the stack that has EQUAL OR HIGHER precedence than the new one. 3. An open parenthesis acts as a BARRIER on the operator stack - never resolve past it until its matching close parenthesis forces everything inside to collapse first.

Time: O(n) - one single pass through the expression's characters/tokens. Space: O(n) in the worst case, for the two stacks (a deeply nested expression could require many operators/numbers waiting simultaneously).

Deeply nested parentheses; multi-digit numbers; division truncating toward zero when a subtraction produces a negative intermediate value; expression length up to 10^5 for performance.

Be ready to carefully handle MULTI-DIGIT numbers (scanning all consecutive digits as one token before pushing) - a common bug is treating each digit as a separate token, breaking multi-digit numbers entirely.