Search All of the Math Forum:

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

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

 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

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 Karl M. Bunday
9/30/02 Alberto C Moreira
9/30/02 Shmuel (Seymour J.) Metz
10/5/02 Moufang Loop
10/7/02 Shmuel (Seymour J.) Metz
9/30/02 Stephen Herschkorn
9/30/02 Magi D. Shepley
10/1/02 Karl M. Bunday
10/2/02 Kevin Foltinek
10/2/02 Karl M. Bunday
10/3/02 Alberto C Moreira
10/3/02 Kevin Foltinek
10/3/02 Jim Hunter
10/4/02 Herman Rubin
10/4/02 Alberto C Moreira
10/5/02 Herman Rubin
10/4/02 Alberto C Moreira
10/4/02 Kevin Foltinek
10/5/02 Alberto C Moreira
10/6/02 Virgil
10/6/02 Herman Rubin
10/6/02 Jim Hunter
10/6/02 Virgil
10/7/02 Kevin Foltinek
10/8/02 Alberto C Moreira
10/8/02 Kevin Foltinek
10/9/02 Alberto C Moreira
10/10/02 Kevin Foltinek
10/11/02 Alberto C Moreira
10/14/02 Kevin Foltinek
10/15/02 Alberto C Moreira
10/15/02 Kevin Foltinek
10/16/02 Alberto C Moreira
10/16/02 Kevin Foltinek
10/14/02 Kevin Foltinek
10/16/02 Alberto C Moreira
10/16/02 Kevin Foltinek
10/12/02 Shmuel (Seymour J.) Metz
10/14/02 Kevin Foltinek
10/25/02 Van Bagnol
10/25/02 Alberto C Moreira
10/26/02 Van Bagnol
10/27/02 Alberto C Moreira
10/27/02 Herman Rubin
10/28/02 Kevin Foltinek
10/29/02 Alberto C Moreira
10/24/02 Van Bagnol
10/25/02 Van Bagnol
10/26/02 Alberto C Moreira
10/28/02 Kevin Foltinek
10/29/02 Alberto C Moreira
10/29/02 Kevin Foltinek
10/31/02 Alberto C Moreira
10/31/02 Kevin Foltinek
11/2/02 Alberto C Moreira
11/2/02 David Redmond
11/3/02 Alberto C Moreira
11/3/02 Alberto C Moreira
11/4/02 Kevin Foltinek
11/2/02 Virgil
11/4/02 Kevin Foltinek
11/5/02 Alberto C Moreira
11/5/02 Kevin Foltinek
11/6/02 Alberto C Moreira
11/7/02 Kevin Foltinek
11/9/02 Alberto C Moreira
11/11/02 Kevin Foltinek
10/3/02 Kevin Foltinek
10/5/02 Magi D. Shepley