Java表达式解析：构建支持括号与一元负号的抽象语法树解析器

record Node(String name, Node left, Node right) {
    @Override
    public String toString() {
        // 重写toString方法，便于打印和调试AST结构
        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;
        }

        // 解析一个“因子”：可以是数字、变量、带括号的表达式或一元负号表达式
        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() + "'");
            }
            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(); // 从解析最顶层的表达式开始
}

public class ExpressionParser {

    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;

            int ch() { return index < input.length() ? input.charAt(index) : -1; }

            boolean eat(char expected) {
                while (Character.isWhitespace(ch())) ++index;
                if (ch() == expected) {
                    ++index;
                    return true;
                }
                return false;
            }

            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() + "'");
                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]]