Course4all
Join us on telegram
Home/dsa/Stack/Basic Calculator III

Basic Calculator III

Master this topic with zero to advance depth.

Basic Calculator III

Evaluate an expression string containing (, ), +, -, *, /, non-negative integers and spaces. This is the ultimate calculator problem.

Visual Representation

s = "2*(5+5*2)/3+(6/2+8)" 1. Handle parentheses recursively or using a stack stack. 2. Within each group, apply multiply/divide first, then add/subtract. 3. Result: 2*(15)/3 + (11) = 10 + 11 = 21
Hard

Examples

Input: s = "2*(5+5*2)/3+(6/2+8)"
Output: 21
Approach 1

Level III: Optimal (Recursion with Deque/Index)

Intuition

This problem combines Basic Calculator I and II. The most natural solution uses recursion to handle parentheses: every time we see (, we recurse; every time we see ), we return the result of the current sub-expression. Within each level, we use the standard 'accumulator' logic for +, -, *, /.

⏱ O(N)💾 O(N)
java
import java.util.*;

public class Solution {
    public int calculate(String s) {
        Queue<Character> tokens = new LinkedList<>();
        for (char c : s.toCharArray()) if (c != ' ') tokens.add(c);
        tokens.add('+'); // Sentinel
        return helper(tokens);
    }

    private int helper(Queue<Character> q) {
        Stack<Integer> stack = new Stack<>();
        int num = 0;
        char sign = '+';
        while (!q.isEmpty()) {
            char c = q.poll();
            if (Character.isDigit(c)) num = num * 10 + (c - '0');
            else if (c == '(') num = helper(q);
            else {
                if (sign == '+') stack.push(num);
                if (sign == '-') stack.push(-num);
                if (sign == '*') stack.push(stack.pop() * num);
                if (sign == '/') stack.push(stack.pop() / num);
                sign = c;
                num = 0;
                if (c == ')') break;
            }
        }
        int res = 0;
        for (int i : stack) res += i;
        return res;
    }
}

⚠️ Common Pitfalls & Tips

Sentinel + at the end makes the loop logic cleaner for the last number. Be careful with division truncation in Python.

← Previous QuestionBasic Calculator
Next Question →Expression Add Operators