Databases
StackOverflow2013
Postsdbo
POHow to walk binary abstract syntax tree to generate infix notation with minimally correct parentheses
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow to walk binary abstract syntax tree to generate infix notation with minimally correct parentheses
    primarykey
    data
    text
    <p>I am being passed a binary AST representing a math formula. Each internal node is an operator and leaf nodes are the operands. I need to walk the tree and output the formula in infix notation. This is pretty easy to do by walking the tree with a recursive algorithm such as the <code>Print()</code> method shows below. The problem with the <code>Print()</code> method is that the order of operations is lost when converting to infix because no parentheses are generated.</p> <p>I wrote the <code>PrintWithParens()</code> method which outputs a correct infix formula, however it adds extraneous parentheses. You can see in three of the four cases of my main method it adds parenthesis when none are necessary.</p> <p>I have been racking my brain trying to figure out what the correct algorithm for <code>PrintWithMinimalParens()</code> should be. I'm sure there must be an algorithm that can output only parentheses when necessary to group terms, however I have been unable to implement it correctly. I think I must need to look at the precedence of the operators in the tree below the current node, but the algorithm I have there now does't work (see the last 2 cases in my main method. No parentheses are needed, but my logic adds them).</p> <pre><code>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 &amp;&amp; left.precedence() &lt; this.op.precedence) || (right.precedence() != 0 &amp;&amp; right.precedence() &lt; 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); } } </code></pre> <p>Output:</p> <pre><code>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) </code></pre> <p><strong>Is is possible to implement the <code>PrintWithMinimalParens()</code> that I want? Does the fact that order is implicit in the tree make doing what I want impossible?</strong></p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USJustin
    1. USJustin
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow to walk binary abstract syntax tree to generate infix notation with minimally correct parentheses
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POHow to walk binary abstract syntax tree to generate infix notation with minimally correct parentheses
      1. This table or related slice is empty.
      1. VTUpMod
    1. COA Google search for [postfix to infix converter] turns up lots of good results with examples in Ruby, C#, C, Java, etc.
      singulars
      1. POHow to walk binary abstract syntax tree to generate infix notation with minimally correct parentheses
      1. USJim Mischel
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload