题目

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=0$的形式，然后使用数学法求解
• 为了简化代码“Clean Code”，将右式正负颠倒后复用左式的解析函数

代码

class Solution:
    def solveEquation(self, equation: str) -> str:
        a, b = 0,0
        def resolve(expression: str):
            nonlocal a,b
            i = 0
            while i < len(expression):
                operator = expression[i]
                i += 1
                start = i
                while i < len(expression) and expression[i] not in "+-":
                    i += 1
                if expression[i-1] == "x":
                    if operator == "+":
                        if i-start == 1:
                            a += 1
                        else:
                            a += int(expression[start:i-1])
                    else:
                        if i-start == 1:
                            a -= 1
                        else:
                            a -= int(expression[start:i-1])
                else:
                    if operator == "+":
                        b += int(expression[start:i])
                    else:
                        b -= int(expression[start:i])
        left, right = equation.split("=")
        if left[0] != "-":
            left = "+"+left
        if right[0] != "-":
            right = "+"+right
        right = right.translate(str.maketrans("+-", "-+"))
        resolve(left)
        resolve(right)

        if a == 0 and b == 0:
            return "Infinite solutions"
        elif a == 0 and b != 0:
            return "No solution"
        else:
            return F"x={
      -b//a}"
          
class Solution2:
    def solveEquation(self, equation: str) -> str:
        left, right = equation.split("=")
        if left[0] != "-":
            left = "+"+left
        if right[0] != "-":
            right = "+"+right
        # formate ax+b = 0
        a, b, i = 0, 0, 0
        while i < len(left):
            operator = left[i]
            i += 1
            start = i
            while i < len(left) and left[i] not in "+-":
                i += 1
            if left[i-1] == "x":
                if operator == "+":
                    if i-start == 1:
                        a += 1
                    else:
                        a += int(left[start:i-1])
                else:
                    if i-start == 1:
                        a -= 1
                    else:
                        a -= int(left[start:i-1])
            else:
                if operator == "+":
                    b += int(left[start:i])
                else:
                    b -= int(left[start:i])
        i = 0
        while i < len(right):
            operator = right[i]
            i += 1
            start = i
            while i < len(right) and right[i] not in "+-":
                i += 1
            if right[i-1] == "x":
                if operator == "+":
                    if i-start == 1:
                        a -= 1
                    else:
                        a -= int(right[start:i-1])
                else:
                    if i-start == 1:
                        a += 1
                    else:
                        a += int(right[start:i-1])
            else:
                if operator == "+":
                    b -= int(right[start:i])
                else:
                    b += int(right[start:i])
        if a == 0 and b == 0:
            return "Infinite solutions"
        elif a == 0 and b != 0:
            return "No solution"
        else:
            return F"x={
      -b//a}"

复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$python 字符串是Immutable的，因此替换需要声明一个新的字符串，为此可以分开写，见Solution2