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

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

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