Re: Removing Extra/Unnecessary Parentheses

Path	csiph.com!usenet.pasdenom.info!aioe.org!.POSTED!not-for-mail
From	Kaz Kylheku <kaz@kylheku.com>
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> (permalink)
References	<ac32b1f5-bd3d-4d84-8b29-7c2499fde56d@googlegroups.com>
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

Show key headers only | View raw

On 2013-12-03, waterNight <willmann817@gmail.com> 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

Back to comp.programming | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Removing Extra/Unnecessary Parentheses waterNight <willmann817@gmail.com> - 2013-12-03 06:11 -0800
  Re: Removing Extra/Unnecessary Parentheses waterNight <willmann817@gmail.com> - 2013-12-03 06:12 -0800
    Re: Removing Extra/Unnecessary Parentheses Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-12-03 21:57 +0000
      Re: Removing Extra/Unnecessary Parentheses waterNight <willmann817@gmail.com> - 2013-12-03 18:12 -0800
        Re: Removing Extra/Unnecessary Parentheses Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-12-04 02:45 +0000
      Re: Removing Extra/Unnecessary Parentheses "BartC" <bc@freeuk.com> - 2013-12-04 11:43 +0000
      Re: Removing Extra/Unnecessary Parentheses Jongware <jongware@no-spam.plz> - 2013-12-10 10:20 +0100
        Re: Removing Extra/Unnecessary Parentheses "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2013-12-10 11:35 +0100
          Re: Removing Extra/Unnecessary Parentheses Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2013-12-10 14:34 +0200
            Re: Removing Extra/Unnecessary Parentheses "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2013-12-10 14:35 +0100
  Re: Removing Extra/Unnecessary Parentheses "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2013-12-10 11:35 +0100
  Re: Removing Extra/Unnecessary Parentheses Kaz Kylheku <kaz@kylheku.com> - 2014-01-25 07:41 +0000

csiph-web