Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Basic Calculator III in Java: Parse Precedence and Parentheses

Derive a calculator from grammar levels, with a quadratic baseline, linear recursive descent, commented Java, cursor-by-cursor dry run and integer division rules.

HardRecursion and backtrackingPattern: recursion

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

  1. 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.

  2. 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.

  3. 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.

Solve on LeetCode ↗

Hints Optional

Hints become more specific one step at a time.
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:

  1. An expression combines terms with addition/subtraction.
  2. A term combines factors with multiplication/division.
  3. 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

  1. Create a fresh parser object and shared cursor for every public invocation.
  2. readExpression reads a term, then consumes each following +/- and its complete right term.
  3. readTerm reads a factor, then consumes each following */ and its complete right factor.
  4. readFactor reads an integer, or consumes (, calls readExpression, and consumes its matching ).
  5. Skip spaces between tokens. Consume all adjacent digits inside a literal.
  6. 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.

Java
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.

Numbered illustrated dry run for Basic Calculator III; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
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.

  1. Read the first factor

    Java operationlong value = readFactor();
    Stateouter T reads 2; cursor=1 at *; outer T.value=2

    The factor consumes the full number. The surrounding expression waits until this term has finished its multiplication.

  2. 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=2

    This child is a new expression frame, not a reset of the cursor or a copy of the substring.

  3. 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.

  4. 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.

  5. Complete the first outer term

    Java operationvalue = operator == '*' ? value * right : value / right;
    Stateouter T: 2×7=14; cursor=7 at -; outer E receives 14

    The minus belongs to the expression level, so the term leaves it for its caller.

  6. 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.

  7. Finish integer division

    Java operationvalue = operator == '*' ? value * right : value / right;
    Stateright T consumes / and reads 2; cursor=11 at end; T returns 5/2=2

    These are integer values. Java drops the fractional part toward zero; no floating-point rounding is used.

  8. Subtract and return

    Java operationvalue = operator == '+' ? value + right : value - right;
    Stateouter E: 14−2=12; cursor=11; public calculate returns 12

    All 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/2 right 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*-3 or unary plus.
  • Applying a stack-based space claim to the repeated-copy baseline, or claiming O(1) for arbitrarily deep nesting.

Practice next

Next lessonExpression Add Operators

Back to Recursion and backtracking →