Problem statement
Evaluate an arithmetic expression containing integer literals, binary +,-,*,/, balanced parentheses and spaces. Return the integer result without using an expression-evaluation library.
Parentheses decide grouping. Multiplication and division bind more tightly than addition and subtraction. Operators of the same precedence are evaluated left to right. Integer division truncates toward zero: (0-3)/2 is -1, not -2.
Explicit implementation contract
The LeetCode 772 page is Premium, and the supplied practice page was not readable during this review. We do not invent hidden length limits. This lesson states its assumptions explicitly:
- The input is a valid expression made from nonnegative decimal literals and binary operators. Subexpressions may evaluate to negative values.
- Literals and mathematical intermediate values fit signed 32-bit integers; code uses long internally and range-checks the final int result.
- Divisors evaluate to nonzero, and parentheses are balanced.
- Unary signs, decimals, exponentiation and implicit multiplication such as
2(3+4)are outside this grammar.
Null, empty and malformed inputs are not valid examples. The code rejects several such cases for clarity, but it is not advertised as a production expression-language validator. If your judge supports unary operators, that is a different factor grammar and must be added deliberately.
Constraints & requirements
- CONTRACT
- Explicit teaching contract: literals and intermediate mathematical values fit signed 32-bit integers; divisors evaluate to nonzero. Unary signs, exponentiation, decimals and implicit multiplication are outside this grammar. LeetCode 772 is Premium; no hidden length/numeric bounds are claimed. Null, empty or malformed inputs are not valid judge cases.
Examples 3 test cases
Example 1 Case 1
- Input
s="2*(3+4)-5/2"- Output
12
Parentheses give 7, the first term becomes 14, integer 5/2 is 2, then 14-2=12.
Example 2 Case 2
- Input
s="2*(5+5*2)/3+(6/2+8)"- Output
21
The two parenthesized expressions evaluate to 15 and 11; 2×15/3+11=21.
Example 3 Case 3
- Input
s="(0-3)/2"- Output
-1
The numerator is -3; Java integer division truncates -1.5 toward zero, not down to -2.
Hints Optional
01Hint 1
Separate three jobs: addition/subtraction, multiplication/division, and one number or parenthesized group.
02Hint 2
Let all parser methods share a cursor that only moves forward.
03Hint 3
A child expression stops before ); the factor that opened ( consumes that matching ). Never search and copy the same substrings repeatedly.
How to think before coding
Do not begin with one giant loop containing every operator rule. First separate the responsibilities:
- An expression combines terms with addition/subtraction.
- A term combines factors with multiplication/division.
- A factor is one number or one parenthesized expression.
When an expression asks for its first term, that term finishes its entire multiplication/division chain before returning. Precedence therefore comes from who calls whom, not from fixing an already-wrong total later.
A parenthesis creates another expression with the same rules. This self-similarity is the recursion clue. Unlike backtracking, parsing does not try multiple guesses or restore old prefixes: it consumes the supplied tokens in one valid interpretation.
Brute force: repeatedly simplify substrings
A workable baseline finds an innermost parenthesized group, evaluates its flat contents with correct precedence, and replaces that substring with its value. Repeat until the outer expression is flat, then evaluate it.
The flat evaluator must still handle multiplication/division before addition/subtraction. Replacing parentheses does not justify calculating everything blindly from left to right.
Repeated searches and immutable-string copying can revisit length-O(L) text for O(L) nested groups, producing O(L²) worst-case time. Negative replacement values must remain numeric tokens; naively producing text such as 2*-3 without handling signed tokens introduces a second bug.
We can avoid both repeated slicing and replacement by keeping one forward-moving cursor into the original string.
Intuition: three grammar levels, one cursor
| Method | Responsibility | Where it stops |
|---|---|---|
readExpression |
Combine complete terms using + and - |
Closing ) or end |
readTerm |
Combine complete factors using * and / |
A lower-precedence operator, ) or end |
readFactor |
Read all digits of one literal, or evaluate (expression) |
Just after that factor |
For 2*(3+4)-5/2, the outer expression does not subtract 5 immediately after seeing the minus. It first asks a term to evaluate the whole 5/2, receives 2, and then performs 14-2.
Who consumes the closing parenthesis?
The factor that consumed ( calls a child expression. The child stops before the matching ). That factor then consumes it and returns the group’s value.
If both methods consume ), the cursor skips the following token. If neither consumes it, the outer parser cannot progress correctly. Give each delimiter one clear owner.
Why is the cursor shared but value local?
All parser methods must agree on the next unread character. A child therefore advances the same index. But each frame has its own local arithmetic value: the inner 3+4 must not overwrite the waiting outer term’s 2.
Returning from the child transfers a number, not a changed copy of the whole parent state. There is no need to move the cursor backward.
Why division uses integers
Java’s integer-division rule truncates the quotient toward zero. Integer operands therefore implement the required rule directly. Floating-point division followed by floor would give the wrong result for negative quotients.
Algorithm
- Create a fresh parser object and shared cursor for every public invocation.
readExpressionreads a term, then consumes each following+/-and its complete right term.readTermreads a factor, then consumes each following*/and its complete right factor.readFactorreads an integer, or consumes(, callsreadExpression, and consumes its matching).- Skip spaces between tokens. Consume all adjacent digits inside a literal.
- At the public boundary, require complete input consumption and return the int result.
Both operator loops evaluate left to right. For example, 8/3/2 is (8/3)/2=1, not 8/(3/2)=8.
Java solution
The nested parser class separates state from the public API. The complete main method exercises precedence, nesting and a negative intermediate result. There is no global cursor left over from a previous call.
import java.util.*;
class Solution {
public static int calculate(String expression) {
if (expression == null) throw new IllegalArgumentException("Expression is required");
CalculatorParser parser = new CalculatorParser(expression); // Fresh cursor for every call.
long answer = parser.readExpression(); // Read the complete lowest-precedence level.
if (parser.current() != '\0') throw new IllegalArgumentException("Unexpected trailing token");
return Math.toIntExact(answer); // Teaching contract: the final answer must fit a Java int.
}
private static class CalculatorParser {
private final String input;
private int index = 0; // One shared cursor: a child leaves it just after its own expression.
CalculatorParser(String input) { this.input = input; }
private char current() {
while (index < input.length() && input.charAt(index) == ' ') index++; // Spaces separate tokens.
return index < input.length() ? input.charAt(index) : '\0'; // Sentinel is not a real operator.
}
private long readExpression() {
long value = readTerm(); // A term finishes its * and / before we use + or -.
while (current() == '+' || current() == '-') { // Stop at ) or end without consuming it.
char operator = input.charAt(index++); // Consume the binary operator exactly once.
long right = readTerm(); // Consume its entire higher-precedence right operand.
value = operator == '+' ? value + right : value - right; // Left-associative + and -.
}
return value; // Caller decides whether this stopped at a closing parenthesis.
}
private long readTerm() {
long value = readFactor(); // A number or a whole parenthesized expression is one factor.
while (current() == '*' || current() == '/') {
char operator = input.charAt(index++);
long right = readFactor(); // Parentheses must finish before this operation.
value = operator == '*' ? value * right : value / right; // Java integer division truncates toward 0.
}
return value; // Consecutive * and / were evaluated left to right.
}
private long readFactor() {
if (current() == '(') { // A child expression owns everything inside these parentheses.
index++; // Consume the opening parenthesis before descending.
long value = readExpression(); // Parent waits; the shared cursor keeps advancing.
if (current() != ')') throw new IllegalArgumentException("Missing closing parenthesis");
index++; // Factor, not the child expression, consumes its matching closing parenthesis.
return value; // The entire parenthesized result acts like one number.
}
char first = current();
if (first < '0' || first > '9') throw new IllegalArgumentException("Expected a number or (");
long value = 0;
while (index < input.length() && input.charAt(index) >= '0' && input.charAt(index) <= '9') {
value = value * 10 + input.charAt(index++) - '0'; // Consume all digits of this literal.
}
return value; // Unary signs are not part of this stated binary-operator grammar.
}
}
public static void main(String[] args) {
System.out.println(calculate("2*(3+4)-5/2")); // 12
System.out.println(calculate("2*(5+5*2)/3+(6/2+8)")); // 21
System.out.println(calculate("(0-3)/2")); // -1
}
}The invocation prints 12, 21 and -1. Ordinary valid inputs are the focus; deep untrusted nesting may exceed Java’s call-stack capacity, so an explicit-stack parser is a useful alternative for a different operational requirement.
Illustrated dry run
Use 2*(3+4)-5/2. Draw the shared cursor once and give every waiting frame its own local value. The image tracks the parentheses’ owner as well as each arithmetic operation.

Read the text transcript
Follow the Java, step by step
Example: s = "2*(3+4)-5/2"
What to track: One shared zero-based cursor, but a separate local value for each parser frame. E=expression (+/-), T=term (*/); F=factor (number/group). This covers every operation; routine wrapper returns are grouped.
-
Read the first factor
Java operationlong value = readFactor();Stateouter T reads 2; cursor=1 at *; outer T.value=2The factor consumes the full number. The surrounding expression waits until this term has finished its multiplication.
-
Enter the parenthesized expression
Java operationlong value = readExpression();Stateouter T consumed *; F consumed ( at index 2; cursor=3 at 3; outer T waits with left=2This child is a new expression frame, not a reset of the cursor or a copy of the substring.
-
Read 3, then handle +
Java operationlong right = readTerm();Stateinner E.value=3; + consumed at index 4; right T reads 4; cursor=6 at )The right term stops at ). Neither this term nor the inner expression consumes the closing token.
-
Return the complete inner result
Java operationvalue = operator == '+' ? value + right : value - right;Stateinner E: 3+4=7; cursor=6; its F caller consumes ) and advances cursor=7 at -Only the factor that opened ( owns the matching closing ). It returns 7 as one factor to the waiting outer term.
-
Complete the first outer term
Java operationvalue = operator == '*' ? value * right : value / right;Stateouter T: 2×7=14; cursor=7 at -; outer E receives 14The minus belongs to the expression level, so the term leaves it for its caller.
-
Read the subtraction’s whole right term
Java operationlong right = readTerm();Stateouter E consumes - at index 7; right T reads 5; cursor=9 at /Do not subtract 5 yet. Its multiplication/division chain must finish first.
-
Finish integer division
Java operationvalue = operator == '*' ? value * right : value / right;Stateright T consumes / and reads 2; cursor=11 at end; T returns 5/2=2These are integer values. Java drops the fractional part toward zero; no floating-point rounding is used.
-
Subtract and return
Java operationvalue = operator == '+' ? value + right : value - right;Stateouter E: 14−2=12; cursor=11; public calculate returns 12All input was consumed. The final integer-range check happens only after the full expression is evaluated.
Final result: 12; cursor=11 (end), after 2×7−(5/2)=14−2.
To debug by hand, pause just before each method return. Ask: “Which token did I leave unread, and which caller owns it?” This catches many errors that a final answer alone does not reveal.
Why it works
Factors: Reading all digits returns exactly one literal. Reading a parenthesized child returns the value of exactly that group and advances past its closing delimiter.
Terms: Assuming factors are correct, the multiplication/division loop combines them left to right. It stops before lower-precedence operators, so a caller receives one complete term.
Expressions: Assuming terms are correct, the addition/subtraction loop combines complete terms left to right. This preserves precedence without ever rearranging the input.
Nested groups and termination: Every recursive group consumes its opening delimiter before descending, and every token-processing loop advances the cursor. Balanced valid input therefore finishes each child and eventually the outer expression.
Complexity and alternative approaches
Let L be expression length and h the maximum parenthesis nesting depth.
| Approach | Time | Extra space | Tradeoff |
|---|---|---|---|
| Repeated innermost-substring replacement | O(L²) worst case | O(L) peak working storage | Easy baseline, but rescans and copies |
| Shared-cursor recursive descent | O(L) | O(h+1), O(L) worst case | Grammar mirrors precedence; no substring copies |
| Explicit value/operator stacks | O(L) | O(L) worst case | Avoids recursive call-stack limits; must implement precedence reductions |
The cursor never moves backward. A character may be inspected at a few grammar boundaries, but only a constant number of times; skipped spaces are consumed once. The returned result is one integer, so output space is O(1).
For a flat expression, recursive-descent depth is constant even if there are many operators. Long multiplication chains use a loop, not a new recursive frame per operator.
Common mistakes
- Treating every operator as equal precedence.
- Evaluating
8/3/2right to left. - Resetting the cursor for a child or retaining it between public calls.
- Letting both the child expression and parent factor consume
). - Parsing only one digit of a multi-digit literal.
- Subtracting 5 before evaluating the full right term
5/2. - Using floor for negative division or evaluating through floating point.
- Claiming this binary-operator grammar already supports
-2,2*-3or unary plus. - Applying a stack-based space claim to the repeated-copy baseline, or claiming O(1) for arbitrarily deep nesting.