> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/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/algorithm-practice/leetcode/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做

```java
class Solution {
    public int calculate(String s) {
        s.replace(" ", "");
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        int i = 0;
        int sign = 1;

        while (i < s.length()) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int val = 0;

                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    val = 10 * val + s.charAt(i) - '0';
                    ++i;
                }
                --i;
                res += sign * val * stack.peek();
            }
            else if (c == '(') {
                stack.push(sign * stack.peek());
                sign = 1;
            }
            else if (c == ')') {
                stack.pop();
            }
            else {
                sign = c == '-' ? -1 : 1;
            }
            ++i;
        }
        return res;
    }
}
```

## 3. Time & Space Complexity

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