基本计算器问题

Leetcode上有几道基本计算器的问题

题目列表

224. 基本计算器

支持加减操作

227. 基本计算器 II

支持加减乘除操作

772. 基本计算器 III

支持加减乘除和括号操作
这个是vip题目，可以在这里牛客或这里lintcode看到替代的题目，是一样的

770. 基本计算器 IV

表达式求值

分析

这里面设计到的一个共同的问题就是计算一个表达式的值的问题，我们可以使用递归或者栈的方式来解决这个问题。实际上递归也是栈的应用，两种方法是一样的。

代码实现

递归

class Solution {
public:
    int parseNum(string& s, int& i) {
        int n = 0;
        while(i < s.length() && isdigit(s[i])) n = s[i++] - '0' + 10 * n;
        return n;
    }

    int parseExpr(string& s, int& i) {
        vector<int> nums;
        char op = '+';
        for (; i < s.length() && op != ')'; i++) {   //右括号可以结束递归
            if (s[i] == ' ') continue;
            int n;
            if(s[i] == '(') n = parseExpr(s, ++i); //左括号开始递归
            else n = parseNum(s, i); //求值
            switch(op) {
                // 加法和减法都放到nums里
                case '+' : nums.push_back(n); break;		//加法
                case '-' : nums.push_back(-n); break;		//减法
                // 乘法和除法可以直接算
                case '*' : nums.back() *= n; break;			//乘法
                case '/' : nums.back() /= n; break;			//除法
            }            
            op = s[i];
        }
        return accumulate(nums.begin(), nums.end(), 0);
    }

    int calculate(string &s) {
        int i = 0;
        return parseExpr(s, i);
    }
};
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

迭代

中缀转后缀

python内置函数