LeetCode 227 Basic Calculator II

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

概述

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

解法

有两个优先级需要保证:

  1. + 与 - 低于 * 和 /
  2. 同级优先级,前面的先执行(实现的时候反向遍历就好了)
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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/