The Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: Is this an exceptionally hard set of questions to answer?
Replies: 68   Last Post: Nov 11, 2002 7:54 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Alberto C Moreira

Posts: 266
Registered: 12/6/04
Re: Is this an exceptionally hard set of questions to answer?
Posted: Nov 3, 2002 10:09 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


David B. Redmond <redmonds@sprynet.com> said:


>No, the issue here is expanding the expression by use of the
>distributive property and there is no intuition involved.


I'm going to follow this up again. No, the issue is not to expand the
expression by use of the distributive property, that's an awfully
clunky way of doing it. What we want is a content-free way of parsing
expressions, that is, a syntax-only way, that works irrespective of
semantics.

It is much more effective to use the notions of operator associativity
and precedence, which are defined at syntactical level and do not need
any knowledge of the semantics of the operations. The rules in this
particular case can be pretty simple:

1. Count the level of parenthesis and do operations deeper inside
first,
2. Once you got rid of parenthesis, do exponentiations first,
followed by multiplications, followed by additions.

This can be encoded in a simple parsing scheme:

1. addition and subtraction have base precedence 1;
2. multiplication and division have base precedence 2;
3. exponentiation has base precedence 3;
4. for every level of parenthesis, add a bias > 4 to the operator's
precedence.

What you're left with is the sequence in which you must compute your
operations. So, for example,

(3+4)*(5*(6+7))

( sets bias=10
+ has precedence 1+10 = 11
) sets bias=0
* has precedence 2
( sets bias=10
* has precedence 10+2 = 12
( sets bias =20
+ has precedence 20+2=22
) sets bias=10
) sets bias=0

So, what we have to do is to compute in precedence order,

6+7=13 because the rightmost + has precedence 22
5*13=65 because the rightmost * has precedence 12
3+4=7 because the leftmost + has precedence 11
7 * 65 = 455 because the leftmost * has precedence 2.

The point that these rules of precedence get operations do behave as
if a distributive law holds is of second importance here, parsing the
expression using the distributive property is a waste of time for both
men and machines.

By the way, this is called "Klammergebirge", the mountains of
parentheses, by its creators Grau, Hill and Langmaak in their vintage
60's Algol compilation book. And notice I'm glossing over issues with
unary operators and with operator left or right associativity.

Now, change the precedences, and guess what ? The meaning of the
expression may change. That's why something like

a + b*c + d

is ambiguous, notationwise, unless we apply operator precedence rules
to it. These precedence rules can be contrived to satisfy the
arithmetic distributive property; or they can be changed to mimc
whatever semantics we might want to, and they can be made semantics
free. We can change the precedence rules if what we want is to do a+b
and c+d before we multiply: it basically has to do with what we want
our notation to express. And in modern computing, we are entitled to
overload the meanings of scribbles such as "+" and "*" to mean things
other than numeric addition and multiplication, so in a way the
traditional math track is a bit stifling here, we need to have rules
to parse expressions that work at syntatic level only and pay no
attention to the semantics of the underlying operations. I said it
before, the advent of computers has put a different spice into this
brew.


Alberto.



Date Subject Author
9/28/02
Read Is this an exceptionally hard set of questions to answer?
Karl M. Bunday
9/30/02
Read Re: Is this an exceptionally hard set of questions to answer?
Alberto C Moreira
9/30/02
Read Re: Is this an exceptionally hard set of questions to answer?
Shmuel (Seymour J.) Metz
10/5/02
Read Re: Is this an exceptionally hard set of questions to answer?
Moufang Loop
10/7/02
Read Re: Is this an exceptionally hard set of questions to answer?
Shmuel (Seymour J.) Metz
9/30/02
Read Re: Is this an exceptionally hard set of questions to answer?
Stephen Herschkorn
9/30/02
Read Re: Is this an exceptionally hard set of questions to answer?
Magi D. Shepley
10/1/02
Read Re: Is this an exceptionally hard set of questions to answer?
Karl M. Bunday
10/2/02
Read Re: Is this an exceptionally hard set of questions to answer?
Kevin Foltinek
10/2/02
Read Re: Is this an exceptionally hard set of questions to answer?
Karl M. Bunday
10/3/02
Read Re: Is this an exceptionally hard set of questions to answer?
Alberto C Moreira
10/3/02
Read Re: Is this an exceptionally hard set of questions to answer?
Kevin Foltinek
10/3/02
Read Re: Is this an exceptionally hard set of questions to answer?
Jim Hunter
10/4/02
Read Re: Is this an exceptionally hard set of questions to answer?
Herman Rubin
10/4/02
Read Re: Is this an exceptionally hard set of questions to answer?
Alberto C Moreira
10/5/02
Read Re: Is this an exceptionally hard set of questions to answer?
Herman Rubin
10/4/02
Read Re: Is this an exceptionally hard set of questions to answer?
Alberto C Moreira
10/4/02
Read Re: Is this an exceptionally hard set of questions to answer?
Kevin Foltinek
10/5/02
Read Re: Is this an exceptionally hard set of questions to answer?
Alberto C Moreira
10/6/02
Read Re: Is this an exceptionally hard set of questions to answer?
Virgil
10/6/02
Read Re: Is this an exceptionally hard set of questions to answer?
Herman Rubin
10/6/02
Read Re: Is this an exceptionally hard set of questions to answer?
Jim Hunter
10/6/02
Read Re: Is this an exceptionally hard set of questions to answer?
Virgil
10/7/02
Read Re: Is this an exceptionally hard set of questions to answer?
Kevin Foltinek
10/8/02
Read Re: Is this an exceptionally hard set of questions to answer?
Alberto C Moreira
10/8/02
Read Re: Is this an exceptionally hard set of questions to answer?
Kevin Foltinek
10/9/02
Read Re: Is this an exceptionally hard set of questions to answer?
Alberto C Moreira
10/10/02
Read Re: Is this an exceptionally hard set of questions to answer?
Kevin Foltinek
10/11/02
Read Re: Is this an exceptionally hard set of questions to answer?
Alberto C Moreira
10/14/02
Read Re: Is this an exceptionally hard set of questions to answer?
Kevin Foltinek
10/15/02
Read Re: Is this an exceptionally hard set of questions to answer?
Alberto C Moreira
10/15/02
Read Re: Is this an exceptionally hard set of questions to answer?
Kevin Foltinek
10/16/02
Read Re: Is this an exceptionally hard set of questions to answer?
Alberto C Moreira
10/16/02
Read Re: Is this an exceptionally hard set of questions to answer?
Kevin Foltinek
10/14/02
Read Re: Is this an exceptionally hard set of questions to answer?
Kevin Foltinek
10/16/02
Read Re: Is this an exceptionally hard set of questions to answer?
Alberto C Moreira
10/16/02
Read Re: Is this an exceptionally hard set of questions to answer?
Kevin Foltinek
10/12/02
Read Re: Is this an exceptionally hard set of questions to answer?
Shmuel (Seymour J.) Metz
10/14/02
Read Re: Is this an exceptionally hard set of questions to answer?
Kevin Foltinek
10/25/02
Read Re: Is this an exceptionally hard set of questions to answer?
Van Bagnol
10/25/02
Read Re: Is this an exceptionally hard set of questions to answer?
Alberto C Moreira
10/26/02
Read Re: Is this an exceptionally hard set of questions to answer?
Van Bagnol
10/27/02
Read Re: Is this an exceptionally hard set of questions to answer?
Alberto C Moreira
10/27/02
Read Re: Is this an exceptionally hard set of questions to answer?
Herman Rubin
10/28/02
Read Re: Is this an exceptionally hard set of questions to answer?
Kevin Foltinek
10/29/02
Read Re: Is this an exceptionally hard set of questions to answer?
Alberto C Moreira
10/24/02
Read Re: Is this an exceptionally hard set of questions to answer?
Van Bagnol
10/25/02
Read Re: Is this an exceptionally hard set of questions to answer?
Van Bagnol
10/26/02
Read Re: Is this an exceptionally hard set of questions to answer?
Alberto C Moreira
10/28/02
Read Re: Is this an exceptionally hard set of questions to answer?
Kevin Foltinek
10/29/02
Read Re: Is this an exceptionally hard set of questions to answer?
Alberto C Moreira
10/29/02
Read Re: Is this an exceptionally hard set of questions to answer?
Kevin Foltinek
10/31/02
Read Re: Is this an exceptionally hard set of questions to answer?
Alberto C Moreira
10/31/02
Read Re: Is this an exceptionally hard set of questions to answer?
Kevin Foltinek
11/2/02
Read Re: Is this an exceptionally hard set of questions to answer?
Alberto C Moreira
11/2/02
Read Re: Is this an exceptionally hard set of questions to answer?
David Redmond
11/3/02
Read Re: Is this an exceptionally hard set of questions to answer?
Alberto C Moreira
11/3/02
Read Re: Is this an exceptionally hard set of questions to answer?
Alberto C Moreira
11/4/02
Read Re: Is this an exceptionally hard set of questions to answer?
Kevin Foltinek
11/2/02
Read Re: Is this an exceptionally hard set of questions to answer?
Virgil
11/4/02
Read Re: Is this an exceptionally hard set of questions to answer?
Kevin Foltinek
11/5/02
Read Re: Is this an exceptionally hard set of questions to answer?
Alberto C Moreira
11/5/02
Read Re: Is this an exceptionally hard set of questions to answer?
Kevin Foltinek
11/6/02
Read Re: Is this an exceptionally hard set of questions to answer?
Alberto C Moreira
11/7/02
Read Re: Is this an exceptionally hard set of questions to answer?
Kevin Foltinek
11/9/02
Read Re: Is this an exceptionally hard set of questions to answer?
Alberto C Moreira
11/11/02
Read Re: Is this an exceptionally hard set of questions to answer?
Kevin Foltinek
10/3/02
Read Re: Is this an exceptionally hard set of questions to answer?
Kevin Foltinek
10/5/02
Read Re: Is this an exceptionally hard set of questions to answer?
Magi D. Shepley

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2017. All Rights Reserved.