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.
评论