0640. 求解方程【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 模拟解析

1. 📝 题目描述

• leetcode

求解一个给定的方程，将 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 只有一个 '='.
• 方程由绝对值在 [0, 100] 范围内且无任何前导零的整数和变量 'x' 组成。​​​

2. 🎯 s.1 - 模拟解析

c

void parse(char* s, int* coef, int* val) {
    *coef = 0; *val = 0;
    int num = 0, sign = 1, hasNum = 0;
    for (int i = 0; s[i] || hasNum; i++) {
        char c = s[i];
        if (c == 0 || c == '+' || c == '-') {
            if (hasNum) *val += sign * num;
            num = 0; hasNum = 0;
            sign = (c == '-') ? -1 : 1;
            if (c == 0) break;
        } else if (c == 'x') {
            *coef += hasNum ? sign * num : sign;
            num = 0; hasNum = 0;
        } else {
            num = num * 10 + (c - '0');
            hasNum = 1;
        }
    }
}

char* solveEquation(char* equation) {
    char* eq = strchr(equation, '=');
    int pos = eq - equation;
    char left[256], right[256];
    strncpy(left, equation, pos); left[pos] = 0;
    strcpy(right, eq + 1);
    int lc, lv, rc, rv;
    parse(left, &lc, &lv);
    parse(right, &rc, &rv);
    int coef = lc - rc, val = rv - lv;
    char* res = (char*)malloc(64);
    if (coef == 0) {
        strcpy(res, val == 0 ? "Infinite solutions" : "No solution");
    } else {
        sprintf(res, "x=%d", val / coef);
    }
    return res;
}

js

/**
 * @param {string} equation
 * @return {string}
 */
var solveEquation = function (equation) {
  const parse = (s) => {
    let coef = 0,
      val = 0,
      num = 0,
      sign = 1,
      hasNum = false
    for (let i = 0; i <= s.length; i++) {
      const c = s[i]
      if (i === s.length || c === '+' || c === '-') {
        if (hasNum) val += sign * num
        num = 0
        hasNum = false
        if (c === '-') sign = -1
        else sign = 1
      } else if (c === 'x') {
        coef += hasNum ? sign * num : sign
        num = 0
        hasNum = false
      } else {
        num = num * 10 + +c
        hasNum = true
      }
    }
    return [coef, val]
  }
  const [left, right] = equation.split('=')
  const [lc, lv] = parse(left)
  const [rc, rv] = parse(right)
  const coef = lc - rc
  const val = rv - lv
  if (coef === 0) return val === 0 ? 'Infinite solutions' : 'No solution'
  return `x=${val / coef}`
}

py

class Solution:
    def solveEquation(self, equation: str) -> str:
        def parse(s):
            coef = val = num = 0
            sign = 1
            has_num = False
            for i, c in enumerate(s + '+'):
                if c in '+-':
                    if has_num:
                        val += sign * num
                    num = 0
                    has_num = False
                    sign = -1 if c == '-' else 1
                elif c == 'x':
                    coef += sign * num if has_num else sign
                    num = 0
                    has_num = False
                else:
                    num = num * 10 + int(c)
                    has_num = True
            return coef, val
        left, right = equation.split('=')
        lc, lv = parse(left)
        rc, rv = parse(right)
        coef, val = lc - rc, rv - lv
        if coef == 0:
            return 'Infinite solutions' if val == 0 else 'No solution'
        return f'x={val // coef}'

• 时间复杂度：$O(n)$，其中 n 是方程字符串长度
• 空间复杂度：$O(1)$

算法思路：

• 分别解析等号左右两侧，提取 x 的系数和常数项
• 移项后判断：系数为 0 时无解或无穷解，否则 x = 常数 / 系数