高效Java表达式解析器设计与实现

record Node(String name, Node left, Node right) {
    @Override
    public String toString() {
        return "Node[" + name
            + (left != null ? ", " + left : "")
            + (right != null ? ", " + right : "") + "]";
    }
}

static Node parse(String input) {
    return new Object() {
        int index = 0; // 当前解析位置

        /**
         * 获取当前字符，不移动指针。
         * 如果已到达字符串末尾，返回-1。
         */
        int ch() {
            return index < input.length() ? input.charAt(index) : -1;
        }

        /**
         * 尝试消费一个预期字符。
         * 会跳过所有空白字符，如果当前字符与预期字符匹配，则移动指针并返回true。
         * 否则，不移动指针并返回false。
         */
        boolean eat(char expected) {
            while (Character.isWhitespace(ch())) { // 跳过空白字符
                ++index;
            }
            if (ch() == expected) {
                ++index;
                return true;
            }
            return false;
        }

        /**
         * 解析最小的表达式单元，即“因子”。
         * 因子可以是：
         * 1. 带括号的表达式 (expression)
         * 2. 单个字母操作数
         * 3. 带有一元减号的因子 (-factor)
         */
        Node factor() {
            Node node;
            boolean minus = eat('-'); // 检查是否有一元减号
            if (eat('(')) { // 如果遇到左括号，解析括号内的表达式
                node = expression();
                if (!eat(')')) { // 确保有匹配的右括号
                    throw new RuntimeException("')' expected");
                }
            } else if (Character.isAlphabetic(ch())) { // 如果是字母，解析为操作数
                node = new Node(Character.toString(ch()), null, null);
                ++index;
            } else { // 遇到未知字符，抛出异常
                throw new RuntimeException("unknown char '" + (char)ch() + "' at index " + index);
            }
            if (minus) { // 如果之前有减号，则创建一个一元减号节点
                node = new Node("-", node, null);
            }
            return node;
        }

        /**
         * 解析一个完整的表达式。
         * 表达式由一个或多个因子通过二元操作符连接而成。
         * 由于输入表达式已通过括号明确操作顺序，这里只需简单地从左到右处理。
         */
        Node expression() {
            Node node = factor(); // 首先解析一个因子
            while (true) { // 循环处理后续的二元操作符和因子
                if (eat('*')) node = new Node("*", node, factor());
                else if (eat('/')) node = new Node("/", node, factor());
                else if (eat('+')) node = new Node("+", node, factor());
                else if (eat('-')) node = new Node("-", node, factor()); // 注意：这里的'-'是二元操作符
                else break; // 没有更多操作符，解析结束
            }
            return node;
        }
    }.expression(); // 从解析最顶层的表达式开始
}

static void testParse(String input) {
    System.out.printf("%-22s -> %s%n", input, parse(input));
}

public static void main(String[] args) {
    testParse("a+b");
    testParse("(a/b) - (c*v)");
    testParse("((a/(b))) - (((c)*v))");
    testParse("-a");
    testParse("-a + (-c/v)");
    testParse("-(c)");
    testParse("(-(c))");
}

a+b                    -> Node[+, Node[a], Node[b]]
(a/b) - (c*v)          -> Node[-, Node[/, Node[a], Node[b]], Node[*, Node[c], Node[v]]]
((a/(b))) - (((c)*v))  -> Node[-, Node[/, Node[a], Node[b]], Node[*, Node[c], Node[v]]]
-a                     -> Node[-, Node[a]]
-a + (-c/v)            -> Node[+, Node[-, Node[a]], Node[/, Node[-, Node[c]], Node[v]]]
-(c)                   -> Node[-, Node[c]]
(-(c))                 -> Node[-, Node[c]]