> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/my-algorithm-summary/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/my-algorithm-summary/data-structure/stack/224-basic-calculator.md).

# 224 Basic Calculator

## 224. [Basic Calculator](https://leetcode.com/problems/basic-calculator/description/)

## 1. Question

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open`(`and closing parentheses`)`, the plus`+`or minus sign`-`, **non-negative** integers and empty spaces.

You may assume that the given expression is always valid.

Some examples:

```
"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23
```

## 2. Implementation

思路：这题输入的符号只有括号，加号，减号和数字，因为有括号，所以要运算优先级，括号里的表达式是一个整体，所以适合用stack做，但要注意的是这里的stack存的是符号(1 或者 -1)。需要考虑的cases:

(1) 可能会连续得到的字符都是数字，所以我们通过num得到最后的数字

(2) 如果当前的字符是 '+', '-'， sign要根据当前的字符更新，并将num变为0

(3) 如果当前字符是'(', 将sign压栈

(4) 如果当前字符是')', 将当前sign出栈

```java
class Solution {
    public int calculate(String s) {
        int res = 0;
        int num = 0, sign = 1;

        Stack<Integer> stack = new Stack<>();
        stack.push(sign);

        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                num = 10 * num + (c - '0');
            }
            else if (c == '+' || c == '-') {
                res += sign * num;
                sign = stack.peek() * (c == '+' ? 1 : -1);
                num = 0;
            }
            else if (c == '(') {
                stack.push(sign);
            }
            else if (c == ')') {
                stack.pop();
            }
        }
        res += sign * num;
        return res;
    }
}
```

## 3. Time & Space Complexity

时间和空间复杂度O(n)