15,663,876 members
Articles / Programming Languages / Visual Basic
Article
Posted 31 Mar 2003

365.5K views
106 bookmarked

# A Math Expression Evaluator

Rate me:
Math Expression Evaluator

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

 Letter Number Tab Space . Punctuation Operator 1 2 4 1 1 4 6 7 2 2 3 3 3 3 3 3 3 1 1 1 1 1 1 1 4 2 4 5 5 4 5 5 5 1 1 1 1 1 1 1 6 1 1 1 1 1 1 1 7 1 1 1 1 1 1 1

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.

Written By
Architect
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.

 First PrevNext
 Praise veen_rp24-Jun-14 19:54 veen_rp 24-Jun-14 19:54
 My vote of 5 amhy19-Apr-11 23:36 amhy 19-Apr-11 23:36
 7/3,5 = 2,3333333333 and 7/3.5= 0.2 ?????????? ciapal18-Nov-10 23:20 ciapal 18-Nov-10 23:20
 9/4.5 = 2,25? Kakskiv25-Jun-10 3:07 Kakskiv 25-Jun-10 3:07
 Re: 9/4.5 = 2,25? Cartesio30-Oct-10 0:16 Cartesio 30-Oct-10 0:16
 State table IamKepu3-Feb-10 10:13 IamKepu 3-Feb-10 10:13
 Wrong Result CodeProject_200814-Oct-08 9:46 CodeProject_2008 14-Oct-08 9:46
 Re: Wrong Result buraksarica25-Apr-11 2:00 buraksarica 25-Apr-11 2:00
 Decimal Problem saldarius20-Apr-08 8:36 saldarius 20-Apr-08 8:36
 Re: Decimal Problem Remy Blaettler24-Apr-12 23:01 Remy Blaettler 24-Apr-12 23:01
 Just what I am after can you use the "Enter" key to evaluate ? gearcam30-Jan-08 10:59 gearcam 30-Jan-08 10:59
 Re: Just what I am after can you use the "Enter" key to evaluate ? saldarius20-Apr-08 8:38 saldarius 20-Apr-08 8:38
 Equation Evaluator Anshul R16-Dec-07 23:37 Anshul R 16-Dec-07 23:37
 Anyone knows a good evaluator to solve equations ? eg. x+5=10
 Extending the parser for evaluating ternary operator pollirrata8-Jun-07 4:44 pollirrata 8-Jun-07 4:44
 letter then number transition state jokiz30-May-07 22:13 jokiz 30-May-07 22:13
 problem with decimal numbers scalpa9830-Apr-07 5:53 scalpa98 30-Apr-07 5:53
 Re: problem with decimal numbers Ruprt20-Aug-07 1:39 Ruprt 20-Aug-07 1:39
 Re: problem with decimal numbers Remy Blaettler24-Apr-12 23:01 Remy Blaettler 24-Apr-12 23:01
 Thanks it's very useful grantmasterb17-Nov-06 7:13 grantmasterb 17-Nov-06 7:13
 Re: Thanks it's very useful Ruprt19-Aug-07 9:09 Ruprt 19-Aug-07 9:09
 bug scalpa983-Nov-06 9:13 scalpa98 3-Nov-06 9:13
 Re: bug paulhumphris19-Jan-07 4:23 paulhumphris 19-Jan-07 4:23
 Rounding The Answer. mshariq5-Oct-06 0:35 mshariq 5-Oct-06 0:35
 Congratulation snort11-Sep-06 22:20 snort 11-Sep-06 22:20