LeetCode 770. Basic Calculator IV调试程序-wowAC

此代码为了方便大家调试用,使用的时候直接用自己的Solution类覆盖代码中的类,程序的输入文件路径默认在桌面的data_in.txt,使用的时候直接将LeetCode的case复制进文件即可。如下图所示。

image.png

#include <iostream>
#include <fstream>
#include <string.h>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <stack>
#include <sstream>

using namespace std;

/***************改成自己的代码****************/
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;
    }
    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;
    }

    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) {
            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;
    }
};
/***************到此为止****************/


/***************不要修改这些代码****************/

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));
}

vector<string> get_array_string(string line) {
    vector<string> res;
    int i = 0, j = line.length();
    while(i<line.length() && line[i]!='[') i++;
    while(j>=0 && line[j]!=']') j--;
    line = line.substr(i+1, j-1-i);

    split_string(line, ",", res);
    for(int i=0; i<res.size(); i++) {
        int s = 0, e = res[i].length();
        while(s<res[i].length() && res[i][s]!='"') s++;
        while(e>=0 && res[i][e]!='"') e--;
        res[i] = res[i].substr(s+1, e-s-1);
        //cout<<res[i]<<endl;
    }
    //cout<<res.size()<<endl;
    return res;
}

vector<int> get_array_int(string line) {
    vector<int> res;
    vector<string> str_array;
    int i = 0, j = line.length();
    while(i<line.length() && line[i]!='[') i++;
    while(j>=0 && line[j]!=']') j--;
    line = line.substr(i+1, j-i-1);

    split_string(line, ",", str_array);
    for(int i=0; i<str_array.size(); i++) {
        res.push_back(atoi(str_array[i].c_str()));
    }
    return res;
}

string get_string(string line) {
    int i = 0, j = line.length()-1;
    while(i<line.length() && line[i]!='"') i++;
    while(j>=0 && line[j]!='"') j--;
    return line.substr(i+1, j-i-1);
}

void print_res(vector<string> res) {
    cout<<"[";
    for(int i=0; i<res.size(); i++) {
        cout<<"\"";
        cout<<res[i]<<"\"";
        if(i != res.size()-1) cout<<",";
    }
    cout<<"]"<<endl;
}

/***************完毕****************/


int main()
{
    //改成自己的输入路径,注意用双斜杠分割 默认输入文件为桌面的data_in.txt
    fstream fin("C:\\Users\\xingxing\\Desktop\\data_in.txt");
    string expression, evalvars, evalints;
    Solution solu;
    int kase = 1;
    while(getline(fin, expression)) {
        if(expression == "") continue;
        vector<string> vars;
        vector<int> ints;

        getline(fin, evalvars);
        getline(fin, evalints);
        expression = get_string(expression);
        vars = get_array_string(evalvars);
        ints = get_array_int(evalints);
//        cout<<"expression: "<<expression<<endl;
//        //split_string("", "*", vars);
//        //cout<<"vars length: "<<vars.size()<<endl;
//        cout<<"vars: ";
//        for(int i=0; i<vars.size(); i++) {
//            cout<<vars[i]<<" ";
//        }
//        cout<<endl;
//        cout<<"ints: ";
//        for(int i=0; i<ints.size(); i++) {
//            cout<<ints[i]<<" ";
//        }
//        cout<<endl;
        cout<<"case"<<kase++<<": "<<endl;
        vector<string> res;
        res = solu.basicCalculatorIV(expression, vars, ints);
        print_res(res);
    }
    return 0;
}

发表评论

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