Re: Minimizing parentheses in a postfix->infix converter output

firth@sei.cmu.edu (Robert Firth)
14 Apr 91 21:13:13 GMT

          From comp.compilers

Related articles
Minimizing parentheses in a postfix->infix converter output acmfiu@fiu.edu (1991-04-13)
Re: Minimizing parentheses in a postfix->infix converter output ressler@cs.cornell.edu (1991-04-14)
Re: Minimizing parentheses in a postfix->infix converter output firth@sei.cmu.edu (1991-04-14)
Re: Minimizing parentheses in a postfix->infix converter output ge@dbf.kun.nl (1991-04-15)
| List of all articles for this month |

Newsgroups: comp.compilers
From: firth@sei.cmu.edu (Robert Firth)
Keywords: design
Organization: Software Engineering Institute, Pittsburgh, PA
References: <9104130521.AA00996@fiu.edu>
Date: 14 Apr 91 21:13:13 GMT

In article <9104130521.AA00996@fiu.edu> acmfiu@fiu.edu (ACMFIU) writes:
>I have a postfix->infix converter and need to output the least number of
>parentheses as possible. The resulting infix expression is kept in a
>binary tree and I just traverse the tree outputting the left/right
>parentheses at each level.


Easy. You need to know the priority of the operators (obviously),
and, before emittinga subtree that isn't a leaf, you compare the
priority of its operator to that of the parent node.


If the sub has a higher priority, no parens.


If the sub has a lowe priority, parens always.


If the sub has the same priority, then you use parens around the
right subtree for a left-associative operator, and the left subtree
for a right-associative operator.


Examples:


ab*c+ => a*b+c
ab+c* => (a+b)*c
abc-- => a-(b-c)


Hope that helps.
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.