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

Groups > comp.programming > #4019 > unrolled thread

Removing Extra/Unnecessary Parentheses

Back to article view | Back to comp.programming

Contents

  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

#4019 — Removing Extra/Unnecessary Parentheses

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?

Thanks for the help.

-Will

[toc] | [next] | [standalone]

#4020

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?
> 
> 
> 
> Thanks for the help.
> 
> 
> 
> -Will

CORRECTION: suppose to be "a+b+c" NOT "a+b+b" as shown above

[toc] | [prev] | [next] | [standalone]

#4026

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.

A simple scanning algorithm looks unlikely.  You can't even drop the
initial '(' of a redundant enclosing pair until you see the end of the
string.  There are asymmetries to consider as well.  (a+b)+c and a+(b+c)
can both be written as a+b+c but the same is not true for a-(b-c).

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#4027

Is it possible if the only two operators are "+" and "*"

[toc] | [prev] | [next] | [standalone]

#4028

waterNight <willmann817@gmail.com> writes:

> Is it possible if the only two operators are "+" and "*"

It's possible if there are other operators too.

You've not kept any context so maybe I've misunderstood what your
initial "it" refers to.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#4029

"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 

[toc] | [prev] | [next] | [standalone]

#4034

On 03-Dec-13 22:57 PM, Ben Bacarisse wrote:
> [..]
> There are asymmetries to consider as well.  (a+b)+c and a+(b+c)
> can both be written as a+b+c but the same is not true for a-(b-c).

Would it get any easier if you translate a - b to a + (-b)? For this 
sample, you'd get

a+ -(b + -c)

and after applying the sign

a + (-b + c)

which can be converted back to a linear '+'-only operation:

a + -b + c

and possibly some sign *cleanup* by replacing '+ -' with '-' again:

a - b + c

The same sequence of operations on (a-b)-c:
  (a + -b) + -c
   a + -b + -c
   a - b - c

[Jw]

[toc] | [prev] | [next] | [standalone]

#4036

On Tue, 10 Dec 2013 10:20:45 +0100, Jongware wrote:

> On 03-Dec-13 22:57 PM, Ben Bacarisse wrote:
>> [..]
>> There are asymmetries to consider as well.  (a+b)+c and a+(b+c)
>> can both be written as a+b+c but the same is not true for a-(b-c).
> 
> Would it get any easier if you translate a - b to a + (-b)?

Yes, e.g. my parser

http://www.dmitry-kazakov.de/ada/components.htm#Parsers_etc

does this. The symbols "+" and "-" can be declared "commutative" with the
unary minus as an inverse. Then the parser will parse

   a + b - c + d

as

  "+"
   |_ a
   |_ b
   |_ "-"
   |  |_ c
   |_ d

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#4037

Dmitry A. Kazakov writes:

> On Tue, 10 Dec 2013 10:20:45 +0100, Jongware wrote:
> 
> > On 03-Dec-13 22:57 PM, Ben Bacarisse wrote:
> >> [..]
> >> There are asymmetries to consider as well.  (a+b)+c and a+(b+c)
> >> can both be written as a+b+c but the same is not true for
> >> a-(b-c).
> > 
> > Would it get any easier if you translate a - b to a + (-b)?
> 
> Yes, e.g. my parser
> 
> http://www.dmitry-kazakov.de/ada/components.htm#Parsers_etc
> 
> does this. The symbols "+" and "-" can be declared "commutative"
> with the unary minus as an inverse. Then the parser will parse
> 
>    a + b - c + d
> 
> as
> 
>   "+"
>    |_ a
>    |_ b
>    |_ "-"
>    |  |_ c
>    |_ d

"Associative".

[toc] | [prev] | [next] | [standalone]

#4038

On 10 Dec 2013 14:34:22 +0200, Jussi Piitulainen wrote:

> Dmitry A. Kazakov writes:
> 
>> On Tue, 10 Dec 2013 10:20:45 +0100, Jongware wrote:
>> 
>>> On 03-Dec-13 22:57 PM, Ben Bacarisse wrote:
>>>> [..]
>>>> There are asymmetries to consider as well.  (a+b)+c and a+(b+c)
>>>> can both be written as a+b+c but the same is not true for
>>>> a-(b-c).
>>> 
>>> Would it get any easier if you translate a - b to a + (-b)?
>> 
>> Yes, e.g. my parser
>> 
>> http://www.dmitry-kazakov.de/ada/components.htm#Parsers_etc
>> 
>> does this. The symbols "+" and "-" can be declared "commutative"
>> with the unary minus as an inverse. Then the parser will parse
>> 
>>    a + b - c + d
>> 
>> as
>> 
>>   "+"
>>    |_ a
>>    |_ b
>>    |_ "-"
>>    |  |_ c
>>    |_ d
> 
> "Associative".

Both. The idea is also to let choose some preferable order of evaluation,
e.g. when folding constants:

   a + 3 - c + 4 --> a + -c + 7

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#4035

On Tue, 3 Dec 2013 06:11:44 -0800 (PST), 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?

Yes. When you generate the AST or whatever else output, you can collapse
the ()-operation with single argument [*]. In a table-driven parser, the
implementation of () would simply push its argument back onto the argument
stack.

----------------------
* () can be overloaded with array/record aggregates. For example, in Ada it
is:

  X := 1+ (2+3);   -- Ordering bracket

  Y := (Color => Red);  -- Record or array aggregate

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#4082

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web