LeetCode 227 Basic Calculator II

    
        标签：
        
            编译原理相关题目
        
            LeetCode
        
    发布于：2022-03-06 10:06:14
    编辑于：2022-03-06 10:06:55
    浏览量：721

概述

https://leetcode.com/problems/basic-calculator-ii/

解法

有两个优先级需要保证：

+ 与 - 低于 * 和 /
同级优先级，前面的先执行（实现的时候反向遍历就好了）

class Solution {
public:
    vector<string> strs;
    int calculate(string s) {
        string t;
        for (auto c : s) {
            if (c == ' ') {
                if (t == "") continue;
                else {
                    strs.push_back(t);
                    t = "";
                }
            } else {
                if (c == '+' || c == '-' || c == '*' || c == '/') {
                    if (t != "") strs.push_back(t);  // 注意这里！
                    strs.push_back(string(1, c));
                    t = "";
                } else {
                    t += c;
                }
            }
        }
        if (t != "") strs.push_back(t);
        // for (auto str : strs) cout << str << " ";
        return helper(0, strs.size()-1);
    }
    
    int helper(int l, int r) {
        // cout << l << " " << r << endl;
        if (l == r) return stoi(strs[l]);
        for (int i = r - 1; i >= l + 1; i --) {
            if (strs[i] == "+") {
                return helper(l, i-1) + helper(i+1, r);
            } else if (strs[i] == "-") {
                return helper(l, i-1) - helper(i+1, r);
            }
        }
        for (int i = r - 1; i >= l + 1; i --) {
            if (strs[i] == "*") {
                return helper(l, i-1) * helper(i+1, r);
            } else if (strs[i] == "/") {
                return helper(l, i-1) / helper(i+1, r);
            }
        }
        return 0;
    }
};

Links: leetcode-227-basic-calculator-ii