Introduction: Writing a simple expression evaluator

Let's make an expression evaluator that takes strings like "2 * 3 + 1.5", evaluates them, and returns the result (7.5). The four arithmetic operators and parentheses are allowed in the expression. You can use this simple program instead of your desktop calculator, or you can embed it in a larger application (for example, it can be useful in accounting software).

You may think about reading an expression sequentially and do the calculations (for the example above: 2 * 3 = 6, then 6 + 1.5 = 7.5). But, if you do so, you will get wrong results for expressions like "3 – 1 / 2" or "1 + 3 * (25 – 4)". The operators have different priorities; that's why you need a more complex algorithm.

Recursive descent parsing

A popular approach (called recursive descent parsing) views an expression as a hierarchical structure. On the top level, an expression consists of several summands:

Summands are separated by "+" and "–" signs. They include single numbers (1.5, 2, 8) and more complex expressions [3.4 * (25 – 4) / 2]. (Strictly speaking, 8 is not a summand here, but a subtrahend. For the purposes of this article, we will refer to the parts of expression separated by "–" as summands, though a mathematician would say it's a misnomer.)

Each summand, in turn, consist of several factors (we will call "factors" the things separated by "*" and "/"):

The summand "1.5" can be viewed as a degenerated case: it constists of one factor, 1.5. The summand "3.4 * (25 – 4) / 2" consists of three factors.

There are 2 types of factors: atoms and subexpressions in parenthesis. In our simple expression evaluator, an atom is just a number (in more complex translators, atoms can also include variable names). Subexpressions can be parsed in the same way as the whole expression (you again found the summands inside the brackets, then factors, and then atoms).

So, we have an hierarchy, where atoms constitute the lowest level, then they are combined into factors, and the factors are combined into summands. A natural way to parse such hierarchical expression is to use recursion:

double ParseAtom(char*& expr) {
    // Read the number from string
    char* end_ptr;
    double res = strtod(expr, &end_ptr);
    // Advance the pointer and return the result
    expr = end_ptr;
    return res;
}

// Parse multiplication and division
double ParseFactors(char*& expr) {
    double num1 = ParseAtom(expr);
    for(;;) {
        // Save the operation
        char op = *expr;
        if(op != '/' && op != '*')
            return num1;
        expr++;
        double num2 = ParseAtom(expr);
        // Perform the saved operation
        if(op == '/')
            num1 /= num2;
        else
            num1 *= num2;
    }
}

// Parse addition and subtraction
double ParseSummands(char*& expr) {
    double num1 = ParseFactors(expr);
    for(;;) {
        char op = *expr;
        if(op != '-' && op != '+')
            return num1;
        expr++;
        double num2 = ParseFactors(expr);
        if(op == '-')
            num1 -= num2;
        else
            num1 += num2;
    }
}

double EvaluateTheExpression(char* expr) {
    return ParseSummands(expr);
};

The hierarchical structure is directly reflected in this code.

Comments to the code

We need to save the operation, because we cannot calculate the result when the second operand is still unknown (e.g., you cannot evaluate "2*3" when you have read only "2*"). The for(;;) loop allows us to parse several summands, e.g., in "1+2+3".

The program uses double data type, which is okay for most applications. If you want to use this code for accounting, you should change to fixed-point data type. Don't use floating-point arithmetic when dealing with money. (If you need an explanation, read about Currency type in Visual Basic 6.0. Also peruse this example in C# and this article from IBM.)

Error handling, parentheses and unary minus parsing are also added to the program below. Only three error messages are used: "parentheses don't match", "invalid character", and "division by zero". When the interpreter sees an unexpected character anywhere, it returns the "invalid character" error code. The position in string where the error occurred is also shown. If there are several errors, only one of them will be reported.

Download the expression evaluator, 40 KB

Recommended reading

• Recursive decent parsing at Wikipedia. A formal definition of the term.
• Jack Crenshaw's tutorial
• "The C++ Programming Language" by Stroustrup has a chapter on expression evaluators.