227. Basic Calculator II

发表于 | 分类于 | 浏览 次

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces ``. The integer division should truncate toward zero.

Example 1:

1
2
Input: "3+2*2"
Output: 7

Example 2:

1
2
Input: " 3/2 "
Output: 1

Example 3:

1
2
Input: " 3+5 / 2 "
Output: 5

Note:

  • You may assume that the given expression is always valid.
  • Do not use the eval built-in library function.

解法1：

使用两个栈，一个栈用来装操作数，另一个用来装操作符。通过后缀表达式的形式来计算。

AC代码

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
class Solution {
public:
    int calculate(string s) {
        if(s.empty()){
            return 0;
        }
        stack<int> nums;
        stack<char> ops;
        bool isNum = true;
        int sum = 0;
        for(int i=0;i<s.size();++i){
            if(s[i] == ' '){
                 continue;
             }
            if(s[i] == '+' || s[i] == '-' || s[i] =='*' || s[i] =='/'){
                if(ops.empty() || isPrefered(s[i], ops.top())){
                    nums.push(sum);
                }else{
                    while(!ops.empty() &&  !isPrefered(s[i], ops.top())){
                        sum = operate(nums.top(), sum, ops.top());
                        ops.pop();
                        nums.pop();
                    } 
                    nums.push(sum);
                }
                ops.push(s[i]);
                sum = 0;        
            }else{
                sum = sum * 10 + (s[i] - '0');
            }
        }
        nums.push(sum);
        while(nums.size() > 1){
            int second = nums.top();
            nums.pop();
            int first = nums.top();
            nums.pop();
            int res = operate(first, second, ops.top());
            ops.pop();
            nums.push(res);
        }
        return nums.top();
    }
    int  operate(int first, int second, char op){
        int res = 0;
        switch(op){
            case '+': res = first + second;
                break;
            case '-':  res = first - second;
                break;
            case '*': res = first *second;
                break;
            case  '/': 
                if(second != 0){
                    res = first / second;
                }else{
                    throw "divided by zero";
                }
                break;
        }
        return res;
    }
    bool isPrefered(char cur, char before){
        if((cur == '*' || cur =='/') && (before =='+' || before == '-')){
            return true;    // 继续入栈
        }
        return false;
    }
};

相关题目

参考文献

[1]后缀表达式：https://www.cnblogs.com/chensongxian/p/7059802.html