Click here to Skip to main content
15,867,686 members
Articles / Programming Languages / Visual Basic
Article

A Math Expression Evaluator

Rate me:
Please Sign up or sign in to vote.
4.87/5 (57 votes)
31 Mar 2003CPOL6 min read 374.5K   4.4K   106   75
Math Expression Evaluator

Image 1

Introduction

A mathematical expression evaluator can be a useful piece of code if you often write applications which rely on any kind of scripting. Graphics applications which create composite images from templates, form filling or spreadsheet software which performs configurable calculations based on user input, or data analysis applications that perform calculations on batch data from scripts are just a few that come to my mind.

Some knowledge of lexical analysis, state machines and parsing would be helpful, but not necessary. The brief discussion here and a little experimentation with the code in the debugger, should hopefully provide adequate explanation to at least get started using the code.

Lexical scanning

The first step in evaluating an expression is to identify the individual components, or tokens, of the expression. This evaluator uses a finite state machine based lexical scanner to identify tokens, assigning each a category such as number, operator, punctuation, or function. A state machine uses a set of predefined rules to make transitions between states, based on the current state and input (characters from a buffer). It will eventually reach an end state (let's hope), at which point, end state specific code can be executed. In this case, an end state signals that a token has been found, and end state specific code identifies it within the input buffer and stores it to a list of tokens.

State machines are typically driven by a table like the one below, which is used in the code presented in this article. The state is indicated on each row, and the column is determined by the input character. The end states are those states in which all entries are 1. When one of these end states is reached, the code, having tracked it's start position and it's current position, cuts out the token from the buffer, stores it to a list with an associated type (number, operator, etc.) and then returns to the start state, state one.

For example, lets start with a buffer of "73 " (a space is added as an end marker). The transition would be as follows: From State 1, an input of 7 (number) indicates a move to state 4. From state 4, an input of 3 (number) indicates staying in state 4. From state 4, an input of ' ' (space) indicates a move to state 5. State 5 is the end state for a number. At this point the number 73 has been identified, which would then be stored in a list of tokens.

 LetterNumberTabSpace.PunctuationOperator
12411467
22333333
31111111
42455455
51111111
61111111
71111111

You might have noticed a little cheating on the column marked Operator. Ordinarily, each operator might have its own column, directing the state machine when that operator character is input. However, single character operators can be combined, provided that some special handling to set the column correctly, is added to the code. This was done so that new operators could easily be added without any modification to the state table. More on this later.

Parsing and evaluation

Once a list of tokens has been generated, each assigned an appropriate type (operator, number, etc), the expression is parsed and evaluated. Parsing verifies the syntax of the expression, restructures the expression to account for operator precedence and, in this case, also evaluates the expression. This code uses a relatively simple recursive descent parsing algorithm.

Recursive descent parsing is implemented through a series of recursive functions, each function handling a different portion of the syntax of an expression. The virtue of recursive decent parsing is that, it is easy to implement. The primary drawback though is that, the language of the expression, math in this case, is hard coded into the structure of the code. As a consequence, a change in the language often requires that the code itself be modified. There are standard parsing algorithms driven by tables, rather than functions, but typically require additional software to generate portions of the code and the tables, and can require much greater effort to implement.

However, the recursive descent parser used in this code has been written in a manner that will allow language modifications typical of those in math expressions (functions and operators), with no changes to the structure of the code.

Adding new operators and functions

This code handles most of the basic operators and functions normally encountered in an expression. However, adding support for additional operators and functions can be implemented simply.

The recursive descent parsing functions have been coded in a series of levels, each level handling operators of a particular precedence, associativity (left, or right) and what might be referred to as degree (unary, or binary). There are 3 levels of precedence (level1, level2 and level3) for binary, left associative operators. By default, level1 handles addition and subtraction (+,-), level2 handles multiplicative operands (*, /, %, \) and level three handles exponents (^). Adding a new operator at any of these levels requires 2 steps. One is to modify the init_operators function to include a symbol for the new operator, specifying the precedence level and the character denoting the operation. Only single character operators can be added without additional changes to the lexical scanner. The second step is to modify the calc_op function to handle the operation, which should become clear once in the code. Level4 handles right associative unary operators (-, + i.e. negation, etc.) and level5 handles left associative unary operators (! factorials). The process to add new operators at these levels is the same as above.

The addition of functions is equally simple. The new function name must first be added to the m_funcs array which is initialized in the declarations of the mcCalc class. Then the calc_function function must be modified to perform the function operation. Function arguments are passed to the calc_function function in a collection. The parser simple passes in the number of comma delimited values it finds enclosed in parenthesis, following the function. The calc_function function is responsible for removing the number of arguments required for the function, and generating any errors when an incorrect number of arguments is passed. Variable length argument lists can even be implemented by simply indicating the number of function arguments in the first argument.

Points of interest

There are several interesting modifications to this code that could provide additional utility. Variable identifiers and substitution could also be of use to those needing a more thorough evaluation tool. Support for caller defined functions or operators through the use of delegates would be a nice addition for anyone interested in using this code as an external assembly. There are certainly more, and any suggestions or modifications for such are welcome. Hopefully this code will prove useful to you in it's application or at least in it's explanation of some of the principles behind expression evaluation.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Architect
United States United States
Michael has been developing software for about 19 years primarily in C#, C/C++, Fortran, and Visual Basic. His previous experience includes Internet data services (communication protocols, data storage and GIS) for the mortgage industry, oil platform instrumentation and explosives simulation and testing. He holds a B.S. in astrophysics and computer science. He is currently working for Global Software in Oklahoma City developing law enforcement and emergency services related software.

Comments and Discussions

 
GeneralPraise Pin
veen_rp24-Jun-14 19:54
professionalveen_rp24-Jun-14 19:54 
Very usefull
GeneralMy vote of 5 Pin
amhy19-Apr-11 23:36
amhy19-Apr-11 23:36 
Question7/3,5 = 2,3333333333 and 7/3.5= 0.2 ?????????? Pin
ciapal18-Nov-10 23:20
ciapal18-Nov-10 23:20 
Question9/4.5 = 2,25? Pin
Kakskiv25-Jun-10 3:07
Kakskiv25-Jun-10 3:07 
AnswerRe: 9/4.5 = 2,25? Pin
Cartesio30-Oct-10 0:16
Cartesio30-Oct-10 0:16 
QuestionState table Pin
IamKepu3-Feb-10 10:13
IamKepu3-Feb-10 10:13 
GeneralWrong Result Pin
CodeProject_200814-Oct-08 9:46
CodeProject_200814-Oct-08 9:46 
GeneralRe: Wrong Result Pin
buraksarica25-Apr-11 2:00
buraksarica25-Apr-11 2:00 
QuestionDecimal Problem Pin
saldarius20-Apr-08 8:36
saldarius20-Apr-08 8:36 
AnswerRe: Decimal Problem Pin
Remy Blaettler24-Apr-12 23:01
Remy Blaettler24-Apr-12 23:01 
QuestionJust what I am after can you use the "Enter" key to evaluate ? Pin
gearcam30-Jan-08 10:59
gearcam30-Jan-08 10:59 
AnswerRe: Just what I am after can you use the "Enter" key to evaluate ? Pin
saldarius20-Apr-08 8:38
saldarius20-Apr-08 8:38 
GeneralEquation Evaluator Pin
Anshul R16-Dec-07 23:37
Anshul R16-Dec-07 23:37 
GeneralExtending the parser for evaluating ternary operator Pin
pollirrata8-Jun-07 4:44
pollirrata8-Jun-07 4:44 
Questionletter then number transition state Pin
jokiz30-May-07 22:13
jokiz30-May-07 22:13 
Generalproblem with decimal numbers Pin
scalpa9830-Apr-07 5:53
scalpa9830-Apr-07 5:53 
AnswerRe: problem with decimal numbers Pin
Ruprt20-Aug-07 1:39
Ruprt20-Aug-07 1:39 
GeneralRe: problem with decimal numbers Pin
Remy Blaettler24-Apr-12 23:01
Remy Blaettler24-Apr-12 23:01 
GeneralThanks it's very useful Pin
grantmasterb17-Nov-06 7:13
grantmasterb17-Nov-06 7:13 
GeneralRe: Thanks it's very useful Pin
Ruprt19-Aug-07 9:09
Ruprt19-Aug-07 9:09 
Generalbug Pin
scalpa983-Nov-06 9:13
scalpa983-Nov-06 9:13 
GeneralRe: bug Pin
paulhumphris19-Jan-07 4:23
paulhumphris19-Jan-07 4:23 
QuestionRounding The Answer. Pin
mshariq5-Oct-06 0:35
mshariq5-Oct-06 0:35 
GeneralCongratulation Pin
snort11-Sep-06 22:20
snort11-Sep-06 22:20 
QuestionPlease Help, just trying to add an X Pin
Brad Galloway4-Sep-06 15:00
Brad Galloway4-Sep-06 15:00 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.