LeetCode 770. Basic Calculator IV题目解析-wowAC

Description

Given an expression such as expression = "e + 8 - a + 5" and an evaluation map such as {"e": 1} (given in terms of evalvars = ["e"] and evalints = [1]), return a list of tokens representing the simplified expression, such as ["-1*a","14"]

  • An expression alternates chunks and symbols, with a space separating each chunk and symbol.

  • A chunk is either an expression in parentheses, a variable, or a non-negative integer.

  • A variable is a string of lowercase letters (not including digits.) Note that variables can be multiple letters, and note that variables never have a leading coefficient or unary operator like "2x" or "-x".

Expressions are evaluated in the usual order: brackets first, then multiplication, then addition and subtraction. For example, expression = "1 + 2 * 3" has an answer of ["7"].

The format of the output is as follows:

  • For each term of free variables with non-zero coefficient, we write the free variables within a term in sorted order lexicographically. For example, we would never write a term like "b*a*c", only "a*b*c".

  • Terms have degree equal to the number of free variables being multiplied, counting multiplicity. (For example, "a*a*b*c" has degree 4.) We write the largest degree terms of our answer first, breaking ties by lexicographic order ignoring the leading coefficient of the term.

  • The leading coefficient of the term is placed directly to the left with an asterisk separating it from the variables (if they exist.)  A leading coefficient of 1 is still printed.

  • An example of a well formatted answer is ["-2*a*a*a", "3*a*a*b", "3*b*b", "4*a", "5*c", "-6"] 

  • Terms (including constant terms) with coefficient 0 are not included.  For example, an expression of "0" has an output of [].

Examples:

input: expression = "e + 8 - a + 5", evalvars = ["e"], evalints = [1]
output: ["-1*a","14"]
input: expression = "e - 8 + temperature - pressure",evalvars = ["e", "temperature"], evalints = [1, 12]
output: ["-1*pressure","5"]
input: expression = "(e + 8) * (e - 8)", evalvars = [], evalints = []
output: ["1*e*e","-64"]
input: expression = "7 - 7", evalvars = [], evalints = []
output: []
input: expression = "a * b * c + b * a * c * 4", evalvars = [], evalints = []
output: ["5*a*b*c"]
input: expression = "((a - b) * (b - c) + (c - a)) * ((a - b) + (b - c) * (c - a))",evalvars = [], evalints = []
output: ["-1*a*a*b*b","2*a*a*b*c","-1*a*a*c*c","1*a*b*b*b","-1*a*b*b*c","-1*a*b*c*c","1*a*c*c*c","-1*b*b*b*c","2*b*b*c*c","-1*b*c*c*c","2*a*a*b","-2*a*a*c","-2*a*b*b","2*a*c*c","1*b*b*b","-1*b*b*c","1*b*c*c","-1*c*c*c","-1*a*a","1*a*b","1*a*c","-1*b*c"]

Note:

  1. expression will have length in range [1, 250].

  2. evalvars, evalints will have equal lengths in range [0, 100].

题目复述

给定一个表达式(包含+ – * ( ) 变量 数字),符号之间用一个空格隔开,变量集合和赋值集合,给出结果。例如expression = "e + 8 – a + 5",evalvars = ["e"] evalints = [1](即e = 1),结果为["-1*a", "14"], 变量只包含小写字母,不会有系数,输出格式如下:

  • 每个因子的包含的变量应该按照字典序排序,比如"b*a*c"只能表示为"a*b*c"

  • 每个因子有一个度,即变量的个数,输出的时候度大的优先,度相同的情况下,按照字典序输出(不包含系数)。

  • 系数总是被输出到最左边,系数1也应该输出

  • 系数为0的项不输出。比如表达式"0"的输出为[]

题目解析

此题是LeetCode 772的加强版,我们依然使用递归下降法来解决这个问题,文法如下:

  1. exp := exp +|- additive | additive

  2. additive := additive * factor | additive

  3. factor := num | (exp) | variable(变量)

我们使用vector<string>类型来表示表达式的结果,该容器中元素之间的关系是相加,比如vector<string> res = ["a", "10"],表示表达式"a+10"。这样只需要在additive函数中处理相乘,在exp函数中处理合并同类项即可。

class Solution {
public:

    string token;
    string str;
    int index;

    vector<string> g_evalvars;
    vector<int> g_evalints;


    //找出下一个符号 + - * ( ) 数字或者变量
    string get_token() {
        while(str[index]==' ') index++;  //去除空格
        string token = "";
        if(index == str.length()) return token;
        //数字
        if(str[index]>='0' && str[index]<='9') {
            while(str[index]>='0' && str[index]<='9') {
                token += str[index];
                index++;
            }
        }else if(str[index]>='a' && str[index]<='z') {  //变量
            while(str[index]>='a' && str[index]<='z') {
                token += str[index];
                index++;
            }
        }else
        switch(str[index]) {
            case '+':
                token += "+";
                index++;
                break;
            case '-':
                token += "-";
                index++;
                break;
            case '*':
                token += "*";
                index++;
                break;
            case '/':
                token += "/";
                index++;
                break;
            case '(':
                token += '(';
                index++;
                break;
            case ')':
                token += ')';
                index++;
                break;
            default:  //不可识别的记号
                break;
        }
        return token;
    }
    //判断是否为num
    bool is_num(string &tk) {
        for(int i=0; i<tk.length(); i++)
            if(tk[i]>='a' && tk[i]<='z') return false;
        return true;
    }
    string int2str(const int int_temp)
    {
        string string_temp;
        stringstream stream;
        stream<<int_temp;
        string_temp=stream.str();   //此处也可以用 stream>>string_temp
        return string_temp;
    }
    //使用c分割字符串s
    void split_string(const string& s, const string& c, vector<string> &v){
        string::size_type pos1, pos2;
        pos2 = s.find(c);
        pos1 = 0;
        while(string::npos != pos2){
            v.push_back(s.substr(pos1, pos2-pos1));

            pos1 = pos2 + c.size();
            pos2 = s.find(c, pos1);
        }
        if(pos1 != s.length())
            v.push_back(s.substr(pos1));
    }
    //分离因子的系数和变量
    void split(const string &fac1, string &num1, string &vars1) {
        int i = 0;
        while(i<fac1.length() && fac1[i]!='*') i++;
        num1 = fac1.substr(0, i);
        if(i != fac1.length())
            vars1 = fac1.substr(i+1, fac1.length()-i-1);
    }
    //处理两个因子相乘 1*a*b*c * 2*c*d
    string multi(string fac1, string fac2) {
        string res = "";
        string num1, vars1, num2, vars2;
        int coff;
        split(fac1, num1, vars1);
        split(fac2, num2, vars2);
        coff = atoi(num1.c_str()) * atoi(num2.c_str());

        vector<string> vvars1, vvars2;
        split_string(vars1, "*", vvars1);
        split_string(vars2, "*", vvars2);
        sort(vvars1.begin(), vvars1.end());
        sort(vvars2.begin(), vvars2.end());

        res += int2str(coff);
        int s1 = 0, s2 = 0;
        while(s1<vvars1.size() && s2<vvars2.size()) {
            if(vvars1[s1] < vvars2[s2]) {
                res += "*";
                res += vvars1[s1];
                s1++;
            }else {
                res += "*";
                res += vvars2[s2];
                s2++;
            }
        }
        while(s1<vvars1.size()) {
            res += "*";
            res += vvars1[s1++];
        }
        while(s2<vvars2.size()) {
            res += "*";
            res += vvars2[s2++];
        }
        return res;
    }
    //排序辅助函数
    static bool cmp(const string &s1, const string &s2) {
        int nums1 = 0, nums2 = 0;  //两因子的度
        for(int i=0; i<s1.length(); i++) if(s1[i] == '*') nums1++;
        for(int i=0; i<s2.length(); i++) if(s2[i] == '*') nums2++;
        if(nums1 != nums2) return nums1 > nums2; //度大的优先
        else {
            string vars1, vars2;
            int i = 0;
            while(i<s1.length() && s1[i]!='*') i++;
            if(i != s1.length()) vars1 = s1.substr(i+1, s1.length()-i-1);
            i = 0;
            while(i<s2.length() && s2[i]!='*') i++;
            if(i != s2.length()) vars2 = s2.substr(i+1, s2.length()-i-1);
            return vars1 < vars2;   //字典序排序
        }
    }
    //合并同类项
    void merge_factor(vector<string> &res, vector<string> &res1) {
        if(res.size() == 0) return ;

        sort(res.begin(), res.end(), cmp);
        int c;
        string num;
        string var;
        for(int i=0; i<res.size(); i++) {
            if(i == 0) {
                split(res[0], num, var);
                c = atoi(num.c_str());
            }else {
                string t_num, t_var;
                split(res[i], t_num, t_var);
                if(t_var == var) c += atoi(t_num.c_str());
                else {
                    if(c != 0) {
                        string tp = int2str(c);
                        if(var != "")   tp += "*"+var;
                        res1.push_back(tp);
                    }
                    num = t_num;
                    var = t_var;
                    c = atoi(num.c_str());
                }
            }
        }
        if(c != 0) { //插入系数非0项
            string tp = int2str(c);
            if(var != "")   tp += "*"+var;
            res1.push_back(tp);
        }
        return ;
    }

    vector<string> exp() {
        vector<string> res = additive();
        vector<string> temp;
        while(token=="+" || token=="-") {
            string op = token;
            token = get_token();    //跳过'+' '-'
            temp = additive();
            if(op=="+") {
                for(int i=0; i<temp.size(); i++) res.push_back(temp[i]);
            }else {
                for(int i=0; i<temp.size(); i++) res.push_back(multi(temp[i], "-1"));
            }
        }
        vector<string> res1;
        //合并同类项
        merge_factor(res, res1);
        return res1;
    }
    vector<string> additive() {
        vector<string> res = factor();
        while(token=="*") {
            token = get_token();   //跳过'*'
            vector<string> fac= factor();
            vector<string> temp;
            //执行相乘运算
            for(int i=0; i<res.size(); i++)
            for(int j=0; j<fac.size(); j++) {
                temp.push_back(multi(res[i], fac[j]));
            }
            res = temp;
        }
        return res;
    }
    vector<string> factor() {
        vector<string> res;
        if(token == "(") {
            token = get_token();
            res = exp();
            token = get_token();  //跳过')'
        }else {
            if(is_num(token)) {
                res.push_back(token);
            }else {
                for(int i=0; i<g_evalvars.size(); i++)
                    if(token == g_evalvars[i])
                        res.push_back(int2str(g_evalints[i]));
                if(res.size() == 0) {
                    string t = "";
                    t += "1*";
                    t += token;
                    res.push_back(t);
                }
            }
            token = get_token();  //跳过num
        }
        return res;
    }
    vector<string> basicCalculatorIV(string expression, vector<string>& evalvars, vector<int>& evalints) {
        vector<string> res;
        str = expression;
        g_evalvars = evalvars;
        g_evalints = evalints;
        index = 0;
        token = get_token();
        res = exp();
        return res;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注