Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!elroy.jpl.nasa.gov!decwrl!world!iecc!compilers-sender
From: acmfiu@fiu.edu (ACMFIU)
Newsgroups: comp.compilers
Subject: Minimizing parentheses in a postfix->infix converter output
Keywords: design
Message-ID: <9104130521.AA00996@fiu.edu>
Date: 13 Apr 91 05:21:31 GMT
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: acmfiu@fiu.edu (ACMFIU)
Organization: Compilers Central
Lines: 17
Approved: compilers@iecc.cambridge.ma.us

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.  This was done for convenience. but now I'd
like to make it better.  As this will involve, to my knowledge, some
lookahead to test the next operator, I don't see the binary tree as the
best data structure.  What can I use to make the lookahead "not hard" and
how would I go about doing what I want?

albert chin
[It is my recollection that there is an easy way to do paren minimization,
but the details escape me. Roughly, at each level you build the expression
string, and wrap a subexpression in parens if its operator binds looser
than the one in the current expression. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.