题解 | 小红的能量校准

import java.util.*;

public class Main {

    // 表示 k*x + b
    static class Expr {
        long k; // x 的系数
        long b; // 常数项

        Expr(long k, long b) {
            this.k = k;
            this.b = b;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();

        String[] parts = s.split("=");
        String left = syri(parts[0]);
        long right = Long.parseLong(parts[1]);

        Expr res = eval(left);

        // A*x + B = right
        long x = (right - res.b) / res.k;
        System.out.println(x);
    }

    static String syri(String input) {
        String expr = input;
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < expr.length(); i++) {
            char c = expr.charAt(i);

            if (i > 0) {
                char prev = expr.charAt(i - 1);
                if (needMultiply(prev, c)) {
                    sb.append('*');
                }
            }
            sb.append(c);
        }

        return sb.toString();
    }

    static boolean needMultiply(char prev, char curr) {
        if (Character.isDigit(prev) && Character.isDigit(curr)) {
            return false;
        }
        // 前一个是：数字 / 字母 / ')'
        boolean prevVal = Character.isDigit(prev)
                          || Character.isLetter(prev)
                          || prev == ')';

        // 当前是：数字 / 字母 / '('
        boolean currVal = Character.isDigit(curr)
                          || Character.isLetter(curr)
                          || curr == '(';

        return prevVal && currVal;
    }

    static Expr eval(String s) {
        Stack<Expr> nums = new Stack<>();
        Stack<Character> ops = new Stack<>();

        int i = 0;
        while (i < s.length()) {
            char c = s.charAt(i);

            if (Character.isDigit(c)) {
                long val = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    val = val * 10 + (s.charAt(i) - '0');
                    i++;
                }
                nums.push(new Expr(0, val));
                continue;
            }

            if (c == 'x') {
                nums.push(new Expr(1, 0));
                i++;
                continue;
            }

            if (c == '(') {
                ops.push(c);
                i++;
                continue;
            }

            if (c == ')') {
                while (ops.peek() != '(') {
                    calc(nums, ops);
                }
                ops.pop(); // 弹出 '('
                i++;
                continue;
            }

            if (c == '+' || c == '*') {
                while (!ops.isEmpty() && precedence(ops.peek()) >= precedence(c)) {
                    calc(nums, ops);
                }
                ops.push(c);
                i++;
                continue;
            }

            i++;
        }

        while (!ops.isEmpty()) {
            calc(nums, ops);
        }

        while (!nums.isEmpty() && nums.size() > 1) {
            ops.push('*');
            calc(nums, ops);
            if (nums.size() == 1) {
                return nums.pop();
            }
        }

        return nums.pop();
    }

    static void calc(Stack<Expr> nums, Stack<Character> ops) {
        Expr b = nums.pop();
        Expr a = nums.pop();
        char op = ops.pop();

        if (op == '+') {
            nums.push(new Expr(a.k + b.k, a.b + b.b));
        } else { // '*'
            nums.push(new Expr(
                          a.k * b.b + b.k * a.b,
                          a.b * b.b
                      ));
        }
    }

    static int precedence(char c) {
        if (c == '+') return 1;
        if (c == '*') return 2;
        return 0;
    }
}

优先补全算式中的‘*’。将对x的计算简化为（k,b），一个栈存储参数，一个栈存储符号位，当入栈字符为‘+’、‘*’时，判断当前与前一个符号的优先级，优先算乘法，当入栈是‘）’时，直接封包计算。将左边所有整合成(k,b)->kx+b，最后计算x的数值