I like Reverse Polish calculators.
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.
Binary Trees - Doing my nut!
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
Re: Stack Calculators, Reverse Polish Notation
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?
Re: Stack Calculators, Reverse Polish Notation
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
Re: Stack Calculators, Reverse Polish Notation
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:
Re: Stack Calculators, Reverse Polish Notation
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
Re: Stack Calculators, Reverse Polish Notation
Indeed, I believe that most compilers, including ASM compilers convert to RPN anyway.
Re: Stack Calculators, Reverse Polish Notation
Are you looking for PARSING assistance in breaking down the expression into "pairs" of operations?
Re: Stack Calculators, Reverse Polish Notation
Assemblers do not optimise as far as I know (being a 1:1 ... code:binary relationship), so you would have to code RPN yourself.
Re: Stack Calculators, Reverse Polish Notation
Quote:
Originally Posted by szlamany
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
5 Attachment(s)
Re: Stack Calculators, Reverse Polish Notation
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 ;)