Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #4029

Re: Removing Extra/Unnecessary Parentheses

Show key headers only | View raw

"Ben Bacarisse" <ben.usenet@bsb.me.uk> wrote in message
news:0.dcc0fa872d9e7291a5b7.20131203215734GMT.87pppdppgx.fsf@bsb.me.uk...
> waterNight <willmann817@gmail.com> writes:
>
>> On Tuesday, December 3, 2013 9:11:44 AM UTC-5, 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+c".  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?
>
> I think you'll have to parse the expression.  Once you have a parse
> tree, it's not hard to write it out with minimal parentheses.

I've just tried this, but I'm starting from a parse tree, with the intention
being to write it out as an expression, but without superfluous parentheses.

Given a parse tree such as X op Y (where X and Y operands can also be nested
expressions of any depth), then the decision to wrap either X or Y in
parentheses must be taken at this point.

For X, parentheses are needed when X is a binary op with precedence lower
then 'op' above (so would otherwise be evaluated after the main op, when
processing the resulting flat expression).

For Y, parentheses are also needed when its precedence is lower, or when 
precedence is the same, but the main op is non-reversible. (And the process 
is applied recursively.)

There are probably other issues (when Y might be a unary op expression, for
example, although I think the problem here is making sure operator symbols
don't end up together (so X+(-(-Y)) might appear as X+--Y)). (I haven't
looked at right-to-left precedence either.)

(Also, the OP probably intends the output only for a human reader. I might
also need the result to be compatible with a particular language, so the
precedences must match that (although there all sorts of extra complications
to deal with there in that case.)

-- 
Bartc 

Back to comp.programming | Previous | Next — Previous in thread | Next 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