解题思路

1. 核心想法：把左侧表达式看成关于未知数的一次式 用一对数值 (k, b) 表示一个子表达式的值：k*x + b。

2. 由于未知数只出现 1 次，所以任意乘法中，最多只有一边含 x，不会出现 x^2。 因此可以安全做线性合并：

   • 加法/减法：(k1, b1) ± (k2, b2) = (k1±k2, b1±b2)
   • 乘法：(k1x+b1)*(k2x+b2) 线性系数：k = k1*b2 + k2*b1 常数项：b = b1*b2

3. 解析表达式：使用递归下降

expr = term {( + | - ) term}*

term = factor { * factor}*

factor = number | variable | '(' expr ')'（可额外支持一元正负号）

(1). expr 负责处理加减（最低优先级）

• 规则：expr = term {( + | - ) term}*
• 含义：先读一个 term，然后只要后面还能看到 + 或 -，就继续读下一个 term 并做加/减，循环下去。
• 为什么加减放这里：因为加减优先级最低，所以要在最外层统一处理。

(2). term 负责处理乘法（高于加减）

• 规则：term = factor { * factor}*
• 含义：先读一个 factor，然后只要后面还能看到 *，就继续读下一个 factor 并做乘法，循环下去。
• 为什么乘法放这里：这样解析出来天然保证 * 比 +/- 先算（因为 expr 每次取的是一个完整的 term）。

(3). factor 负责最基本的“原子”（最高优先级）

• 规则：factor = number | variable | '(' expr ')'（可选支持一元正负号）
• 含义：factor 是不能再拆的最小单位，三种情况：
  • number：一串数字，比如 123
  • variable：未知数，比如 x
  • 括号：( expr )，括号里又是一个完整 expr，所以递归调用 parse_expr()，直到遇到对应的 )
• 括号为什么厉害：因为 factor 直接把 (expr) 当成一个整体返回，所以括号里的加减乘都会先在里面算完。

(4). 一元正负号怎么支持（可选但很常用）

• 在 factor 前面加一条：factor = ('+'|'-') factor | number | variable | '(' expr ')'
• 含义：如果开头是 -，就把后面的 factor 整体取反。

4. 处理隐式乘法：例如 x3、)5、2(x+1) 在分词后，如果出现“前一个是操作数结尾（数字/变量/)）且后一个是操作数开头（数字/变量/(）”，中间自动插入 *。
5. 解方程：左侧解析得到 k*x + b，右侧是整数 R 则 x = (R - b) / k（题目保证是整数）。

复杂度分析

• 设字符串长度为 n
• 时间复杂度：O(n)（分词 + 递归下降每个 token 基本只处理一次）
• 空间复杂度：O(n)（token 列表与递归栈）

代码实现

Python

import sys

# 用 (k, b) 表示 k*x + b
def add(a, b):
    return (a[0] + b[0], a[1] + b[1])

def sub(a, b):
    return (a[0] - b[0], a[1] - b[1])

def mul(a, b):
    # (k1x+b1)*(k2x+b2) 由于 x 只出现一次，不会出现 x^2
    k1, b1 = a
    k2, b2 = b
    return (k1 * b2 + k2 * b1, b1 * b2)

def neg(a):
    return (-a[0], -a[1])

def tokenize(s):
    # 先做基础分词
    base = []
    i = 0
    n = len(s)
    while i < n:
        c = s[i]
        if c.isdigit():
            j = i
            while j < n and s[j].isdigit():
                j += 1
            base.append(("num", int(s[i:j])))
            i = j
        elif c.isalpha():
            base.append(("var", c))
            i += 1
        elif c in "+-*()":
            base.append(("op", c))
            i += 1
        else:
            # 默认输入合法，这里仅跳过空格等
            i += 1

    # 插入隐式乘号
    def is_end_operand(t):
        return t[0] == "num" or t[0] == "var" or (t[0] == "op" and t[1] == ")")

    def is_start_operand(t):
        return t[0] == "num" or t[0] == "var" or (t[0] == "op" and t[1] == "(")

    tokens = []
    for idx in range(len(base)):
        tokens.append(base[idx])
        if idx + 1 < len(base) and is_end_operand(base[idx]) and is_start_operand(base[idx + 1]):
            tokens.append(("op", "*"))
    return tokens

class Parser:
    def __init__(self, tokens):
        self.t = tokens
        self.i = 0

    def peek(self):
        if self.i >= len(self.t):
            return None
        return self.t[self.i]

    def get(self):
        cur = self.peek()
        self.i += 1
        return cur

    def parse_expr(self):
        # expr = term {( + | - ) term}*
        left = self.parse_term()
        while True:
            p = self.peek()
            if p and p[0] == "op" and p[1] in "+-":
                op = self.get()[1]
                right = self.parse_term()
                if op == "+":
                    left = add(left, right)
                else:
                    left = sub(left, right)
            else:
                break
        return left

    def parse_term(self):
        # term = factor { * factor}*
        left = self.parse_factor()
        while True:
            p = self.peek()
            if p and p[0] == "op" and p[1] == "*":
                self.get()
                right = self.parse_factor()
                left = mul(left, right)
            else:
                break
        return left

    def parse_factor(self):
        # factor = (+|-)factor | num | var | '(' expr ')'
        p = self.peek()
        if p and p[0] == "op" and p[1] in "+-":
            op = self.get()[1]
            val = self.parse_factor()
            return val if op == "+" else neg(val)

        p = self.get()
        if p[0] == "num":
            return (0, p[1])
        if p[0] == "var":
            # 未知数只出现一次，变量视作 x
            return (1, 0)
        if p[0] == "op" and p[1] == "(":
            val = self.parse_expr()
            # 读 ')'
            self.get()
            return val
        return (0, 0)  # 理论不会到这里（输入保证合法）

def solve(equation):
    left_s, right_s = equation.split("=")
    tokens = tokenize(left_s)
    parser = Parser(tokens)
    k, b = parser.parse_expr()
    R = int(right_s)
    # k*x + b = R
    x = (R - b) // k
    return x

def main():
    s = sys.stdin.readline().strip()
    print(solve(s))

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {

    // 用 (k, b) 表示 k*x + b
    static class Pair {
        long k, b;
        Pair(long k, long b) { this.k = k; this.b = b; }
    }

    static Pair add(Pair a, Pair c) { return new Pair(a.k + c.k, a.b + c.b); }
    static Pair sub(Pair a, Pair c) { return new Pair(a.k - c.k, a.b - c.b); }

    static Pair mul(Pair a, Pair c) {
        // (k1x+b1)*(k2x+b2) 由于 x 只出现一次，不会出现 x^2
        long k = a.k * c.b + c.k * a.b;
        long b = a.b * c.b;
        return new Pair(k, b);
    }

    static Pair neg(Pair a) { return new Pair(-a.k, -a.b); }

    static class Tok {
        String type; // "num", "var", "op"
        long val;    // num value
        char op;     // operator char
        Tok(String type, long val, char op) { this.type = type; this.val = val; this.op = op; }
        static Tok num(long v) { return new Tok("num", v, '\0'); }
        static Tok var(char c) { return new Tok("var", 0, c); }
        static Tok op(char c)  { return new Tok("op", 0, c); }
    }

    static ArrayList<Tok> tokenize(String s) {
        ArrayList<Tok> base = new ArrayList<>();
        int i = 0, n = s.length();
        while (i < n) {
            char c = s.charAt(i);
            if (c >= '0' && c <= '9') {
                int j = i;
                while (j < n) {
                    char d = s.charAt(j);
                    if (d < '0' || d > '9') break;
                    j++;
                }
                long v = Long.parseLong(s.substring(i, j));
                base.add(Tok.num(v));
                i = j;
            } else if (Character.isLetter(c)) {
                base.add(Tok.var(c));
                i++;
            } else if (c == '+' || c == '-' || c == '*' || c == '(' || c == ')') {
                base.add(Tok.op(c));
                i++;
            } else {
                i++; // 跳过空格等
            }
        }

        // 插入隐式乘号
        ArrayList<Tok> tokens = new ArrayList<>();
        for (int idx = 0; idx < base.size(); idx++) {
            Tok cur = base.get(idx);
            tokens.add(cur);
            if (idx + 1 < base.size()) {
                Tok nxt = base.get(idx + 1);
                if (isEndOperand(cur) && isStartOperand(nxt)) {
                    tokens.add(Tok.op('*'));
                }
            }
        }
        return tokens;
    }

    static boolean isEndOperand(Tok t) {
        if (t.type.equals("num") || t.type.equals("var")) return true;
        return t.type.equals("op") && t.op == ')';
    }

    static boolean isStartOperand(Tok t) {
        if (t.type.equals("num") || t.type.equals("var")) return true;
        return t.type.equals("op") && t.op == '(';
    }

    static class Parser {
        ArrayList<Tok> t;
        int i = 0;
        Parser(ArrayList<Tok> t) { this.t = t; }

        Tok peek() { return i >= t.size() ? null : t.get(i); }
        Tok get() { return t.get(i++); }

        // expr = term {( + | - ) term}*
        Pair parseExpr() {
            Pair left = parseTerm();
            while (true) {
                Tok p = peek();
                if (p != null && p.type.equals("op") && (p.op == '+' || p.op == '-')) {
                    char op = get().op;
                    Pair right = parseTerm();
                    left = (op == '+') ? add(left, right) : sub(left, right);
                } else break;
            }
            return left;
        }

        // term = factor { * factor}*
        Pair parseTerm() {
            Pair left = parseFactor();
            while (true) {
                Tok p = peek();
                if (p != null && p.type.equals("op") && p.op == '*') {
                    get();
                    Pair right = parseFactor();
                    left = mul(left, right);
                } else break;
            }
            return left;
        }

        // factor = (+|-)factor | num | var | '(' expr ')'
        Pair parseFactor() {
            Tok p = peek();
            if (p != null && p.type.equals("op") && (p.op == '+' || p.op == '-')) {
                char op = get().op;
                Pair v = parseFactor();
                return (op == '+') ? v : neg(v);
            }

            Tok cur = get();
            if (cur.type.equals("num")) return new Pair(0, cur.val);
            if (cur.type.equals("var")) return new Pair(1, 0); // 变量即未知数
            if (cur.type.equals("op") && cur.op == '(') {
                Pair v = parseExpr();
                get(); // 读取 ')'
                return v;
            }
            return new Pair(0, 0); // 输入合法理论不会到这里
        }
    }

    static long solve(String equation) {
        String[] parts = equation.split("=");
        String left = parts[0];
        String right = parts[1];

        ArrayList<Tok> tokens = tokenize(left);
        Parser parser = new Parser(tokens);
        Pair res = parser.parseExpr();

        long k = res.k, b = res.b;
        long R = Long.parseLong(right);

        // k*x + b = R
        return (R - b) / k; // 题目保证为整数
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        System.out.print(solve(s.trim()));
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 用 (k, b) 表示 k*x + b
struct Pair {
    long long k, b;
};

Pair addp(const Pair& a, const Pair& c) { return {a.k + c.k, a.b + c.b}; }
Pair subp(const Pair& a, const Pair& c) { return {a.k - c.k, a.b - c.b}; }

Pair mulp(const Pair& a, const Pair& c) {
    // (k1x+b1)*(k2x+b2) 由于 x 只出现一次，不会出现 x^2
    long long k = a.k * c.b + c.k * a.b;
    long long b = a.b * c.b;
    return {k, b};
}

Pair negp(const Pair& a) { return {-a.k, -a.b}; }

struct Tok {
    // type: 0=num, 1=var, 2=op
    int type;
    long long val;
    char op;
};

static bool isEndOperand(const Tok& t) {
    if (t.type == 0 || t.type == 1) return true;
    return t.type == 2 && t.op == ')';
}

static bool isStartOperand(const Tok& t) {
    if (t.type == 0 || t.type == 1) return true;
    return t.type == 2 && t.op == '(';
}

vector<Tok> tokenize(const string& s) {
    vector<Tok> base;
    int n = (int)s.size();
    for (int i = 0; i < n; ) {
        char c = s[i];
        if (c >= '0' && c <= '9') {
            int j = i;
            while (j < n && s[j] >= '0' && s[j] <= '9') j++;
            long long v = stoll(s.substr(i, j - i));
            base.push_back({0, v, 0});
            i = j;
        } else if (isalpha((unsigned char)c)) {
            base.push_back({1, 0, c});
            i++;
        } else if (c=='+' || c=='-' || c=='*' || c=='(' || c==')') {
            base.push_back({2, 0, c});
            i++;
        } else {
            i++; // 跳过空格等
        }
    }

    // 插入隐式乘号
    vector<Tok> tokens;
    for (int i = 0; i < (int)base.size(); i++) {
        tokens.push_back(base[i]);
        if (i + 1 < (int)base.size() && isEndOperand(base[i]) && isStartOperand(base[i + 1])) {
            tokens.push_back({2, 0, '*'});
        }
    }
    return tokens;
}

struct Parser {
    vector<Tok> t;
    int i = 0;
    Parser(const vector<Tok>& t) : t(t) {}

    Tok* peek() {
        if (i >= (int)t.size()) return nullptr;
        return &t[i];
    }
    Tok get() { return t[i++]; }

    // expr = term {( + | - ) term}*
    Pair parseExpr() {
        Pair left = parseTerm();
        while (true) {
            Tok* p = peek();
            if (p && p->type == 2 && (p->op == '+' || p->op == '-')) {
                char op = get().op;
                Pair right = parseTerm();
                left = (op == '+') ? addp(left, right) : subp(left, right);
            } else break;
        }
        return left;
    }

    // term = factor { * factor}*
    Pair parseTerm() {
        Pair left = parseFactor();
        while (true) {
            Tok* p = peek();
            if (p && p->type == 2 && p->op == '*') {
                get();
                Pair right = parseFactor();
                left = mulp(left, right);
            } else break;
        }
        return left;
    }

    // factor = (+|-)factor | num | var | '(' expr ')'
    Pair parseFactor() {
        Tok* p = peek();
        if (p && p->type == 2 && (p->op == '+' || p->op == '-')) {
            char op = get().op;
            Pair v = parseFactor();
            return (op == '+') ? v : negp(v);
        }

        Tok cur = get();
        if (cur.type == 0) return {0, cur.val};
        if (cur.type == 1) return {1, 0}; // 变量即未知数
        if (cur.type == 2 && cur.op == '(') {
            Pair v = parseExpr();
            get(); // 读取 ')'
            return v;
        }
        return {0, 0}; // 输入合法理论不会到这里
    }
};

long long solve(const string& equation) {
    int pos = equation.find('=');
    string left = equation.substr(0, pos);
    string right = equation.substr(pos + 1);

    vector<Tok> tokens = tokenize(left);
    Parser parser(tokens);
    Pair res = parser.parseExpr();

    long long k = res.k, b = res.b;
    long long R = stoll(right);

    // k*x + b = R
    return (R - b) / k; // 题目保证为整数
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    getline(cin, s);
    cout << solve(s);
    return 0;
}

题目内容

给一个字符串的方程表达式 $s$ ，请你实现一个计算器来计算出它的未知数的值。用例保证未知数为整数

输入描述

1.输入为方程的字符表达。例如：$(x_3+2)5=100$ 或者 $5(3x+2)=100$ 。由于乘法交换律，因此两种形式均可能出现。

2.方程由数字、'$x$'、'$+$'、'$*$'、'$($'、'$)$'、和 '$=$' 组成

3.方程未知数 $x$ 只出现在左边，右边为数字。且未知数 $x$ 只出现 $1$ 次

4.所有数字均在 $(-2147483648,2147483647]$ 范围内

5.不会出现连续两个运算符

输出描述

1.求解出的未知数的值。用例保证未知数为整数

2.如果结果是负数，在前面加负号 '$-$'

3.合法的输出有如下 $3$ 种情况：$a、0、-a$

其中 $a$ 取值范围均为 $[0,2147483647]$ 范围

样例1

输入

10+2*x=6

输出

-2

说明

求解方程为 $-2$ ， 请注意乘法的计算优先吸级高于加法

样例2

输入

(x+2)*3=21

输出

5

说明

求解方程

$3x+6=21$

$3x=15$

$x=5$

样例3

输入

((x+2)*3+1)*2+5=79

输出

10

说明

将 $x=10$ 带入方程 $(10+2)*3+1)*2+5=79$，方程两边相等

样例4

输入

(x+2)*3=15

输出

3

说明

将 $x=3$ 带入方程后 $(3+2)*3=15$ 方程两边相等

样例5

输入

x+1=3

输出

2

说明

当 $x=2$ 时方程等式成立

提示

$5 <= s.length <= 1000$

每个数字和运行的计算格适合于一个有符号的 $32$ 位整数

当乘法和加法一起目无括号限制时，乘法的计算顺序高于加法