如何使用二进制抽象语法树来生成具有最小正确括号的中缀表示法

Question

我正在传递一个表示数学公式的二进制AST.每个内部节点都是运算符,叶节点是操作数.我需要走树并以中缀表示法输出公式.通过使用递归算法(例如Print()下面显示的方法)遍历树,这很容易实现.该Print()方法的问题在于转换为中缀时操作顺序丢失,因为没有生成括号.

我编写了PrintWithParens()输出正确的中缀公式的方法,但它添加了无关的括号.您可以在我的main方法的四个案例中的三个中看到它在没有必要时添加括号.

我一直绞尽脑汁试图弄清楚PrintWithMinimalParens()应该是什么样的正确算法.我确信必须有一个算法只能在必要时输出括号来组合术语,但是我无法正确实现它.我想我必须要查看当前节点下面树中运算符的优先级,但我现在的算法不起作用(参见我的main方法中的最后两种情况.不需要括号,但是我的逻辑添加它们).

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()我想要的吗？订单是否隐含在树中的事实是否使我想做的事情变得不可能？

Answer 1

在您的代码中,您将每个操作符与其子项进行比较,以查看是否需要围绕它的括号.但你应该把它与它的父母进行比较.以下是一些可以确定是否可以省略括号的规则:

1. 在AST的根处,您永远不需要围绕运算符的括号.
2. 如果运算符A是运算符B的子节点,并且A的优先级高于B,则可以省略A周围的括号.
3. 如果左关联运算符A是具有相同优先级的左关联运算符B的左子节点,则可以省略A周围的括号.左关联运算符是x A y A z被解析为的运算符(x A y) A z.
4. 如果右关联运算符A是具有相同优先级的右关联运算符B的右子,则可以省略A周围的括号.右关联运算符x A y A z是解析为的运算符x A (y A z).
5. 如果你可以假设运营商A是联想,即(x A y) A z = x A (y A z)对所有的X,Y,Z,A是同一运营商A的孩子,你可以选择忽略周围的孩子A.括号在这种情况下,重新分析表达将产生一个不同的AST,在评估时给出相同的结果.

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