力扣—— 224. 基本计算器（困难）_力扣 基本计算器

题目描述

给你一个字符串表达式s，请你实现一个基本的计算器来返回它的值。注意不允许使用任何将字符串作为数学表达式计算的内置函数，比如：eval()。
示例一：
输入：s=“1+1”
输出：2
示例二：
输入：s=" 2-1 + 2"
输出：3
示例三：
输入：s="(1+(4+5+2)-3)+(6+8)"
输出：23

题目分析

涉及到优先级问题，准备用栈做。需要解决 ：什么时候可以计算？什么时候需要等待？即需要我们设置一个标志位来记录计算的状态（compute_flag）。
计算流程：未遇到左括号可先行计算（compute_flag=1），遇到左括号停止计算（compute_flag=0）,等待右括号出现则继续计算（compute_flag=1）。
数据提取：需将字符串中的表达式进行分解，我们将数字与运算符单独存放在各自的栈中（number_stack与operation_stack）。当数字栈中存储够两个数字且操作符栈中存在操作符，则将这两个数字与运算符弹出栈进行计算，将计算后的值重新push进栈顶。若栈内元素不够计算，则往栈内push新的值。此外，遇到“（”运算符则停止计算继续push，遇到“）”运算符继续计算。

以1+121-（14+（5-6））为例：

字符串的处理：
主要存在两种状态，一种是数值，一种是运算符。
遇到数值，则进行数值拼接，如123，需要将每次取到的位上的值进行处理最终拼接成int型123———（（（‘1’-‘0’）*10）+（‘2’-‘0’））*10+（‘3’-‘0’））。
遇到空值需跳过，需要注意首位为“-”的情况！若第一个为负数，需先将数字栈补充0。

c++代码

#include <stack>
#include <string>
class Solution {
public:
    //具体的计算函数
    void compute(std::stack<int>& number_stack, std::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(num2 + num1);
        }
        else if (operation_stack.top() == '-') {
            number_stack.push(num1 - num2);
        }
        operation_stack.pop();
    }
    //如何再合适的时候调用计算函数
    int calculate(std::string s) {
        //不同的状态代表不同的操作
        static const int STATE_BEGIN = 0;
        static const int NUMBER_STATE = 1;
        static const int OPERATION_STATE = 2;
        //设置两个栈用于存放数字与运算符
        std::stack<int> number_stack;
        std::stack<char> operation_stack;
        //设置初始变量
        int number = 0; //用于计算字符串中数值
        int STATE = STATE_BEGIN; //初始状态
        int compuate_flag = 0; //计算标记位 0不计算  1计算 
        for (int i = 0; i < s.length(); i++) {
            //考虑开头是负数的情况
            if (i == 0) {
                if (s[i] == '-') {
                    number_stack.push(0);
                    operation_stack.push(s[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') {
                    //下面操作就是如果只有各位数字。将个位数字变为int型，如果有别的位数则下一次进入变为对应的整数型数值
                    //10*number为上一次的位数值（int）,s[i]-'0'为本次位数(int)
                    int a = s[i] - '0';
                    number = 10 * number + a;
                }
                //如果这个数的所有位数都遍历完，则把它push到number_stack
                else {
                    number_stack.push(number);
                    //判断是否能进行一次计算
                    if (compuate_flag == 1) {
                        compute(number_stack, operation_stack);
                    }
                    //重置number
                    number = 0;
                    //序号归位
                    i--;
                    //开始进行运算符操作
                    STATE = OPERATION_STATE;
                }
                break;
            case OPERATION_STATE:
                if (s[i] == '+' || s[i] == '-') {
                    operation_stack.push(s[i]);
                    compuate_flag = 1;
                }
                // ( 不计算，继续往number_stack里面push新的数字
                else if (s[i] == '(') {
                    STATE = NUMBER_STATE;
                    compuate_flag = 0;
                }
                else if (s[i] >= '0' && s[i] <= '9') {
                    STATE = NUMBER_STATE;
                    i--;
                }
                else if (s[i] == ')') {
                    compute(number_stack, operation_stack);
                }
                break;
            }
        }
        if (number != 0) {
            number_stack.push(number);
            compute(number_stack, operation_stack);
        }
        if (number == 0 && number_stack.empty()) {
            return 0;
        }
        return number_stack.top();
    }
};
//测试
int main() {
    std::string s1 = "2+1";
    std::string s2 = "-1+1";
    std::string s3 = "-122+(2-(2+3))";
    Solution solve;
    printf("%d\n", solve.calculate(s1));
    printf("%d\n", solve.calculate(s2));
    printf("%d\n", solve.calculate(s3));
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118