224. 基本计算器

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格。

Solution：

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
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(num1 + num2);
        }else if(operation_stack.top() == '-'){
            number_stack.push(num1 - num2);
        }
        operation_stack.pop();
    }
    int calculate(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;
        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(compuate_flag == 1){
                            compute(number_stack,operation_stack);
                        }
                        number = 0;
                        i--;
                        STATE = OPERATION_STATE;
                    }
                    break;
                case OPERATION_STATE:
                    if(s[i] == '+' || s[i] == '-'){
                        operation_stack.push(s[i]);
                        compuate_flag = 1;
                    }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();
    }
};

首先，数据用两个栈来存储。一个存数字，一个存操作符。

其次，建立一个状态机，来描述指针的走向状态。根据状态来做相应的操作。

加减状态机

刚开始有一个开始状态。检测下一个字符是数字还是字母。然后转换为相应的状态。

我们先讨论数字与操作符的存储时机：

  • 当指针指向数字时，先将数字暂存起来，继续检查下一位置，还是数字，继续与暂存的数字融合。当指针指向的不是数字时，这时就需要把这个数字存起来。
  • 字符的存储时机就为该位置为+、-时进行存储。

接下来讨论计算的时机。

首先是检测操作符，如果操作符后面是数字，则在该数字进行存储完成之后立马进行计算。

如果操作符之后是” ( “ 就要等下一个相应的” ) “出现。之后再进行计算。

所以设置一个计算标志。如果检测到操作符，把计算标志置为可计算，接着继续下一位的检测，如果是数字，就在存储后进行计算。如果是” ( “，就需要取消计算标志。

一定要注意退格操作！！！

退格发生在下一位置不再是数字或者在操作符之后的检测是不是数字的时候。

最后就是将描述翻译成代码的工作了。

这里注意，在表达式的最后通常是数字，这时也需要将数字存储起来再进行一次运算。

如果表达式正确，存储数字的栈的长度一定是1，直接返回栈顶。