Click here to Skip to main content
Click here to Skip to main content

A Math Expression Evaluator

, 31 Mar 2003 CPOL
Rate this:
Please Sign up or sign in to vote.
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.

License

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

Share

About the Author

Michael Combs
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 Pinmemberveen_rp24-Jun-14 19:54 
GeneralMy vote of 5 Pinmemberamhy19-Apr-11 23:36 
Question7/3,5 = 2,3333333333 and 7/3.5= 0.2 ?????????? Pinmemberciapal18-Nov-10 23:20 
Question9/4.5 = 2,25? PinmemberKakskiv25-Jun-10 3:07 
AnswerRe: 9/4.5 = 2,25? PinmemberCartesio30-Oct-10 0:16 
QuestionState table PinmemberIamKepu3-Feb-10 10:13 
GeneralWrong Result PinmemberCodeProject_200814-Oct-08 9:46 
GeneralRe: Wrong Result Pinmemberburaksarica25-Apr-11 2:00 
QuestionDecimal Problem Pinmembersaldarius20-Apr-08 8:36 
AnswerRe: Decimal Problem PinmemberRemy Blaettler24-Apr-12 23:01 
QuestionJust what I am after can you use the "Enter" key to evaluate ? Pinmembergearcam30-Jan-08 10:59 
AnswerRe: Just what I am after can you use the "Enter" key to evaluate ? Pinmembersaldarius20-Apr-08 8:38 
GeneralEquation Evaluator Pinmemberpranav9516-Dec-07 23:37 
GeneralExtending the parser for evaluating ternary operator Pinmemberpollirrata8-Jun-07 4:44 
Questionletter then number transition state Pinmemberjokiz30-May-07 22:13 
Generalproblem with decimal numbers Pinmemberscalpa9830-Apr-07 5:53 
AnswerRe: problem with decimal numbers PinmemberRuprt20-Aug-07 1:39 
GeneralRe: problem with decimal numbers PinmemberRemy Blaettler24-Apr-12 23:01 
GeneralThanks it's very useful Pinmembergrantmasterb17-Nov-06 7:13 
GeneralRe: Thanks it's very useful PinmemberRuprt19-Aug-07 9:09 
Generalbug Pinmemberscalpa983-Nov-06 9:13 
GeneralRe: bug Pinmemberpaulhumphris19-Jan-07 4:23 
QuestionRounding The Answer. Pinmembermshariq5-Oct-06 0:35 
GeneralCongratulation Pinmembersnort11-Sep-06 22:20 
QuestionPlease Help, just trying to add an X PinmemberBrad Galloway4-Sep-06 15:00 
AnswerRe: Please Help, just trying to add an X [modified] Pinmembernim5220-Sep-06 10:33 
GeneralEXP and Error Handling PinmemberPeter Verijke7-Jun-06 10:25 
QuestionExtending the Parser to Simplify Expressions PinmemberJasonSG26-Nov-05 10:25 
QuestionAdditional Functions PinmemberJasonSG25-Nov-05 7:48 
GeneralCode extension: Formulas with variables inside PinmemberPanzermeyer18-Aug-05 2:09 
GeneralIIf statements... PinmemberJPamental27-Jul-05 8:39 
GeneralRe: IIf statements... Pinmemberjokiz25-Sep-06 16:54 
QuestionWhat should I do if... Pinmemberviettho4-Jun-04 8:34 
GeneralReadability Suggestions PinmemberJimHugh2-Feb-04 9:55 
GeneralNull value Pinmembergadish@log-on.com1-Feb-04 7:21 
GeneralCompact Framework Problem "BinarySearch" PinsussCarter Barnes13-Jan-04 11:48 
GeneralRe: Compact Framework Problem "BinarySearch" PinmemberMichael Combs14-Jan-04 18:33 
GeneralRe: Compact Framework Problem "BinarySearch" PinsussJohn M-W24-Feb-04 13:54 
Generalsteady decline of memory PinsussAnonymous3-Nov-03 23:11 
GeneralRe: steady decline of memory PinsussAnonymous4-Nov-03 4:07 
Generallog10 PinmemberSerena_Sutton16-Oct-03 3:27 
GeneralRe: log10 PinmemberMichael Combs16-Oct-03 4:23 
GeneralC++ PinmemberA M Ginsberg24-Aug-03 21:56 
Questiondecimal numbers? PinsussTheDoc1-Aug-03 9:49 
AnswerRe: decimal numbers? PinmemberMichael Combs1-Aug-03 9:55 
GeneralRe: decimal numbers? PinsussTheDoc1-Aug-03 10:23 
GeneralRe: decimal numbers? PinmemberMichael Combs1-Aug-03 10:30 
GeneralRe: decimal numbers? PinsussTheDoc1-Aug-03 10:50 
GeneralRe: decimal numbers? Pinmemberdeveloperl24-May-04 7:09 
GeneralRe: decimal numbers? Handling Culture PinmemberPiotrek9116-Oct-04 21:47 

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

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

| Advertise | Privacy | Mobile
Web01 | 2.8.141022.2 | Last Updated 1 Apr 2003
Article Copyright 2003 by Michael Combs
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid