Stack Calculators, Reverse Polish Notation

[[Digital-X-Treme]]

Hi, i am currently working on an expression evaluating calculator using a stack to evaluate expressions in reverse polish notation.

I am up to the point where i need to convert infix notation to reverse polish.

I know where to go next, in the respect of creating a binary tree and getting the info from that into reverse polish notation, i was just wondering if anyone had done this before, and could offer me any advice...I read in another thread that Guv had created a stack calculator before... Any ideas Guv?

I have seen a very good example in VB of the use of a binary tree to evaluate expressions, but i have lost the link to the site. It was posted in this forum on a thread about evaluating expressions some time ago. I would be greatful if someone could give me a link to this site, as i cannot find the link after searching the forum...

Any ideas, advice or info.?

Laterz

[HarryW]

You can convert Infix to Reverse Polish both by using an intermediate stack while you convert, or by creating an expression tree (a kind of binary tree). You seem to be building your Reverse Polish expression using an expression tree and then a postorder traversal of that tree.

The easiest (and probably best) way to create and use trees is by using recursive functions. You can consider any node in an expression tree to be either

A. a leaf node, if it is a constant

or

B. a root node of a subtree, if it is an operator.

Thus you could write a function called CreateTree, or something similar, taking an infix expression or a constant as a parameter and returning a node ID or a pointer, which would set up a node with either a constant in it (if the parameter is some constant), or a node with an operator in it and two child trees (if the parameter is a non-constant expression). You can do that by calling CreateTree again and assigning the return values to the child nodes.

I hope some of that makes sense, I feel like I want to draw diagrams and stuff.

You can then perform a postorder traversal of the whole expression tree to give the Reverse Polish expression. The pseudocode for that recursive function would be something like this:

if this node is a leaf node,
yield the value of this node
else
yield the value of this node's left child subtree
yield the value of this node's right child subtree
yield the value of this node
end if

[Guv]

In a post I once mentioned my preference for Stack calculators over algebraic ones, but I can provide no help in converting infix notation to reverse Polish.

I know that there is a lot of literature on this subject. Even when writing a compiler for a non stack CPU, conversion to reverse Polish or other stack related notation is typically (always, I think) done first. This step is required to allow for recognition of invalid input, as well as for obtaining a more tractable version of complex equations.

There must be algorithms available on the Web in your local library, and in computer journals.

If I had to do it, I would not reinvent this wheel. I would find an algorithm somewhere, and spend my efforts on writing/testing the code.

[simonm]

Would anyone care to tell me what 'reverse polish notation' is? I've never heard of a stack calculator.

[[Digital-X-Treme]]

Reverse Polish notation is a way of expressing infix notation in a way which computers find easy to work with. Polish notation was developed by Polish philosopher and mathematician Jan Lucasiewicz (1878-1956). Reverse Polish notation, as the name suggests, is a reversal of this notation.

Say you had the following expression to evaluate.

(4+8)*2+6

When evaluating this, we say "Add 4 to 8, times by two, then add 6".

It would be quite hard to code an efficient algorithm to evaluate this expression. The algorithm would have to skip back and forth, evaluating different sections of the expression, taking into account the precedence of operations "BODMAS (Brackets, Order (indices), Divison, Multiplication, Addition, Subtraction)"

A stack is a type of object. You can push elements onto the stack, but u can only pop the top value off of a stack.

In Reverse Polish Notation, numbers and operators from an expression are listed one after another.
When evaluating Reverse Polish notation using a stack, if you come across a number, it is pushed onto the stack. If you come across an operator, it always operates on the top two values of the stack (it 'pops' them off). The result of this operation is then pushed back onto the top of the stack.


Example. Take the equation we had before. (4+8)*2+6

To evaluate this equation correctly, we would:

add 4 and 8 (as they are in brackets)
times the result by 2
add 6 to the result

The equation above would be written like the following in Reverse Polish notation:

4 8 + 2 * 6 +

To evaluate the following Reverse Polish Notation on the stack, you would...

Push 4 onto the stack.
Push 8 onto the stack.
We come across the + operator, so.
Pop the top value off of the stack (8)
Pop the top value off of the stack (4)
Add these two values.
Push the result back onto the stack. (12)
Push 2 on.
We come across the * operator, so.
Pop the top value off of the stack (2)
Pop the top value off of the stack (12)
Multiply these two values.
Push the result back onto the stack. (24)
Push 6 onto the stack.
We come across the + operator, so.
Pop the top value off of the stack (6)
Pop the top value off of the stack (24)
Add these two values.
Push the result back onto the stack (30)
The stack now contains the result of the operation, 30.

I hope this goes some way as to explaining the basics of stacks and reverse polish notation. I myself, have only been looking into this for a couple of days, so forgive me if i am wrong in places.

Laterz

[simonm]

You made it very clear indeed.

[[Digital-X-Treme]]

I am having trouble finding any examples of building binary trees from mathematical expressions. Does anyone know of any examples out there? I have searched the net high and low, but cannot find any examples.

I remeber once coming across a VB site that offered a project which implemented a binary tree in expression evaluation. The project contained numerous examples of the use of the binary tree in VB, packaging its functionality into a DLL, using Memmory APIs to speed things up etc.

I would be grateful if anyone could post links to any sites which off "expression parsing" utilities, so i can check them out to see if it was the site i had come across.

HarryW, u seem to know what i am on about. Could u provide me with any links or examples on creating binary trees for evaluating "mathematical expressions"?

Thanks

Laterz

[HarryW]

What language are you using? VB I assume... well I'll ICQ you

[[Digital-X-Treme]]

Thanks HarryW, i am downloading ICQ again now... (i uninstalled when i partitioned my disk to install linux) I will be 30-40 mins.

Might see ya later if ya still on.

Later

[visualAd]

Sorry to dig this thread up.. I am in the process of creating a probgram which will evaluate an expression. I have decided to use RPN to evaluate the expression.

Converting a string expression to RPN may present a little bit more of a challenge however. I haven't got a clue what binary trees are but here a couple of the ideas I have come up with so far:

Hope fully I am right in assuming that unless otherwise satated by operator precedence or brackets the order of evaluation in an expression is left to right.
Assuming the above I have decided to give all operators a precendence value similar to what is done in programming languages:
^ (exponentional) = 1
* (multiplication) = 10
/ (division) = 10
% (modulus) = 10??
+ (addition) = 20
- (subtraction) = 20

The lower the number the higher the precenence the operator takes.
I have deliberatly left off bracket because I have identified them as sub expressions. Nested brackets may be a bit tricky, in walking through the expression one character at a times, should I find an opening bracket I could dispatch that to another RPN through recursion until i find a closing bracket.
When evaluating single expressions such as:
3 + 4 x 4 - 12 x 7 / 2
I shall first look for the operators with the highest precedence and add the numbers either side of them to the RPN:

3 + (4,4x) - ((12,7x)2/) --> 3,4,4x+12,7x2/-

Is there anything I am missing here?

[zaza]

Hi VA

Do you have a plan for how to deal with, in your case, the subtraction at the end. It may be difficult to know when to do this. In the example you gave you could work through operator by operator until the "precedence" dropped, then do everything up to that point in reverse order. So, You have + then x then -, so when you get to the - you know to go back and do x, then +. Then you do -, x, / and then reach the end, so you go back in reverse order again.

But will that always hold? Certainly not if you have brackets.

By and large, it looks OK, but then I'm drinking wine and even NoteMe's English is starting to look OK.

zaza

[geroldsh]

I'm also writing an expression calculator. However, I am using algebraic; this allows the user to enter expressions as they are read. I use multitreading to separate the expression and pass the results. I also allow the user to enter expressions into ten other textboxes; each of which can be included in the main expression textbox, or within each other. This allows for formulas to be entered. I know this does not contribute to your question; I just wanted to participate. :wave:

[wossname]

I like this RPN idea, very neat.

I might try to do a simple math evaluator in ASM it seems ideal for RPN.

Anyway I have a powerful math evaluator in Roboplot, but thats in VB.Net code I'm afraid. I'm thinking of releasing it as a standalone class lib if there is any interest. Maybe sooner. Here's the tatty old website for it... www.roboplot.8k.com

[visualAd]

Indeed, I believe that most compilers, including ASM compilers convert to RPN anyway.

[szlamany]

Are you looking for PARSING assistance in breaking down the expression into "pairs" of operations?

[wossname]

Assemblers do not optimise as far as I know (being a 1:1 ... code:binary relationship), so you would have to code RPN yourself.

[visualAd]

Are you looking for PARSING assistance in breaking down the expression into "pairs" of operations?
Yes - I am going to have a stab at it next week. It will only be simple to start as I am writing it in Delphi and my string manipulation skills in Delphi are a little rusty :D

[szlamany]

Well - this might be completely useless...

But we had our own proprietary database on the mainframes back in the 80's and 90's and had our own "formula" language that we could use in our table definitions.

We had a routine to COMPILE the formula into RPN - written in VAX-11 BASIC. And a routine to execute the formula - written in VAX-11 MACRO (assembler on the mainframe). These were Digital Computer mini/mainframe type systems...

Well - at any rate, I dug up the old code - and attached it here.

Like I said, might be completely useless to you - but the BASIC is similar to VB (for the most part) - so at least you can get an idea of how we parsed a formula into RPN.

Remember this was the 80's - so structured and object oriented code didn't exist ;)