6

数式を表すバイナリ AST が渡されます。各内部ノードは演算子であり、リーフ ノードはオペランドです。ツリーをたどって式を中置表記で出力する必要があります。これは、以下に示す方法のような再帰アルゴリズムを使用してツリーをたどることで、非常に簡単に実行できPrint()ます。このメソッドの問題は、Print()括弧が生成されないため、中置に変換するときに操作の順序が失われることです。

PrintWithParens()正しい中置式を出力するメソッドを書きましたが、余分な括弧が追加されています。メイン メソッドの 4 つのケースのうち 3 つのケースで、括弧が不要なときに括弧が追加されていることがわかります。

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()ことは可能ですか？順序がツリー内で暗黙的であるという事実は、私がやりたいことを不可能にしますか?

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 がassociativeである、つまり、(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 に答える