如何遍历二进制抽象语法树以生成具有最低限度正确括号的中缀符号

传递给我一个表示数学公式的二进制AST。每个内部节点是一个操作符，叶子节点是操作数。我需要遍历树并以中缀符号输出公式。通过使用递归算法(如下面所示的Print()方法)遍历树，这是非常容易做到的。Print()方法的问题是，在转换为中缀时，由于没有生成括号，操作顺序丢失。

我写了PrintWithParens()方法输出一个正确的中缀公式，但是它增加了多余的括号。你可以看到，在main方法的四种情况中，有三种在不需要的情况下添加了括号。

我一直在绞尽脑汁试图找出PrintWithMinimalParens()的正确算法应该是什么。我敢肯定，必须有一个算法，可以输出只有括号时需要组术语，但我一直无法正确实现它。我想我必须需要看看当前节点下面的树中的操作符的优先级，但是我现在在那里的算法不起作用(参见我的主要方法中的最后2个案例)。不需要括号，但是我的逻辑添加了它们)。

public class Test {
static abstract class Node {
    Node left;
    Node right;
    String text;
    abstract void Print();
    abstract void PrintWithParens();
    abstract void PrintWithMinimalParens();
    int precedence()
    {
        return 0;
    }
}
enum Operator { 
    PLUS(1,"+"), 
    MINUS(1, "-"), 
    MULTIPLY(2, "*"), 
    DIVIDE(2, "/"), 
    POW(3, "^") 
    ;
    private final int precedence;
    private final String text;
    private Operator(int precedence, String text)
    {
        this.precedence = precedence;
        this.text = text;
    }
    @Override
    public String toString() {
        return text;
    }
    public int getPrecedence() {
        return precedence;
    }
}
static class OperatorNode extends Node {
    private final Operator op;
    OperatorNode(Operator op)
    {
        this.op = op;
    }
    @Override
    void Print() {
        left.Print();
        System.out.print(op);
        right.Print();
    }
    @Override
    void PrintWithParens() {
        System.out.print("(");
        left.PrintWithParens();
        System.out.print(op);
        right.PrintWithParens();
        System.out.print(")");
    }
    @Override
    void PrintWithMinimalParens() {
        boolean needParens = 
                (left.precedence() != 0 && left.precedence() < this.op.precedence) 
                || 
                (right.precedence() != 0 && right.precedence() < this.op.precedence);
        if(needParens)
            System.out.print("(");
        left.PrintWithMinimalParens();
        System.out.print(op);
        right.PrintWithMinimalParens();
        if(needParens)
            System.out.print(")");
    }
    @Override
    int precedence() {
        return op.getPrecedence();
    }
}
static class TextNode extends Node {
    TextNode(String text)
    {
        this.text = text;
    }
    @Override
    void Print() {
        System.out.print(text);
    }
    @Override
    void PrintWithParens() {
        System.out.print(text);
    }
    @Override
    void PrintWithMinimalParens() {
        System.out.print(text);
    }
}
private static void printExpressions(Node rootNode) {
    System.out.print("Print() : ");
    rootNode.Print();
    System.out.println();
    System.out.print("PrintWithParens() : ");
    rootNode.PrintWithParens();
    System.out.println();
    System.out.print("PrintWithMinimalParens() : ");
    rootNode.PrintWithMinimalParens();
    System.out.println();
    System.out.println();
}
public static void main(String[] args) 
{
    System.out.println("Desired:  1+2+3+4");
    Node rootNode = new OperatorNode(Operator.PLUS);
    rootNode.left = new TextNode("1");
    rootNode.right = new OperatorNode(Operator.PLUS);
    rootNode.right.left = new TextNode("2");
    rootNode.right.right = new OperatorNode(Operator.PLUS);
    rootNode.right.right.left = new TextNode("3");
    rootNode.right.right.right = new TextNode("4");
    printExpressions(rootNode);
    System.out.println("Desired: 1+2*3+4");
    rootNode = new OperatorNode(Operator.PLUS);
    rootNode.left = new TextNode("1");
    rootNode.right = new OperatorNode(Operator.PLUS);
    rootNode.right.left = new OperatorNode(Operator.MULTIPLY);
    rootNode.right.left.left = new TextNode("2");
    rootNode.right.left.right = new TextNode("3");
    rootNode.right.right = new TextNode("4");
    printExpressions(rootNode);
    System.out.println("Desired: 1+2*(3+4)");
    rootNode = new OperatorNode(Operator.PLUS);
    rootNode.left = new TextNode("1");
    rootNode.right = new OperatorNode(Operator.MULTIPLY);
    rootNode.right.left = new TextNode("2");
    rootNode.right.right = new OperatorNode(Operator.PLUS);
    rootNode.right.right.left = new TextNode("3");
    rootNode.right.right.right = new TextNode("4");
    printExpressions(rootNode);
    System.out.println("Desired: 1+2^8*3+4");
    rootNode = new OperatorNode(Operator.PLUS);
    rootNode.left = new TextNode("1");
    rootNode.right = new OperatorNode(Operator.MULTIPLY);
    rootNode.right.left = new OperatorNode(Operator.POW);
    rootNode.right.left.left = new TextNode("2");
    rootNode.right.left.right = new TextNode("8");
    rootNode.right.right = new OperatorNode(Operator.PLUS);
    rootNode.right.right.left = new TextNode("3");
    rootNode.right.right.right = new TextNode("4");
    printExpressions(rootNode);
    }
}

输出:

Desired:  1+2+3+4
Print() : 1+2+3+4
PrintWithParens() : (1+(2+(3+4)))
PrintWithMinimalParens() : 1+2+3+4
Desired: 1+2*3+4
Print() : 1+2*3+4
PrintWithParens() : (1+((2*3)+4))
PrintWithMinimalParens() : 1+2*3+4
Desired: 1+2*(3+4)
Print() : 1+2*3+4
PrintWithParens() : (1+(2*(3+4)))
PrintWithMinimalParens() : 1+(2*3+4)
Desired: 1+2^8*3+4
Print() : 1+2^8*3+4
PrintWithParens() : (1+((2^8)*(3+4)))
PrintWithMinimalParens() : 1+(2^8*3+4)

是否有可能实现我想要的PrintWithMinimalParens() ?树中隐含的顺序是否使我无法随心所欲?

在您的代码中，您将每个操作符与其子操作符进行比较，以查看是否需要将其括起来。但是你应该把它和它的父结点进行比较。以下是一些可以确定括号是否可以省略的规则:

你不需要在AST的根操作符周围加上括号。
如果操作符A是操作符B的子操作符，且A的优先级高于B，则可以省略A周围的括号。
如果左结合运算符a是具有相同优先级的左结合运算符B的左子，则可以省略a周围的括号。左结合运算符是将x A y A z解析为(x A y) A z的运算符。
如果右结合运算符a是具有相同优先级的右结合运算符B的右子，则可以省略a周围的括号。右结合运算符是将x A y A z解析为x A (y A z)的运算符。
如果你可以假设一个运算符A是关联的，即所有x,y,z和A的(x A y) A z = x A (y A z)是同一运算符A的子运算符，你可以选择省略子运算符A周围的括号。在这种情况下，重新解析表达式将产生一个不同的AST，在求值时给出相同的结果。

注意，对于您的第一个示例，期望的结果只有在您可以假设+是关联的(这在处理普通数字时是正确的)并实现规则#5时才是正确的。这是因为输入树是以右结合的方式构建的，而操作符+通常是左结合的。

如果左或右子节点具有较低优先级的操作符，即使其中一个是高优先级或等优先级的操作符，则将整个表达式括在括号中。

我认为你需要把你的布尔needparenns分为不同的左子和右子。像这样(未经测试):

void PrintWithMinimalParens() {
    boolean needLeftChildParens = 
            (left.precedence() != 0 && left.precedence() < this.op.precedence);
    boolean needRightChildParens = 
            (right.precedence() != 0 && right.precedence() < this.op.precedence);
    if(needLeftChildParens)
        System.out.print("(");
    left.PrintWithMinimalParens();
    if(needLeftChildParens)
        System.out.print(")");
    System.out.print(op);
    if(needRightChildParens)
        System.out.print("(");
    right.PrintWithMinimalParens();
    if(needRightChildParens)
        System.out.print(")");
}

还有，我不认为你最后一个例子是正确的。看着你的树，我想应该是:

1+2^8*(3+4)

相关内容

最新更新

热门标签：