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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/stack/nested/basic-calculator.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.