6

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

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

我一直在绞尽脑汁试图找出正确的算法PrintWithMinimalParens()应该是什么。我确信必须有一种算法可以在需要对术语进行分组时只输出括号，但是我一直无法正确实现它。我想我必须需要查看当前节点下方树中运算符的优先级，但是我现在拥有的算法不起作用（请参阅我的 main 方法中的最后 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()我想要的吗？顺序是隐含在树中的事实是否使我想做的事情变得不可能？

4

2 回答 2

7

在您的代码中，您将每个运算符与其子项进行比较，以查看是否需要在其周围加上括号。但是您实际上应该将其与其父级进行比较。以下是一些可以确定是否可以省略括号的规则：

  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 时，所需的结果才是正确的。这是因为您的输入树是以右关联方式构建的，而运算符+通常是左关联的。

于 2013-01-06T16:56:21.867 回答
0

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

我认为你需要将你的布尔值 needParens 分成左右孩子的不同案例。像这样的东西（未经测试）：

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)
于 2013-01-06T16:49:39.567 回答