Display a parse tree with minimum parentheses?

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'
operator.


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 comp.compilers page.
Search the comp.compilers archives again.