Expression Evaluator (Postfix)

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

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).

Search DelphiForFun.org only

 

 

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:

bulletConvert 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, *}.
bulletOnce 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:

bullet AddVariable which receives a variable name and the value to substitute when the variable is referenced in an expression. 
bulletEvaluate 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 

bullet Download source
bullet Download  executable

Suggestions for Further Explorations

bullet Higher resolution variable values with a TVariables object.
bullet For efficiency, add a method to evaluate an expression multiple times with different variable values without rebuilding the Postfix list each time. 
bullet More operations, exponentiation for example.   

 

Original Date: November 21, 2007

Modified: July 29, 2017

 

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.