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

Basic Calculator

Master this topic with zero to advance depth.

Basic Calculator

Implement a basic calculator to evaluate a simple expression string containing (, ), +, -, non-negative integers and empty spaces.

Visual Representation

s = " 1 + (4 + 5 - 2) - 3 " 1. '1': res = 1, sign = + 2. '+': Push current res (1) and sign (+) to stack. 3. '(': Start new group. 4. Groups: (4 + 5 - 2) = 7 5. Pop: 1 + (+)7 = 8 6. '-': res = 8, sign = - 7. '3': res = 8 - 3 = 5
Hard

Examples

Input: s = " 1 + (4 + 5 - 2) - 3 "
Output: 5
Approach 1

Level III: Optimal (Iterative with Stack)

Intuition

Process the string character by character. Use a stack to handle parentheses by saving the current result and sign before entering a new group. For + and -, apply them to the running total. For (, push the state; for ), pop and combine.

⏱ O(N)💾 O(N)

Detailed Dry Run

CharRunning TotalSignStack
'1'11[]
'+'11[]
'('01[(1, 1)]
'4'41[(1, 1)]
java
import java.util.Stack;

public class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        int result = 0, number = 0, sign = 1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                number = 10 * number + (c - '0');
            } else if (c == '+') {
                result += sign * number;
                number = 0; sign = 1;
            } else if (c == '-') {
                result += sign * number;
                number = 0; sign = -1;
            } else if (c == '(') {
                stack.push(result);
                stack.push(sign);
                result = 0; sign = 1;
            } else if (c == ')') {
                result += sign * number;
                number = 0;
                result *= stack.pop();    // sign
                result += stack.pop();    // result before (
            }
        }
        if (number != 0) result += sign * number;
        return result;
    }
}

⚠️ Common Pitfalls & Tips

Ensure the last number is added. Be careful with large results (use long long in C++). Handle nested parentheses correctly by pushing both result and sign.

← Previous QuestionRemove Duplicate Letters
Next Question →Basic Calculator III