> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/stack/nested/basic-calculator.md).

# Basic Calculator

<https://leetcode.com/problems/basic-calculator/description/>

> 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.

## Thoughts

eval由+-()组成的数学数学表达式。nested括号匹配是stack最常见的应用之一。栈里存(之前计算出的结果并记录(对应的正负号，栈外存当前的结果。遇到)就把s内一个结果pop出并和当前结果合并成新的当前结果。

## Code

```cpp
/*
 * @lc app=leetcode id=224 lang=cpp
 *
 * [224] Basic Calculator
 */
class Solution {
public:
    int calculate(string str) {
        int num = 0, sign = 1, res = 0;
        stack<int> s;
        for (const auto c : str) {
            if (c >= '0' && c <= '9') num = num * 10 + (c - '0');
            else if (c == '+') {
                res += sign * num;
                sign = 1;
                num = 0;
            } else if (c == '-') {
                res += sign * num;
                sign = -1;
                num = 0;
            } else if (c == '(') {
                s.push(res);
                s.push(sign);
                sign = 1;
                num = 0;
                res = 0;
            } else if (c == ')') {
                int psign = s.top(); s.pop();
                int pres = s.top(); s.pop();
                res += sign * num;
                res *= psign;
                res += pres; 
                num = 0;
                sign = 1;
            }
        }
        if (num != 0) res += sign * num;
        return res;
    }
};


```

## Analysis

Errors:

1. 忘了把num, res, sigh等重置
2. 右括号时忘了写res += sign \* num;

时空复杂度都是O(N).