【字符串, 模拟】求解方程

题目

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' 。 ​​​

解题

方法一：字符串 模拟

思路

模拟：把等式按 '=' 分开，然后把两边的式子分别处理成 $ax+b$​ 的形式：

这里 $a$ 和 $b$ 表示系数(coef)和常数(cons)。解析式子(Formula)字符串时，首先创建一个变量表示符号(sign)初始化为 '+' ，这是为了防止第一项的符号为正号省略时符号变量不被初始化，然后创建一个数字(num)维护某一项中的数字。再在输入的字符串后面加一个符号('+')，这是为了让式子中最后一项不被忽略。

遍历字符串中每个字符：

• 如果当前字符是数字(不是 '+'、'-'、'x')，那么直接把当前维护的整数 num 加上该位(乘以 10 再加上该字符表示的整数)，然后记录该项有出现数字(has_num = true)。
• 如果当前字符是 'x'，说明该项是未知项，首先如果该项没有出现数字的话说明这一项是 "x" ($1x$)，那么把 num 赋值为 1（这是为了区分 "0x=0" 这样的测试点），然后根据符号(sign)把 num 累加进系数或者从系数中减去。这一项就处理完了，把 num 重置为 0 、has_num 重置为 false。
• 如果当前字符是 '+' 或 '-'，说明该项是常数项或者是之前已经处理完了的未知项（这种情况不用管，因为变量已经重置过了，不会干扰）。那么就根据符号(sign)把 num 累加进常数或者从常数中减去，然后把维护下一项的符号为当前字符，重置 num、has_num。

处理完后我们会得到这样两个式子：left: Formula{coef=a, cons=b}、right: Formula{coef=c, cons=d}，写成我们熟悉的数学形式就是：$ax+b=cx+d$，这样就简单了，把两边移项变成 $(a-c)x=d-b$ (代码中分别为 coef 和 cons)。那么如果 coef 和 cons 都为零的话等式就是 $0x=0$ 无穷解返回 "Infinite solutions"。如果 coef 不为零，cons 为零的话等式就是 $kx=0$ 无解返回 "No solution"。如果都不为零的话这个等式就可以正常计算：$x=\frac{cons}{coef}$ 按照题目给定的格式返回就可以了。

这题的字符串处理类似 2022 RoboCom 世界机器人开发者大赛-本科组（省赛）- RC-u3 跑团机器人。

代码

struct Formula {
    int coef = 0, cons = 0;

    Formula(string str) {
        str += "+";
        char sign = '+';
        bool has_num = false;
        int num = 0;
        for (char ch : str) {
            switch (ch) {
                case '+': case '-':
                    cons += (sign == '+' ? num : -num);
                    sign = ch;
                    num = 0;
                    has_num = false;
                    break;
                case 'x':
                    if (!has_num) num = 1;
                    coef += (sign == '+' ? num : -num);
                    num = 0;
                    has_num = false;
                    break;
                default:
                    num = num * 10 + ch - '0';
                    has_num = true;
            }
        }
    }
};

class Solution {
public:
    string solveEquation(string equation) {
        int split = equation.find('=');
        Formula left(equation.substr(0, split)), right(equation.substr(split + 1));
        int coef = left.coef - right.coef, cons = right.cons - left.cons;
        if (!coef && !cons) return "Infinite solutions";
        if (!coef) return "No solution";
        return "x=" + to_string(cons / coef);
    }
};

class Formula {
    public int coef = 0, cons = 0;

    public Formula(String str) {
        str += "+";
        char sign = '+';
        boolean hasNum = false;
        int num = 0;
        for (char ch : str.toCharArray()) {
            switch (ch) {
                case '+': case '-':
                    cons += (sign == '+' ? num : -num);
                    sign = ch;
                    num = 0;
                    hasNum = false;
                    break;
                case 'x':
                    if (!hasNum) num = 1;
                    coef += (sign == '+' ? num : -num);
                    num = 0;
                    hasNum = false;
                    break;
                default:
                    num = num * 10 + ch - '0';
                    hasNum = true;
            }
        }
    }
}

class Solution {
    public String solveEquation(String equation) {
        int split = equation.indexOf('=');
        Formula left = new Formula(equation.substring(0, split));
        Formula right = new Formula(equation.substring(split + 1));
        int coef = left.coef - right.coef, cons = right.cons - left.cons;
        if (coef == 0 && cons == 0) return "Infinite solutions";
        if (coef == 0) return "No solution";
        return "x=" + (cons / coef);
    }
}