640. 求解方程

题目：

求解一个给定的方程，将x以字符串 "x=#value" 的形式返回。该方程仅包含 '+' ， '-' 操作，变量 x 和其对应系数。

如果方程没有解，请返回 "No solution" 。如果方程有无限解，则返回 “Infinite solutions” 。

题目保证，如果方程中只有一个解，则 'x' 的值是一个整数。

---

示例 1：

输入: equation = "x+5-3+x=6+x-2"
输出: "x=2"

---

示例 2:

输入: equation = "x=x"
输出: "Infinite solutions"

---

示例 3:

输入: equation = "2x=x"
输出: "x=0"

---

提示:

3 <= equation.length <= 1000
equation 只有一个 '='.
equation 方程由整数组成，其绝对值在 [0, 100] 范围内，不含前导零和变量 'x' 。

---

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/solve-the-equation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

思路：

这个方法的核心工作就是统计出左右两侧的x的数量以及化简后常数项的大小，设它们为x_count,num
以"x+5-3+x=6+x-2"为例，左右端都化简完可以得到"2x+2=x+4",即对于左端来说x_count = 2,num = 2;对于右端来说x_count = 1,num=4。
由于两侧的化简方法是相同的所以我们把它提取成同一个函数，用一个vector作为返回值存储x_count,num。最终的x_count = left_x_count - right_x_count,
num = right_num - left_num。
那么x = num/x_count，在进行这步计算之前要判断x_count =0 的情况：当num=0则对应Infinite solutions”；当num!=0则对应“No solution”。
因为本道题只有加减法，因此我们只需根据读取到的+/-来改变当前的sign = 1/-1即可，数字或者x_count更新时注意乘以当前的sign。
本道题的一些cornercase:
1.在读取数字时需要考虑多位数的情况，当我们终止数字读取时一定是遇见了非数字项：x/+/-,或者数字在结尾。前三种情况对数字处理的方式也有所不同：当数字后面接上x时，我们要更新x_count;当数字后面是+/-时，直接计算求和即可，注意要乘以sign。若表达式以数字作为结尾，这种情况我们还需要单独考虑。
2.答案中给了一个特别不合规矩的cornercase "0x=0",针对这种情况我们只能特殊问题特殊处理了，读取到了x前面的数字为y,则x_count += y*sign。但这样会使“x+5 = 3”这种x前面没有数字的情况变成新的cornercase,因此我们可以把这个进行特殊化处理，而把前一种情况泛化处理即可。

---

作者：darwin_tao
链接：https://leetcode.cn/problems/solve-the-equation/solution/zuo-you-yi-qi-hua-jian-gou-zao-fu-zhu-ha-xo1q/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

---

代码：

class Solution {
public:
/* 化简函数：可以将包含x的字符串表达式化简成x_count*x+num的形式*/
vector<int> simplify(string s){
       vector<int> result(2,0);//result[0]存储x_count,result[1]存储num
        int sign = 1;//默认符号为1
        int x_count = 0;//初始化为0
        int num = 0;//工具
        int sum= 0;//最终常数项
        for(int i =0;isize();i++){
            char c = s[i];
            if(c>='0'&&c<='9'){//读取数字
                num = num*10+c-'0';
            }
            else{
                if(c=='x') {
                    //对应cornercase（2）
                    if(i>0&&(s[i-1]=='+'||s[i-1]=='-')||i==0) x_count += sign;
                    else x_count += sign*num;
                    num = 0;//停止读数后为了下一次使用方便要清0
                }
                else {
                sum += num*sign;//累加sum
                num = 0;//清零
                if(c=='+') sign = 1;
                if(c=='-') sign = -1;
                }
            }
        }
        if(num !=0 ){//表达式可能以数字结尾，以上终止条件无法包含这种情况
           sum += num*sign;
        } 
        result[0] = x_count;
        result[1] = sum;
        return result;
}
    string solveEquation(string equation) {
        int i  = equation.size();
        if(i==0) return "No solution"; i--;
        while(equation[i]!= '=') i--;//找到‘=’将字符串分成左右两部分
         string s_left = equation.substr(0,i);
         string s_right = equation.substr(i+1,equation.size()-i-1);
 
         //deal with left
        vector<int> left = simplify(s_left);
 
        //deal with right
        vector<int> right = simplify(s_right);
 
        //organize the result
        int x_count = left[0]-right[0];
        int num = right[1]-left[1];
 
        if(x_count==0&&num==0) return "Infinite solutions";
        if(x_count==0&&num!=0) return "No solution";
        string s = to_string(num/x_count);
        return "x="+s;
    }
};