solution.md

# 基本计算器

<p>给你一个字符串表达式 <code>s</code> ，请你实现一个基本计算器来计算并返回它的值。</p>

<p> </p>

<p><strong>示例 1：</strong></p>

<pre>
<strong>输入：</strong>s = "1 + 1"
<strong>输出：</strong>2
</pre>

<p><strong>示例 2：</strong></p>

<pre>
<strong>输入：</strong>s = " 2-1 + 2 "
<strong>输出：</strong>3
</pre>

<p><strong>示例 3：</strong></p>

<pre>
<strong>输入：</strong>s = "(1+(4+5+2)-3)+(6+8)"
<strong>输出：</strong>23
</pre>

<p> </p>

<p><strong>提示：</strong></p>

<ul>
	<li><code>1 <= s.length <= 3 * 10<sup>5</sup></code></li>
	<li><code>s</code> 由数字、<code>'+'</code>、<code>'-'</code>、<code>'('</code>、<code>')'</code>、和 <code>' '</code> 组成</li>
	<li><code>s</code> 表示一个有效的表达式</li>
</ul>

<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
```

### after

```cpp
int main()
{
    Solution sol;
    int res;
    string s1 = "(1+(4+5+2)-3)+(6+8)";
    res = sol.calculate(s1);
    cout << res;
    return 0;
}
```

## 答案

```cpp
class Solution
{
public:
    int calculate(string s)
    {
        stack<string> expr, nums, ops;
        int cur = 0, len = s.size();
        string tmp = "";
        while (cur < len)
        {

            switch (s[cur])
            {
            case ' ':
                break;
            case '+':
            case '-':
            case '(':
                if (tmp != "")
                {
                    expr.push(tmp);
                    tmp = "";
                }
                expr.push(tmp + s[cur]);
                break;
            case ')':
            {
                if (tmp != "")
                {
                    expr.push(tmp);
                    tmp = "";
                }
                int caled = calculate(expr);
                expr.push(intToStr(caled));
                break;
            }
            default:
                tmp += s[cur];
                break;
            }
            ++cur;
        }
        if (tmp != "")
            expr.push(tmp);
        return calculate(expr);
    }

private:
    int calculate(stack<string> &s)
    {
        stack<int> nums;
        stack<char> ops;
        string top;

        while (!s.empty() && (top = s.top()) != "(")
        {
            if (top == "+" || top == "-")
                ops.push(top[0]);
            else
                nums.push(strToInt(top));
            s.pop();
        }
        if (!s.empty())
            s.pop();

        int ans = nums.top(), num;
        nums.pop();
        while (!ops.empty())
        {
            num = nums.top();
            nums.pop();
            if (ops.top() == '+')
                ans += num;
            else
                ans -= num;
        }
        return ans;
    }

    int strToInt(string s)
    {
        int ans = 0, len = s.size();
        if (len == 0)
            return 0;
        int symbol = s[0] == '-' ? -1 : 1;
        for (int i = s[0] == '+' || s[0] == '-' ? 1 : 0; i < len; ++i)
        {
            ans *= 10;
            ans += s[i] - '0';
        }
        return ans * symbol;
    }

    string intToStr(int num)
    {
        if (num == 0)
            return "0";
        int symbol = num >= 0 ? 1 : -1;
        string s = "";
        num *= symbol;
        while (num)
        {
            s = (char)(num % 10 + '0') + s;
            num /= 10;
        }
        if (symbol == -1)
            s = "-" + s;
        return s;
    }
};
```
## 选项


### A

```cpp
class Solution
{
public:
    int calculate(string s)
    {
        stack<long> conclude;
        stack<char> fuhao;
        int i = 0, len = s.length();
        while (i < len)
        {
            if (s[i] == ' ')
                i++;
            else if (s[i] == '(')
            {
                fuhao.push('(');
                i++;
            }
            else if (s[i] == ')')
            {
                if (fuhao.top() != '(')
                {
                    long x = conclude.top();
                    conclude.pop();
                    long y = conclude.top();
                    conclude.pop();
                    if (fuhao.top() == '+')
                        conclude.push(y + x);
                    else
                        conclude.push(y - x);
                    fuhao.pop();
                }
                fuhao.pop();
                i++;
            }
            else if (s[i] == '+' || s[i] == '-')
            {
                if (!fuhao.empty() && fuhao.top() != '(')
                {
                    long x = conclude.top();
                    conclude.pop();
                    long y = conclude.top();
                    conclude.pop();
                    if (fuhao.top() == '+')
                        conclude.push(y + x);
                    else
                        conclude.push(y - x);
                    fuhao.pop();
                }
                fuhao.push(s[i]);
                i++;
            }
            else
            {
                long x = s[i] - '0';
                i++;
                while (i < len && s[i] <= '9' && s[i] >= '0')
                {
                    x = x * 10 + (s[i] - '0');
                    i++;
                }
                conclude.push(x);
            }
        }
        if (!fuhao.empty())
        {
            long x = conclude.top();
            conclude.pop();
            long y = conclude.top();
            conclude.pop();
            if (fuhao.top() == '+')
                conclude.push(y + x);
            else
                conclude.push(y - x);
            fuhao.pop();
        }
        return conclude.top();
    }
};
```

### B

```cpp
class Solution
{
public:
    int calculate(string s)
    {
        static const int STATE_BEGIN = 0;
        static const int NUMBER_STATE = 1;
        static const int OPERATION_STATE = 2;
        long number = 0;
        int STATE = STATE_BEGIN;
        int computer_flag = 0;
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] == ' ')
            {
                continue;
            }
            switch (STATE)
            {
            case STATE_BEGIN:
                if (s[i] >= '0' && s[i] <= '9')
                {
                    STATE = NUMBER_STATE;
                }
                else
                {
                    STATE = OPERATION_STATE;
                }
                i--;
                break;
            case NUMBER_STATE:
                if (s[i] >= '0' && s[i] <= '9')
                {
                    number = number * 10 + s[i] - '0';
                }
                else
                {
                    number_stack.push(number);
                    if (computer_flag == 1)
                    {
                        computer(number_stack, operation_stack);
                    }
                    number = 0;
                    i--;
                    STATE = OPERATION_STATE;
                }
                break;
            case OPERATION_STATE:
                if (s[i] == '+' || s[i] == '-')
                {
                    operation_stack.push(s[i]);
                    computer_flag = 1;
                }
                else if (s[i] == '(')
                {
                    computer_flag = 0;
                }
                else if (s[i] >= '0' && s[i] <= '9')
                {
                    STATE = NUMBER_STATE;
                    i--;
                }
                else if (s[i] == ')')
                {
                    computer(number_stack, operation_stack);
                }
                break;
            }
        }
        if (number != 0)
        {
            number_stack.push(number);
            computer(number_stack, operation_stack);
        }
        if (number == 0 && number_stack.empty())
        {
            return 0;
        }
        return number_stack.top();
    }
    void computer(stack<long> &number_stack, stack<char> &operation_stack)
    {
        if (number_stack.size() < 2)
        {
            return;
        }
        int num2 = number_stack.top();
        number_stack.pop();
        int num1 = number_stack.top();
        number_stack.pop();
        if (operation_stack.top() == '+')
        {
            number_stack.push(num1 + num2);
        }
        else if (operation_stack.top() == '-')
        {
            number_stack.push(num1 - num2);
        }
        operation_stack.pop();
    }

private:
    stack<long> number_stack;
    stack<char> operation_stack;
};
```

### C

```cpp
class Solution
{
public:
    void sum(vector<string> &stk)
    {
        vector<string> temp;
        while (!stk.empty() && stk.back() != "(")
        {
            temp.push_back(stk.back());
            stk.pop_back();
        }
        if (!stk.empty() && stk.back() == "(")
            stk.pop_back();
        if (temp.back() != "-")
            temp.emplace_back("+");
        reverse(temp.begin(), temp.end());

        int ret = 0;
        int n = temp.size();
        for (int i = 0; i < n - 1; i += 2)
        {
            int num = stoi(temp[i + 1]);
            if (temp[i] == "-")
                num *= (-1);
            ret += num;
        }

        stk.push_back(to_string(ret));
    }
    int calculate(string s)
    {
        vector<string> stk;
        int n = s.size();
        int ret = 0;

        string temp;
        for (int i = 0; i < n; ++i)
        {
            if (isdigit(s[i]))
            {
                temp += s[i];
            }
            else if (s[i] == '+' || s[i] == '-')
            {
                if (!temp.empty())
                {
                    stk.push_back(temp);
                    temp.clear();
                }
                temp += s[i];
                stk.push_back(temp);
                temp.clear();
            }
            else if (s[i] == '(')
            {
                temp += s[i];
                stk.push_back(temp);
                temp.clear();
            }
            else if (s[i] == ')')
            {
                stk.push_back(temp);
                temp.clear();
                sum(stk);
            }
        }
        if (!temp.empty())
            stk.push_back(temp);
        sum(stk);
        if (stk.size() == 1)
            ret = stoi(stk[0]);

        return ret;
    }
};
```