题目描述

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

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

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

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

样例

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

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

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

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

输入: "x=x+2"
输出: "No solution"

算法

(模拟) $O(n)$

1. 设置变量 cons 和 coef 分别记录系数和常数，然后再设立标记 equ_flag 判断在等号左右。
2. 然后依次读取字符，遇到数字累计上；遇到符号，将之前的数字根据正负号和等号左右累积到常数上；遇到 x，将之前的数字根据正负号和等号左右累积到系数上。
3. 特殊情况是 x 前没有数字，此时需要判断若累计到的数字为 0，并且 x 前是符号，则系数根据正负号和等号左右变为 1 或 -1。
4. 最后，若系数不为 0，则最终解为 -cons / coef；若系数和常数都为 0，则无穷多解；否则无解。

时间复杂度

• 每个字符仅遍历一次，故时间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    string solveEquation(string equation) {
        int n = equation.length();
        int cons = 0, coef = 0, equ_flag = 1;
        int tmp_num = 0, neg_flag = 1;
        for (int i = 0; i < n; i++) {
            if (equation[i] >= '0' && equation[i] <= '9')
                tmp_num = tmp_num * 10 + equation[i] - '0';
            else if (equation[i] == '+') {
                cons += tmp_num * neg_flag * equ_flag;
                tmp_num = 0;
                neg_flag = 1;
            }
            else if (equation[i] == '-') {
                cons += tmp_num * neg_flag * equ_flag;
                tmp_num = 0;
                neg_flag = -1;
            }
            else if (equation[i] == 'x') {
                if (tmp_num == 0 && (i == 0 || equation[i - 1] == '+' || equation[i - 1] == '-' || equation[i - 1] == '='))
                    tmp_num = 1;
                coef += tmp_num * neg_flag * equ_flag;
                tmp_num = 0;
                neg_flag = 1;
            }
            else {
                cons += tmp_num * neg_flag * equ_flag;
                tmp_num = 0;
                neg_flag = 1;
                equ_flag = -1;
            }
        }
        cons += tmp_num * neg_flag * equ_flag;

        if (coef != 0)
            return "x=" + to_string(-cons / coef);
        else if (cons == 0 && coef == 0)
            return "Infinite solutions";
        else
            return "No solution";
    }
};