Search
As of October, 2016, Embarcadero is offering a free release
of Delphi (Delphi
10.1 Berlin Starter Edition ). There
are a few restrictions, but it is a welcome step toward making
more programmers aware of the joys of Delphi. They do say
"Offer may be withdrawn at any time", so don't delay if you want
to check it out. Please use the
feedback link to let
me know if the link stops working.
Support DFF - Shop
If you shop at Amazon anyway, consider
using this link.
We receive a few cents from each
purchase. Thanks
Support DFF - Donate
If you benefit from the website, in terms of
knowledge, entertainment value, or something otherwise useful,
consider making a donation via PayPal to help defray the
costs. (No PayPal account necessary to donate via credit
card.) Transaction is secure.
Mensa®
Daily Puzzlers
For over 15 years
Mensa Page-A-Day calendars have provided several puzzles a year
for my programming pleasure. Coding "solvers" is most fun,
but many programs also allow user solving, convenient for "fill
in the blanks" type. Below are Amazon links to the
two most recent years.
Mensa®
365 Puzzlers Calendar 2017
Mensa®
365 Puzzlers Calendar 2018
(Hint: If you can
wait, current year calendars are usually on sale in January.)
Contact
Feedback:
Send an
e-mail with your comments about this program (or anything else).
|
| |
Problem Description
A program to illustrate the use of the
"Postfix" notation to simplify the evaluation of arithmetic
expressions. Postfix notation is a way to write arithmetic expressions
that simplifies their evaluation by computers. All parentheses are
removed and each operation or function is preceded by the values that it
needs.
Background & Techniques
I had used the Postfix data structure previously in
programs (Brute Force for
example), but was surprised to find that I had not created an object to
simplify its use in a more general sense. I recently posted a program
to analyze "age type" story problems and produce the equations which
solve the problem. To actually solve the equations will require an
expression evaluator. This program provides one.
Postfix is also referred to as Reverse Polish
Notation (RPN). RPN was probably the original name, because a Polish
mathematician (whose name escapes me) developed it. Wikipedia has a
good Postfix article under "Reverse Polish Notation".
Evaluating an expression using the Postfix
structure is a two phase process:
 | Convert the input expression in "infix"
notation, (the way we normally write expressions), to a list of items in Postfix notation. Infix separates
variables and partial results defined by parentheses by operations such
as plus (+), minus (-), multiply (*), and divide (/)
operations. In Postfix form, each binary operation applies to the
the two operands which precede it. While building the Postfix list, the
implied priority of operations must be honored (multiplications and
divisions are performed before additions and subtractions) as well as
honoring the use of parentheses to specify phrases to be evaluated
first. So, for example, a+b*c is evaluated by multiplying
b*c first and then adding a and the b*c product but
(a+b)*c is evaluated by adding a and b and then
multiplying that sum by c. In postfix form, a+b*c
==> {a, b, c, *, + } and (a+b)*c ==> {a,
b, +, c, *}. |
| Once the Postfix list is built,
evaluation proceeds by moving from left to right, replacing each
operation and the two numbers preceding it with the result of performing
the computation implied by the operation (add, subtract, multiply,
divide). |
The program allows the user to define a set of
variables and their values in one box and the expressions to be evaluated in
another. The "Evaluate" button displays the results in a third box.
A "Show Solving Steps" checkbox displays the calculation process step by
step.
Non-programmers are welcome to read on, but may
want to skip to the bottom of this page to download
executable version of the program.
Notes for programmers
The program uses a TEval object to implement
the evaluation. The two mandatory methods to call are:
| AddVariable which receives a variable
name and the value to substitute when the variable is referenced in an
expression. |
| Evaluate which is passed a text string and
returns the value of the expression. If the Evaluate function
returns false, a call may be made to GetLastError to retrieve the
text message describing problem found in the expression. |
TOpObj is a simple object containing the information about each
item in the PostFixList. A Tokentype field specifies
whether the items is a variable, a constant or an operation. For
constants, the value is contained here, for variables, the object contains
the index of the variable in a separate Variables list.
For an operation, the operator type is included.
Both phases of the evaluation make use of a
temporary stack area. A "stack" is a last-in, first-out (LIFO) list of
items and provides an easy way to reverse the order by using "push" and
"pop" operations. "Push" adds an item to the list, "Pop" retrieves the
last item added it and removes it from list. TEval
simulates push and pop using an array (AStack) of TOpObj
objects with a counter, SCount. An item from the Postfix list
is added by incrementing SCount and AStack[SCount] to the object being
added. Pop sets the retrieved item to AStack[SCount] and decrements SCount.
One potentially confusing "trick" used is to store
the variable value in the Objects property field of the Variables Tstringlist. The
Objects property normally holds a pointer to an object
to be associated with each string in the list. Floating point type
Single is
4 bytes in length and by typecasting can be stored and retrieved with each
in the Objects property for each
variable defined. The better solution would be to define a
TVariable object containing the values as type Extended
and using Objects entries to hold pointers to these value objects.
There is a lot more that could be said about TEval,
but grandkids (and kids) are arriving this afternoon for Thanksgiving
celebrations, so I'll let those interested study the code and write with
specific questions/suggestions.
Running/Exploring the Program
Suggestions for Further Explorations
 |
Higher
resolution variable values with a TVariables object. |
|
|
For efficiency,
add a method to evaluate an expression multiple times with different
variable values without rebuilding the Postfix list each time.
|
|
|
More operations,
exponentiation for example.
|
|
Original Date: November 21, 2007 |
Modified:
May 15, 2018 |
|
|
