实现抽象语法树

在 Java 中定义抽象语法树（AST）通常涉及创建一些基本的类来表示树中的节点。每个节点可以代表一个操作符、操作数、变量或表达式。

下面是一个简单的抽象语法树的 Java 实现示例，表示算术表达式：

1. 定义 AST 节点类

首先定义一个 ASTNode 类，它可以有不同的子类来表示不同类型的节点（例如操作符、操作数等）。

// 抽象语法树节点
abstract class ASTNode {
    // 递归的方式输出节点信息
    public abstract void print();
}

// 表示操作数的节点，如数字或变量
class OperandNode extends ASTNode {
    String value;

    public OperandNode(String value) {
        this.value = value;
    }

    @Override
    public void print() {
        System.out.print(value);
    }
}

// 表示操作符的节点，如 +, -, *, /
class OperatorNode extends ASTNode {
    char operator;
    ASTNode left;
    ASTNode right;

    public OperatorNode(char operator, ASTNode left, ASTNode right) {
        this.operator = operator;
        this.left = left;
        this.right = right;
    }

    @Override
    public void print() {
        System.out.print("(");
        left.print();
        System.out.print(" " + operator + " ");
        right.print();
        System.out.print(")");
    }
}

2. 创建树的根节点并构建表达式

接下来，我们创建一个表达式并使用不同类型的节点构建抽象语法树。例如，构建一个表示 a + b * c 的 AST。

public class Main {
    public static void main(String[] args) {
        // 构建 AST 表达式：a + b * c
        ASTNode a = new OperandNode("a");
        ASTNode b = new OperandNode("b");
        ASTNode c = new OperandNode("c");

        // b * c
        ASTNode mul = new OperatorNode('*', b, c);

        // a + (b * c)
        ASTNode add = new OperatorNode('+', a, mul);

        // 打印 AST
        System.out.print("AST: ");
        add.print();
        System.out.println();  // 输出: (a + (b * c))
    }
}

3. 输出

输出的 AST 将展示表达式 a + b * c 的结构：

AST: (a + (b * c))

4. 解析与扩展

上述代码构建了一个简单的表达式 AST。你可以根据需求扩展它的功能，比如支持更多类型的操作符，或者支持常量、函数调用等。在实际的编译器或解释器中，AST 会更加复杂，但本示例提供了构建 AST 的基本框架。

总结

• ASTNode：定义了抽象语法树的基本结构。
• OperandNode：用于表示操作数（如数字、变量等）。
• OperatorNode：用于表示操作符（如 +、-、*、/ 等），同时连接左右子节点表示操作数或子表达式。
• 构建与打印：通过连接这些节点来构建树，并通过递归的方式打印 AST 结构。