Back to DSA

Basic Calculator

hard
Acceptance: 38%
StackMathString

Write a calculator that evaluates a string expression containing non-negative integers, the operators + and -, parentheses for grouping, and optional spaces. The expression is guaranteed to be well-formed. Return the computed integer result.

Examples

Example 1:
Input:s = "5 - 3 + 2"
Output:4
Example 2:
Input:s = "(2+(3+4+1)-2)+(7+9)"
Output:24

Hints

Related Problems

Min StackmediumValid ParentheseseasyEvaluate Reverse Polish NotationmediumDaily TemperaturesmediumNext Greater Element Ieasy
00:00
import java.util.*;

class Solution {
    public int calculate(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        int result = 0, num = 0, sign = 1;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '+') {
                result += sign * num; num = 0; sign = 1;
            } else if (c == '-') {
                result += sign * num; num = 0; sign = -1;
            } else if (c == '(') {
                stack.push(result); stack.push(sign);
                result = 0; sign = 1;
            } else if (c == ')') {
                result += sign * num; num = 0;
                result *= stack.pop(); result += stack.pop();
            }
        }
        return result + sign * num;
    }
}
Time complexityO(n)
Space complexityO(n)