Well, that's been a good start. Sadly, although it's great at validating expressions, it doesn't calculate a thing. We need to do something else to calculate values.
Computing Expressions
To actually calculate some values, we need to add a value stack and modify the routines to support calculations using that stack. To handle this, we add "actions" at the right point in the productions. When a number is properly detected, it is placed on the stack, for example. When an operation is detected, it proceeds to get the next value and then performs the indicated calculation, too.
The reason for a stack to hold values is that the calculations cannot always proceed in the left to right order of processing the expression. For example, when processing 5+3*4, the value 5 needs to be placed somewhere temporarily, while the product of 3 and 5 are processed. To handle this, a manually managed stack can be used.
The details of the stack method I chose, in BASIC, use some functions that aren't commonly used. These are MKD$() and CVD() and can be used to append and remove values from a convenient BASIC string variable. Their big advantage is that the floating point values are maintained precisely and the stack count is automatically maintained as part of the string's length. I've included two routines to manage this process of appending and removing values, Push and Pop. Because there is some possibility of division by zero, error checking is now added, as well. Dividing by zero places a special value on the stack called "overflow." In the end, this can be tested to determine if the calculation was unable to proceed. The routines to deal with this are Overflow and IsOverflow.
The essence, though, of arranging to have calculations proceed are:
- When a number is recognized, get its value and push it on the stack; and,
- When an operation is detected, get the next value and perform the indicated operation -- such operations, if binary (as all of these are), should remove two values from the stack and place the computed result back onto the stack.
Rather than belabor these details, I think we've proceeded far enough that I can just provide a new, modified version of the code developed earlier and let you persue it on your own, looking at the differences. I think you'll see what's going on, now that you have some context. Just compare the differences in the routines. I think you'll see what I did.
If you take this code and modify Item to print the value that is pushed there and modify Add, Subtract, Multiply, and Divide to simply print out their respective operation symbol (all of these, one per line), then you will also see reverse polish notation printed on your screen! Try it.
I've also created a program that will evaluate various, common unary functions such as SIN, TAN, and so on. You can examine it at:
- EQ_07.ZIP or EQ_07.BAS
- This program adds the ability to calculate common unary function values, like SIN() and TAN().
Final Notes
None of these programs support the use of a unary sign before the first term of an expression. The first item of the first term can only be either a number or else an expression surrounded by parenthesis. As numbers do, in fact, support a sign, the only place this becomes an issue is if you try and use a leading, unary sign before an open paren at the start of an expression. In that case, the code will reject it. For example, -(5) will be rejected.
If you want this feature, you need to extend the rules to support it and change the code. This is a good chance to test what you may understand, by now. There are several possible approaches that involve small changes to the code and the productions that will do the job well.
In addition, the idea of adding variables that can be set as well as read and used in expressions requires some changes to the productions to support named variables in expressions; assignment statements (an equal sign thing); and code to add and find these named variables in a table of some kind. One of the advantages of having a variable table, too, is that you can predefine some names (like PI, for example) so that they can be conveniently used in expressions. The code in EQ_07 already has most of the production rule changes and actual code needed to use variables in expressions (just examine the Item routine, which already collects up a token that is tested against pre-defined function names and could be also tested against a variable name table.) It does not support assignment statements, but adding them requires very little real change.
For those not interested in trying to add these things on their own, I'll include some files you can grab, below:
- EQ_08.ZIP or EQ_08.BAS
- This program adds support for a unary sign before an open paren to EQ_07.
- EQ_09.ZIP or EQ_09.BAS
- This program adds support for a variable name table using fast hashing functions and installs two pre-defined values, one for PI and one for E, that can be used in expressions. These two symbols can be given in upper or lower case.
- EQ_10.ZIP or EQ_10.BAS
- This program adds further support for assignments statements, so you can assign values to your own named variables, and adds the ability to enter a list of statements and expressions to be calculated, separately. For example, you can enter: -3*PI;m=PI/3;SIN(m) and get three values printed. Upper and lower case have the same meaning, in this program. It also adds a preface telling about the program and a help command (?) that will list the pre-defined elements of the calculator.
All of these programs, those above and those demonstrated earlier, can be run using QBASIC. None of these are modularized or use features that aren't available in QBASIC. Since QBASIC is available with Microsoft operating systems (for Win9x based systems, on the CD-ROM under the oldmsdos subdirectory, where I usually just copy it to the \Windows\Command directory), it should be possible to try these out.
I've also added a short note on a page for the c programming language, which includes more sophisticated code for not only interpreting, but also compiling into push-pop code for faster execution of repeated expressions (for example, if you need to use an expression evaluator in a loop.) The link to the page carrying this subject matter is here.
Last updated: Wednesday, January 04, 2006 01:21