640. 求解方程

示例 ：

输入: “x+5-3+x=6+x-2”
输出: “x=2”

如果方程没有解，请返回“No solution”。

• 如0x=10。此时x的系数为0，常数不为0

如果方程有无限解，则返回“Infinite solutions”。

• 如2x=2x,也就是0x=0。此时x的系数为0，常数也为0

如果方程中只有一个解，要保证返回值 x 是一个整数。

• 如2x=10。此时x的系数不为0，常数不为0

所以我们需要统计x的系数之和以及常量之和。然后将常量除以系数即可

写法1

第一步：将字符串按照+ -分开，并放入向量item中。

• 如把x+5-3+x 分为x,+5,-3,+x。则向量item={‘x’,’+5’,’-3’,’+x’}

vector<string> split(string &equation, vector<string> item) {
    string cur = "";
    for (auto &i:equation) {
        if (i == '+' || i == '-') {
            if (!cur.empty()) { // 遇到了一个符号，则把符号前面的字符串添加到item中
                item.push_back(cur);
                cur = "";// 添加后，将cur置空
            }
        }
        cur += i;
    }
    item.push_back(cur); // 把最后一项也添加进去
    return item;
}

这个函数的功能也可以通过正则表达式来提取

• 注意：这里有一个非常隐蔽的bug。通过re("(?=[-+*/])") 分隔字符时，若一开始就是符号，则也会提取符号前面的内容。如”-1+2”会分成””,”-1”,”+2”（注意这里有一个””）。所以迭代器要用if ((*it)=="") it++; 跳过这个空的，从下一个开始算起（因为这道题的测试用例中含有以符号开始的字符串，所以一定要加这句话，否则在后面的stoi(i)函数中转化为int型时，编译器就懵逼了）
• *it只是与空字符串””内容相同（但类型不同），所以可以用if ((*it)=="") ，不能用(*it).size() 或(*it).empty()判断是否为空

vector<string> split(string &equation, vector<string> item) {
    regex re("(?=[-+])");
    sregex_token_iterator it(equation.begin(), equation.end(), re, -1), end;
    if ((*it)=="") it++; // 注意这句话
    for (; it != end; ++it) {
        item.push_back(*it);
    }
    return item;
}

第二步：得到向量item后，统计x的系数之和以及常量系数之和，将其分别存入coeffX及coeffNum中

vector<int> cal(vector<string> item) {
    int coeffX = 0;
    int coeffNum = 0;
    for (string i:item) {
        if (count(i.begin(), i.end(), 'x')) {
            coeffX += stoi(i);
        } else {
            coeffNum += stoi(i);
        }
    }
    return {coeffX,coeffNum};
}

第三步：由于这是一个等式，所以

• 将字符串按照=分成左右两边
• 分别统计等式左右的系数之和，然后将左右系数相减
  • 如x+5-3+x=6+x-2
    • 左边：x的系数之和为2，常量之和为2
    • 右边：x的系数之和为1，常量之和为4
  • 左边-右边，x的系数之和prevX为1，常量之和prevNum为-2。我们得到了1x-2=0
• 按照x的系数及常量系数是否为0，分别返回相应的字符串结果

注意：在第二步时，用stoi(i)将字符串转成int型时，+x、 -x、 x 这三种不可以直接转，所以需要在原始字符串中将x变为1x。即：x+5-3+x=6+x-2 -> 1x+5-3+1x=6+1x-2 。这样才可以用stoi(i)转换。

for(int i=0;i<equation.size();++i)  //将 'x'换成'1x'
    if(equation[i]=='x'&&(i==0||!isdigit(equation[i-1])))
        equation.insert(equation.begin()+i,'1');

综上，汇总代码：

class Solution {
public:
//    分隔字符串
    vector<string> split(string &equation, vector<string> item) {
        string cur = "";
        for (auto &i:equation) {
            if (i == '+' || i == '-') {
                if (!cur.empty()) { // 遇到了一个符号，则把符号前面的字符串添加到item中
                    item.push_back(cur);
                    cur = "";// 添加后，将cur置空
                }
            }
            cur += i;
        }
        item.push_back(cur); // 把最后一项也添加进去
        return item;
    }
//    统计x和常数的系数
    vector<int> cal(vector<string> item) {
        int coeffX = 0;
        int coeffNum = 0;
        for (string i:item) {
            if (count(i.begin(), i.end(), 'x')) {
                coeffX += stoi(i); // 这是包含x的项
            } else {
                coeffNum += stoi(i); // 这是常数项
            }
        }
        return {coeffX,coeffNum};
    }
    // 汇总函数
    string solveEquation(string equation) {
        //将 'x'换成'1x'    
        for(int i=0;i<equation.size();++i)  
            if(equation[i]=='x'&&(i==0||!isdigit(equation[i-1])))
                equation.insert(equation.begin()+i,'1');
//        根据'='，将字符串分成左右两边
        int idx = equation.find('=');
        string l = equation.substr(0, idx);
        string r = equation.substr(idx + 1, equation.size() - idx - 1); // 可直接写为 string r = equation.substr(idx + 1);
//        将子字符串根据加减号分开，并放到向量中
        vector<string> itemL=split(l, {});
        vector<string> itemR=split(r, {});
//        统计x和常数的系数
        vector<int>preL=cal(itemL);
        vector<int>preR=cal(itemR);
        int prevX=cal(itemL)[0]-cal(itemR)[0];
        int prevNum=cal(itemL)[1]-cal(itemR)[1];
//        根据系数返回对应的结果
        if (prevX==0 && prevNum==0){
            return "Infinite solutions";
        }
        else if (prevX==0 && prevNum!=0){
            return "No solution";
        } else
            return "x="+to_string(-prevNum/prevX);
    }
};

写法2

可以把第一步和第二步整合，在遍历的同时统计x和常数的系数和。

• 如果是数字或x，则放到cur中
• 如果是加减号
  • 前一个为x，则说明是x的系数，放到prevX中 （用i!=0确保前一个字符存在）
  • 前一个为数字，则说明是常数，放到prevNum中 （用i!=0确保前一个字符存在）

class Solution {
public:
//    统计x和常数的系数
    vector<int> splitAndCal(string &equation) {
        string cur = "";
        char sign = ' '; // 用于记录正负号
        vector<int> prevX; // x的系数
        vector<int> prevNum; // 常数系数
        for (int i = 0; i < equation.size(); ++i) {
            char c=equation[i];
            if (isdigit(c)||c=='x'){
                cur+=c;
            }
            else if (c=='+'||c=='-'){
                if (i!=0 && equation[i-1]=='x'){
                    prevX.push_back(stoi(sign+cur));
                }
                else if (i!=0 && isdigit(equation[i-1])){
                    prevNum.push_back(stoi(sign+cur));
                }
                sign=c;
                cur="";
            }
        }
//        记得加最后一个cur
        cur.back()=='x'?prevX.push_back(stoi(sign+cur)):prevNum.push_back(stoi(sign+cur));
        int a=accumulate(prevX.begin(), prevX.end(),0);
        int b=accumulate(prevNum.begin(), prevNum.end(),0);
        return {a,b};
    }


    // 汇总函数
    string solveEquation(string equation) {
        //将 'x'换成'1x'
        for (int i = 0; i < equation.size(); ++i)
            if (equation[i] == 'x' && (i == 0 || !isdigit(equation[i - 1])))
                equation.insert(equation.begin() + i, '1');
//        根据'='，将字符串分成左右两边
        int idx = equation.find('=');
        string l = equation.substr(0, idx);
        string r = equation.substr(idx + 1);
//        将子字符串根据加减号分开，统计x和常数的系数
        vector<int> calL= splitAndCal(l);
        vector<int> calR= splitAndCal(r);

        int allX = calL[0] - calR[0];
        int allNum = calL[1] - calR[1];
//        根据系数返回对应的结果
        if (allX == 0 && allNum == 0) {
            return "Infinite solutions";
        } else if (allX == 0 && allNum != 0) {
            return "No solution";
        } else
            return "x=" + to_string(-allNum / allX);
    }
};