Calculator and Operator Precedence

Calculator and Operator Precedence

[jon]

i ve built a basic calculator which asks user for expression using a
console.

eg

Enter expression : 1 + 2 + 3 * 4

now i need to make it so it can handle Operator Precendence

whats the best way of doing this ? Arrays ?

Re: Calculator and Operator Precedence

[Stephen Leake]

jon <jkjw@brighton.ac.uk> writes:

> i ve built a basic calculator which asks user for expression using a
> console.
> 
> eg
> 
> Enter expression : 1 + 2 + 3 * 4
> 
> now i need to make it so it can handle Operator Precendence
> 
> whats the best way of doing this ? Arrays ?

You need a tree structure, with operators at the nodes and operands at
the leaves.

You can implement a tree using arrays, or linked lists, or many other
things. Or you can use an existing package from on of the Ada
libraries available. See http://www.adapower.com/reuse/index.html

Hmm, I just noticed my library isn't there; I'll have to fix that :).
See http://users.erols.com/leakstan/Stephe/Ada/sal.html

-- 
-- Stephe

Re: Calculator and Operator Precedence

[Matthew Heaney]

"jon" <jkjw@brighton.ac.uk> wrote in message
news:3C727CCF.505D83E0@brighton.ac.uk...
> i ve built a basic calculator which asks user for expression using a
> console.
>
> eg
>
> Enter expression : 1 + 2 + 3 * 4
>
> now i need to make it so it can handle Operator Precendence

You'll need to define a grammar, something like

 <exp> ::= <factor> [+ <exp>]
<factor> ::= <term> [* <factor>]
<term> ::= (<exp>) | <digit>

I like to use an Interpreter pattern.  As you scan the expression, you can
emit expression objects.  To return a value you "evaluate" the ultimate
expression object:

   Exp : constant Exp_Access := Parse (Line);
   Value : constant Integer := Eval (Exp);

http://www.acm.org/archives/wa.cgi?A2=ind9810&L=patterns&P=R2
http://www.acm.org/archives/patterns.html

If you're worried about memory leaks, you can use "smart"
(reference-counted) pointers or "auto" pointers (a la C++) or "control"
types.

Re: Calculator and Operator Precedence

[Phil Thornley]

"jon" <jkjw@brighton.ac.uk> wrote in message
news:3C727CCF.505D83E0@brighton.ac.uk...
> i ve built a basic calculator which asks user for expression using a
> console.
>
> eg
>
> Enter expression : 1 + 2 + 3 * 4
>
> now i need to make it so it can handle Operator Precendence
>
> whats the best way of doing this ? Arrays ?
>

Well, a calculator is one of the examples that runs through the Ada
textbook freely available at:
http://www.adaic.org/docs/craft/html/contents.htm

(Written by someone not too far from brighton.ac.uk :-)

Cheers,

Phil

--
Phil Thornley
Programmes, Engineering
Warton

Re: Calculator and Operator Precedence

[Jon]

yeah ive seen that, but want to make a program without packages.


> Well, a calculator is one of the examples that runs through the Ada
> textbook freely available at:
> http://www.adaic.org/docs/craft/html/contents.htm
>
> (Written by someone not too far from brighton.ac.uk :-)
>
> Cheers,
>
> Phil
>
> --
> Phil Thornley
> Programmes, Engineering
> Warton
>
>

Re: Calculator and Operator Precedence

[John English]

Jon wrote:
> 
> yeah ive seen that, but want to make a program without packages.

The examples in the book are separated into packages, but you could
take the code from the packages and put them in your main procedure
to give you a single monolithic procedure. The book just doesn't do
it that way (because monolithic code is a Bad Thing ;-).

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.it.bton.ac.uk/staff/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

RE: Calculator and Operator Precedence

[Steven Deller]

Interestingly, I just cobbled together Ada code to parse arbitrary Ada
expressions consisting of just operators, parentheses, and literals (I'm
probably going to make it handle type conversions as well).

It uses two stacks (one for operands, one for operators), and recursion
(on parentheses).  Since each stack only needs a maximum of 5 entries
(because of Ada's left to right evaluation for equal precedence
operators) they could have been done with simple arrays (though I used a
stack package abstraction).

You don't need trees.  

I thought about using a grammar-based parse (Matthew H's solution), but
it has some problems with recognizing where you are in the grammar.

Unary operators are the biggest complication.

About 50 lines of code.  If you can prove you're not doing a student
exercise, I'd be glad to send you the sources.

Regards,
Steve

Re: Calculator and Operator Precedence

[Jean-Marc Bourguet]

"Steven Deller" <deller@smsail.com> writes:

> Interestingly, I just cobbled together Ada code to parse arbitrary Ada
> expressions consisting of just operators, parentheses, and literals (I'm
> probably going to make it handle type conversions as well).
> 
> It uses two stacks (one for operands, one for operators), and recursion
> (on parentheses). 

Why do you need recursion?  Parentheses can be handled with the two
stacks, pushing opening parenthese on the operator stack and applaying
operators till a openening parenthese is on TOS when seeing a close
parenthese.

BTW, This parsing technique can be extented (see weak operator
precedence in the litterature) and has been used quite a lot before
LALR grammar where showed to be usefull.

-- 
Jean-Marc

Re: Calculator and Operator Precedence

[Vadim Godunko]

Hello,

Please send me those sources. Very intresting.

Regards,
Vadim
----- Original Message ----- 
From: "Steven Deller" <deller@smsail.com>
Newsgroups: comp.lang.ada
Sent: Friday, February 22, 2002 7:10 PM
Subject: RE: Calculator and Operator Precedence


> Interestingly, I just cobbled together Ada code to parse arbitrary Ada
> expressions consisting of just operators, parentheses, and literals (I'm
> probably going to make it handle type conversions as well).
> 
> It uses two stacks (one for operands, one for operators), and recursion
> (on parentheses).  Since each stack only needs a maximum of 5 entries
> (because of Ada's left to right evaluation for equal precedence
> operators) they could have been done with simple arrays (though I used a
> stack package abstraction).
> 
> You don't need trees.  
> 
> I thought about using a grammar-based parse (Matthew H's solution), but
> it has some problems with recognizing where you are in the grammar.
> 
> Unary operators are the biggest complication.
> 
> About 50 lines of code.  If you can prove you're not doing a student
> exercise, I'd be glad to send you the sources.
> 
> Regards,
> Steve
> 

Re: Calculator and Operator Precedence

[Dmitry A. Kazakov]

On 22 Feb 2002 17:55:49 +0100, Jean-Marc Bourguet <jm@bourguet.org>
wrote:

>"Steven Deller" <deller@smsail.com> writes:
>
>> Interestingly, I just cobbled together Ada code to parse arbitrary Ada
>> expressions consisting of just operators, parentheses, and literals (I'm
>> probably going to make it handle type conversions as well).
>> 
>> It uses two stacks (one for operands, one for operators), and recursion
>> (on parentheses). 
>
>Why do you need recursion?  Parentheses can be handled with the two
>stacks, pushing opening parenthese on the operator stack and applaying
>operators till a openening parenthese is on TOS when seeing a close
>parenthese.

Yes, this technique works perfectly with prefix, postfix operations as
well as function calls and array indexing. No recursion is necessary.
Though kind of pattern matching might be useful for comment detection.

>BTW, This parsing technique can be extented (see weak operator
>precedence in the litterature) and has been used quite a lot before
>LALR grammar where showed to be usefull.

It is still in use.(:-)) I have used it for parsing measurement unit
expressions, which have prefix, dyadic and postfix operations.

Regards,
Dmitry Kazakov