How to traverse a binary abstract syntax tree to generate infix notation with minimally correct parentheses

Question

Binary AST is presented to me, representing a mathematical formula. Each internal node is an operator, and leaf nodes are operands. I need to go through the tree and derive the formula in infix notation. This is fairly easy to do by traversing the tree using a recursive algorithm such as the Print() method, which is shown below. The problem with the Print() method is that the order of operations is lost when converting to infix, since the brackets are not created.

I wrote a PrintWithParens() method that outputs the correct infix formula, however it adds extraneous parentheses. You can see in three of four cases my main method, which adds brackets when not necessary.

I am trying to figure out what the correct algorithm for PrintWithMinimalParens() should be. I am sure there should be an algorithm that can only output brackets when necessary in order to group the terms, however I could not execute it correctly. I think I need to look at the priority of the operators in the tree below the current node, but the algorithm that I have there now does not work (see the last 2 cases in my main method. No brackets are required, but my logic adds them).

 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); } } 

Output:

 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) 

Is it possible to implement the PrintWithMinimalParens() that I want? Does the fact that the order is implicit in the tree make what I want impossible?

Answer 1

In your code, you are comparing each statement with its children to see if you need parentheses. But you really have to compare it with your parent. Here are some rules that can determine whether parentheses can be omitted:

• You do not need parentheses around the operator in the root of the AST.
• If the operator A is a descendant of the operator B and A has a higher priority than B, the brackets around A may be omitted.
• If the left-associative operator A is the left child of the left-associative operator B with the same priority, the brackets around A can be omitted. A left-associative operator is one for which x A y A z parsed as (x A y) A z .
• If the right associative operator A is the right child of the right associative operator B with the same priority, parentheses around A can be omitted. A correctly associative operator is one for which x A y A z parsed as x A (y A z) .
• If you can assume that the operator A is associative , that is, (x A y) A z = x A (y A z) for all x, y, z and A is a child of the same operator A, you can exclude round parentheses around child A. In this case, re-expression of the expression will give another AST, which gives the same result when evaluating.

Please note that for your first example, the desired result is correct if you can assume that + is associative (which is true when working with normal numbers) and implements rule number 5. This is because your input tree is constructed correctly associatively, and the + operator is usually left-associative.

Answer 2

An integer expression is included in parentheses if either the left or right operator has an operator with a lower priority, even if one of them is an operator with a higher or equal priority.

I think you need to separate your logical needParens in individual cases for left and right children. Something like this (untested):

 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(")"); } 

Also, I don't think your last example is true. Looking at your tree, I think it should be:

 1+2^8*(3+4)