Click here to Skip to main content
12,702,599 members (34,282 online)
Click here to Skip to main content
Add your own
alternative version


102 bookmarked

A Math Expression Evaluator

, 31 Mar 2003 CPOL
Rate this:
Please Sign up or sign in to vote.
Math Expression Evaluator


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.


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.


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


About the Author

Michael Combs
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.

You may also be interested in...

Comments and Discussions

Question7/3,5 = 2,3333333333 and 7/3.5= 0.2 ?????????? Pin
ciapal19-Nov-10 0:20
memberciapal19-Nov-10 0:20 

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.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170118.1 | Last Updated 1 Apr 2003
Article Copyright 2003 by Michael Combs
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid