14 Apr 2004 00:27:58 -0400

Related articles |
---|

Display a parse tree with minimum parentheses? johnmillaway@yahoo.com (John Millaway) (2004-04-14) |

Re: Display a parse tree with minimum parentheses? danwang74@hotmail.com (Daniel C. Wang) (2004-04-15) |

Re: Display a parse tree with minimum parentheses? haberg@matematik.su.se (2004-04-15) |

Re: Display a parse tree with minimum parentheses? clint@0lsen.net (Clint Olsen) (2004-04-15) |

From: | John Millaway <johnmillaway@yahoo.com> |

Newsgroups: | comp.compilers |

Date: | 14 Apr 2004 00:27:58 -0400 |

Organization: | Compilers Central |

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'

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]

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.