Path: csiph.com!usenet.pasdenom.info!aioe.org!.POSTED!not-for-mail From: Kaz Kylheku Newsgroups: comp.programming Subject: Re: Removing Extra/Unnecessary Parentheses Date: Sat, 25 Jan 2014 07:41:40 +0000 (UTC) Organization: Aioe.org NNTP Server Lines: 43 Message-ID: <20140124233541.822@kylheku.com> References: NNTP-Posting-Host: X+c6YNb3AaWMPA3YfA4opg.user.speranza.aioe.org X-Complaints-To: abuse@aioe.org User-Agent: slrn/pre1.0.0-18 (Linux) X-Notice: Filtered by postfilter v. 0.8.2 Xref: csiph.com comp.programming:4082 On 2013-12-03, waterNight wrote: > Given an arithmetic expression in infix notation and in the form of a string, > what is an algorithm to remove the extra parentheses? The PEMDAS or My Dear > Aunt Sally precedence rules are in effect so "(a*b)+c" needs to return > "a*b+c" and "((a+b)+c)" needs to return "a+b+b". Is it possible to do > without converting to postfix notation by just scanning for a certain > property or properties? If so what am I looking for? The abstract syntaxes for a*b+c and a*(b+c) are: + * * c a + a b b c In this representation, there are no parentheses. Why does the second tree require parentheses when rendered into infix? Simple! The condition is "precedence inversion": that a low precedence operator node (+) is a child of a higher precedence operator node (*). We can proceed bottom up, perhaps recursively. Scanning the tree, we produce the infix pieces: {a} and {b + c}. Now we are standing at the * node and it is time to combine these child infix pieces. What do we do? We peer at both pieces and see that one of them is based on an operator with a lower precedence than *. So, we wrap it with parens, and now we have {a} and {(b + c)}. At this point we combine them: {a * (b + c)}. Try something like that! Syntax tree first, then traverse it to produce infix, using the principle of comparing parent and child precedences, looking for inversion. Child expressions based on lower precedence operators than their parents have to be wrapped. -- Music DIY Mailing List: http://www.kylheku.com/diy ADA MP-1 Mailing List: http://www.kylheku.com/mp1