小红的能量校准

题目分析

给定一个关于变量 $x$ 的一元一次方程，形如 左侧表达式=右侧整数。左侧表达式包含变量 $x$ 、非负整数、运算符 +、*、(、)，且存在隐式乘法——当数字、变量、括号直接相邻时，中间省略了乘号。例如 2(x+1) 表示 $2 \times (x+1)$ ，x3 表示 $x \times 3$ 。

$x$ 在左侧恰好出现一次，方程保证有整数解，求 $x$ 的值。

思路

递归下降解析 + 线性多项式运算

由于 $x$ 只出现一次，左侧表达式关于 $x$ 是线性的，可以表示为 $ax + b$ 的形式。我们用一个二元组 $(a, b)$ 来表示每个子表达式的值，其中 $a$ 是 $x$ 的系数， $b$ 是常数项。

定义运算规则：

加法： $(a_1, b_1) + (a_2, b_2) = (a_1 + a_2, b_1 + b_2)$
减法： $(a_1, b_1) - (a_2, b_2) = (a_1 - a_2, b_1 - b_2)$
乘法： $(a_1, b_1) \times (a_2, b_2) = (a_1 b_2 + a_2 b_1, b_1 b_2)$ （因为线性， $a_1 a_2 = 0$ ）

用递归下降解析表达式，按优先级从低到高分三层：

parseExpr：处理 + 和 -，解析若干 term 的加减。
parseTerm：处理 * 和隐式乘法。当下一个字符是 (、x 或数字时，即为隐式乘法。
parseFactor：处理最基本的单元——数字返回 $(0, v)$ ，变量 $x$ 返回 $(1, 0)$ ，括号则递归调用 parseExpr。

解析完左侧得到 $(a, b)$ ，右侧为整数 $r$ ，则 $x = (r - b) / a$ 。

代码

C++
Java
Python3
JavaScript

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

typedef pair<long long, long long> P;
string s;
int pos;

P parseExpr();
P parseTerm();
P parseFactor();

P mul(P p1, P p2) {
    return {p1.first * p2.second + p2.first * p1.second, p1.second * p2.second};
}

P parseExpr() {
    P res = parseTerm();
    while (pos < (int)s.size() && (s[pos] == '+' || s[pos] == '-')) {
        char op = s[pos++];
        P t = parseTerm();
        if (op == '+') res = {res.first + t.first, res.second + t.second};
        else res = {res.first - t.first, res.second - t.second};
    }
    return res;
}

P parseTerm() {
    P res = parseFactor();
    while (pos < (int)s.size()) {
        if (s[pos] == '*') {
            pos++;
            res = mul(res, parseFactor());
        } else if (s[pos] == '(' || s[pos] == 'x' || isdigit(s[pos])) {
            res = mul(res, parseFactor());
        } else break;
    }
    return res;
}

P parseFactor() {
    if (s[pos] == '(') {
        pos++;
        P res = parseExpr();
        pos++;
        return res;
    } else if (s[pos] == 'x') {
        pos++;
        return {1, 0};
    } else {
        long long num = 0;
        while (pos < (int)s.size() && isdigit(s[pos]))
            num = num * 10 + (s[pos++] - '0');
        return {0, num};
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    getline(cin, s);
    int eq = s.find('=');
    long long rhs = stoll(s.substr(eq + 1));
    s = s.substr(0, eq);
    pos = 0;
    P lhs = parseExpr();
    cout << (rhs - lhs.second) / lhs.first << endl;
}

import java.util.Scanner;

public class Main {
    static String s;
    static int pos;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        int eq = line.indexOf('=');
        long rhsVal = Long.parseLong(line.substring(eq + 1));
        s = line.substring(0, eq);
        pos = 0;
        long[] lhs = parseExpr();
        System.out.println((rhsVal - lhs[1]) / lhs[0]);
    }

    static long[] parseExpr() {
        long[] res = parseTerm();
        while (pos < s.length() && (s.charAt(pos) == '+' || s.charAt(pos) == '-')) {
            char op = s.charAt(pos++);
            long[] t = parseTerm();
            if (op == '+') { res[0] += t[0]; res[1] += t[1]; }
            else { res[0] -= t[0]; res[1] -= t[1]; }
        }
        return res;
    }

    static long[] parseTerm() {
        long[] res = parseFactor();
        while (pos < s.length()) {
            if (s.charAt(pos) == '*') {
                pos++;
                long[] f = parseFactor();
                res = mul(res, f);
            } else if (s.charAt(pos) == '(' || s.charAt(pos) == 'x' || Character.isDigit(s.charAt(pos))) {
                res = mul(res, parseFactor());
            } else break;
        }
        return res;
    }

    static long[] parseFactor() {
        if (s.charAt(pos) == '(') {
            pos++;
            long[] res = parseExpr();
            pos++;
            return res;
        } else if (s.charAt(pos) == 'x') {
            pos++;
            return new long[]{1, 0};
        } else {
            long num = 0;
            while (pos < s.length() && Character.isDigit(s.charAt(pos)))
                num = num * 10 + (s.charAt(pos++) - '0');
            return new long[]{0, num};
        }
    }

    static long[] mul(long[] a, long[] b) {
        return new long[]{a[0] * b[1] + b[0] * a[1], a[1] * b[1]};
    }
}

import sys

def solve():
    line = input().strip()
    eq = line.index('=')
    lhs_str = line[:eq]
    rhs_val = int(line[eq+1:])

    s = lhs_str
    pos = [0]

    def parse_expr():
        a, b = parse_term()
        while pos[0] < len(s) and s[pos[0]] in '+-':
            op = s[pos[0]]; pos[0] += 1
            ta, tb = parse_term()
            if op == '+': a += ta; b += tb
            else: a -= ta; b -= tb
        return a, b

    def parse_term():
        a, b = parse_factor()
        while pos[0] < len(s):
            c = s[pos[0]]
            if c == '*':
                pos[0] += 1
                fa, fb = parse_factor()
                a, b = a * fb + fa * b, b * fb
            elif c == '(' or c == 'x' or c.isdigit():
                fa, fb = parse_factor()
                a, b = a * fb + fa * b, b * fb
            else: break
        return a, b

    def parse_factor():
        c = s[pos[0]]
        if c == '(':
            pos[0] += 1
            a, b = parse_expr()
            pos[0] += 1
            return a, b
        elif c == 'x':
            pos[0] += 1
            return 1, 0
        else:
            num = 0
            while pos[0] < len(s) and s[pos[0]].isdigit():
                num = num * 10 + int(s[pos[0]])
                pos[0] += 1
            return 0, num

    a, b = parse_expr()
    print((rhs_val - b) // a)

solve()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });

rl.on('line', (line) => {
    line = line.trim();
    const eq = line.indexOf('=');
    const lhs = line.substring(0, eq);
    const rhsVal = BigInt(line.substring(eq + 1));

    let pos = 0;
    const s = lhs;

    function parseExpr() {
        let [a, b] = parseTerm();
        while (pos < s.length && (s[pos] === '+' || s[pos] === '-')) {
            const op = s[pos++];
            const [ta, tb] = parseTerm();
            if (op === '+') { a += ta; b += tb; }
            else { a -= ta; b -= tb; }
        }
        return [a, b];
    }

    function parseTerm() {
        let [a, b] = parseFactor();
        while (pos < s.length) {
            if (s[pos] === '*') {
                pos++;
                const [fa, fb] = parseFactor();
                [a, b] = [a * fb + fa * b, b * fb];
            } else if (s[pos] === '(' || s[pos] === 'x' || (s[pos] >= '0' && s[pos] <= '9')) {
                const [fa, fb] = parseFactor();
                [a, b] = [a * fb + fa * b, b * fb];
            } else break;
        }
        return [a, b];
    }

    function parseFactor() {
        if (s[pos] === '(') {
            pos++;
            const res = parseExpr();
            pos++;
            return res;
        } else if (s[pos] === 'x') {
            pos++;
            return [1n, 0n];
        } else {
            let num = 0n;
            while (pos < s.length && s[pos] >= '0' && s[pos] <= '9')
                num = num * 10n + BigInt(s[pos++].charCodeAt(0) - 48);
            return [0n, num];
        }
    }

    const [a, b] = parseExpr();
    console.log(((rhsVal - b) / a).toString());
    rl.close();
});

复杂度分析

时间复杂度： $O(n)$ ，其中 $n$ 为表达式字符串长度。每个字符恰好被访问一次。
空间复杂度： $O(d)$ ，其中 $d$ 为括号嵌套深度，即递归栈的深度。