图解LeetCode——640. 求解方程（难度：中等）

一、题目

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

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

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

二、示例

2.1> 示例 1：

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

2.2> 示例 2:

【输入】 equation = "x=x" 【输出】 "Infinite solutions"

2.3> 示例 3:

【输入】 equation = "2x=x" 【输出】 "x=0"

提示:

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

三、解题思路

3.1> 思路1：

根据题目描述，equation只有一个“=”，所以我们首先可以将整个方程的字符串通过split("=")将其拆分为两部分：左侧方程字符串&右侧方程字符串。为什么要通过等号去拆分整个方程呢？其实有两个主要的原因，首先：我们要针对方程字符串进行解析操作，那么我们可以提供一个通用的拆分方程字符串的方法，这样左侧和右侧的方程字符串都可以通过调用该方法进行拆分操作了。下面我们以equation="x+5-3+x=6+x-2"为例：

通过等号拆分出“左侧方程字符串”和“右侧方程字符串”之后，我们就需要解析方程字符串了。字符串一般是由三种类型组成：首先，“加号”或“减号”；其次，x变量；最后，非x的整数型数字。那么，我们再解析的时候，就可以通过“加号”或者“减号”来分割运算符和非运算符。这里可以通过substring(...)和indexOf(...)方法来获取子串。以字符串x+5-3+x为例，判断indexOf("-")或indexOf("+")的下标位置，取index下标值最小的作为分割末尾，此时待分割末尾index=1，所以通过e.substring(0, 1)获得截取字符串“x”。最后，我们的e就是截取后剩余的字符串。按照上面的逻辑继续的去拆分，最终会将“x+5-3+x”拆分为：“x”，“+5”，“-3”，“+x”。具体操作如下所示：

此时有一个特殊的情况需要注意，就是如果第一个是负数，那么我们特殊处理一下，因为我们在上面的操作过程中，是通过indexOf确定“加号”或“减号”的位置，然后截取其前面的字符串，那么，如果我们通过indexOf("-")可以获得下标位置为0，那么截取的字符串就为空字符串“”了。所以，我们要通过indexOf("-", 1)或者indexOf("+", 1)来进行判断，即：从下标为1的位置开始，而不是从下标为0的位置开始判断。具体操作如下所示：

当我们完成了字符串方程的解析之后，我们就把x变量都放在等号左侧，将非x变量放到等号右侧。那么，在运算过程中，如果x变量在右侧的话，那么由于要被移动到左侧，所以，其正数会变为负数，而负数会变为正数。对于非x变量的移动也会遵循这一点。那么当移动完毕之后，我们会统计x的总和（xSum）以及非x数字的总和（sum）。那么当xSum等于0并且sum等于0的时候，方法返回“Infinite solutions”；否则，如果只有xSum等于0，那么则返回“No solution”；否则，返回 x= sum/xSum。具体操作如下所示：

四、代码实现

4.1> 实现1：

class Solution {
    int xSum = 0; // 所有x，都移动到等号左侧进行计算
    int sum = 0; // 所有数字，均移动到等号右侧进行计算
    
    public String solveEquation(String equation) {
        calculate(equation.split("=")[0], true);
        calculate(equation.split("=")[1], false);
        return (xSum == 0 && sum == 0) ? "Infinite solutions" : (xSum == 0 ? "No solution" : "x=" + sum/xSum);
    }

    public void calculate(String equation, boolean left) {
        while(true) {
            if (equation == null || equation.equals("")) break;
            // 防止第一个数是负数，将其当做减号，所以从第一位开始对比
            int minusIndex = equation.indexOf("-", 1) == -1 ? Integer.MAX_VALUE : equation.indexOf("-", 1); 
            int plusIndex = equation.indexOf("+", 1) == -1 ? Integer.MAX_VALUE : equation.indexOf("+", 1);
            int endIndex = (minusIndex == Integer.MAX_VALUE && plusIndex == Integer.MAX_VALUE) ? equation.length() : Math.min(minusIndex, plusIndex);

            String numStr = equation.substring(0, endIndex);
            if (numStr.contains("x")) {
                // 针对x或者nx的特殊处理
                int xnum = (numStr.equals("x") || numStr.equals("+x")) ? 1 : (numStr.equals("-x") ? -1: Integer.valueOf(numStr.replace("x", "")));
                xSum += left ? xnum : -xnum;
            } else { // 减法操作
                sum += left ? -Integer.valueOf(numStr) : Integer.valueOf(numStr);
            }

            equation = equation.substring(endIndex);
        }
    }
}