Formula Evaluation – Expression Parsing

Yesterday I introduced the concept of evaluating a mathematical expression using a C# technique that converts the string to values and operations that can be performed. The code that performs the calculation uses expressions in the form of postfix notation (sometimes called Polish Notation) simplifying the calculation process.

One difficulty is that we are taught to write equations using infix notation.

For example

Infix 5 * 2

Postfix 5 2 *

To make the process more difficult you must execute the formula according to the order of precedence of the operations.

1 + 2 * 5 = 1 + (2 * 5)

This is simpler to define using postfix

1 2 5 * +

Postfix formulas are executing by processing each value in order. Each value or operation is processed sequentially. As each string is processed it follows the following process:

If it is a value it is placed on a value stack.

If it is an operation, two values are popped off the stack. The first is a variable to the right of the operation, and the seond is the variable to the left of the operation. The operation is performed on the two values, and the result is pushed back on the stack.

This sequence continues until all values have been processed and all operators are executed. Once completed the resutl of the entire formula remains on the stack.

So, how do you translate an infix formula into postfix form. The easiest way is to first convert the operands and operators into distinct items that may be organized into postfix notation. One problem is that users may add parentheses to overide the order of operations. A second problem is that users may use or not use spaces in the formula.

I have found it is easier to first parse the string and translate the results into a list of strings with each individual component. This works expecially well if the formula contains variables or numbers with more than one digit.

I like to translate the original equation into a list of bytes and evaluate them one byte at a time.

First I create a string accumulator for numbers and variables because they are the only items in the string that may consist of more than a single byte.

For each byte I perform the following logic

If the byte is any of the following characters * / – + ( ) or space

If the temporary number variable length > 0 then

Add it to the string list

Set the number accumulator to empty string

Add the current character to the string list

Else

Add the current character to the number accumulator

A formula such as: