|Display a parse tree with minimum parentheses? email@example.com (John Millaway) (2004-04-14)|
|Re: Display a parse tree with minimum parentheses? firstname.lastname@example.org (Daniel C. Wang) (2004-04-15)|
|Re: Display a parse tree with minimum parentheses? email@example.com (2004-04-15)|
|Re: Display a parse tree with minimum parentheses? firstname.lastname@example.org (Clint Olsen) (2004-04-15)|
|From:||John Millaway <email@example.com>|
|Date:||14 Apr 2004 00:27:58 -0400|
|Keywords:||parse, question, comment|
|Posted-Date:||14 Apr 2004 00:27:58 EDT|
Given a parse tree representing a typical boolean expression, where the
grouping is implicit in the tree structure, is there an algorithm to print
the equivalent unambiguous infix expression with the minimum parentheses
(preserving left-to-right order)?
For example, the parse tree for the expression, "a or b and c," would be
naively printed as "(a or (b and c))," although no parentheses are required,
assuming that the `and' operator has higher precedence than the `or'
My best guess is that the the left subtree requires parentheses if the
precedence of the right-most unparenthesized operator in that subtree is less
than or equal to the precedence of the current operator, and similarly for
the right subtree.
Thanks, -John M
[This is a very familiar question, and I think your idea about adding
parens when there's a precedence drop is the right one. -John]
Return to the
Search the comp.compilers archives again.