Path: utzoo!attcan!uunet!ogicse!mintaka!spdcc!iecc!compilers-sender
From: firth@sei.cmu.edu (Robert Firth)
Newsgroups: comp.compilers
Subject: Re: Minimizing parentheses in a postfix->infix converter output
Keywords: design
Message-ID: <24038@as0c.sei.cmu.edu>
Date: 14 Apr 91 21:13:13 GMT
References: <9104130521.AA00996@fiu.edu>
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: firth@sei.cmu.edu (Robert Firth)
Organization: Software Engineering Institute, Pittsburgh, PA
Lines: 28
Approved: compilers@iecc.cambridge.ma.us

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.
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.