Evaluating Arithmetic Expressions from String in C++

Evaluating arithmetic expressions from string in C++

I think you're looking for a simple recursive descent parser.

Here's a very simple example:

const char * expressionToParse = "3*2+4*1+(4+9)*6";

char peek()
{
    return *expressionToParse;
}

char get()
{
    return *expressionToParse++;
}

int expression();

int number()
{
    int result = get() - '0';
    while (peek() >= '0' && peek() <= '9')
    {
        result = 10*result + get() - '0';
    }
    return result;
}

int factor()
{
    if (peek() >= '0' && peek() <= '9')
        return number();
    else if (peek() == '(')
    {
        get(); // '('
        int result = expression();
        get(); // ')'
        return result;
    }
    else if (peek() == '-')
    {
        get();
        return -factor();
    }
    return 0; // error
}

int term()
{
    int result = factor();
    while (peek() == '*' || peek() == '/')
        if (get() == '*')
            result *= factor();
        else
            result /= factor();
    return result;
}

int expression()
{
    int result = term();
    while (peek() == '+' || peek() == '-')
        if (get() == '+')
            result += term();
        else
            result -= term();
    return result;
}

int _tmain(int argc, _TCHAR* argv[])
{

    int result = expression();

    return 0;
}

evaluate an arithmetic expression stored in a string (C#)

There's a javascript library you can reference, then just do something like:

var engine = VsaEngine.CreateEngine();
Eval.JScriptEvaluate(mySum, engine);

Edit;
Library is Microsoft.JScript

How to evaluate a mathematical expression using strings and arrays in C

Look into the shunting yard algorithm and convert the string into reverse polish notation.

It will help if you also separate out number detection from symbol detection by reading the string one character at a time instead of just jumping to the operators.

After that, it is rather easy to perform the computation, as the inputs are ordered in a manner that makes a stack based calculator easy to implement.

Yes, you could do a full fledged recursive descent parser; but, for the relatively simple matter of algebraic expressions, they are overkill.

--- Edited because I see that there's controversy over tools vs techniques ---

I see a lot of people mentioning lexx and yacc. They are great tools, they are also overkill for what you need. It's like saying to open a carpentry shop when you want to replace a board on your fence. You don't need to learn another language to handle your math language, and lexx and yacc will require you to learn their domain specific configuration language to build the parser for your domain specific language. That's a lot of languages for a simple, solved problem.

Lexx and Yacc are great if you want to build a mathematical tree of your data; however, RPN is a mathematical tree of your data stored in a list of two fundamental node types (data) and (operation).

(a)(b)(c) // three "data nodes"
(a)(b)(+) // two "data nodes" and one operation node.

This allows one to use a stack based machine (very easy to implement). The machine has an "instruction set" of

 if (x is data) { push X onto the top of the stack }
 if (x is operation) {
   pop the operation's required parameters.
   pass them to the operation.
   push the result on the stack
 }

so assuming you had a '+' operator, the expression 3 + 5 + 6 would convert to RPN 3 5 + 6 + and the stack would look like (during processing)

 <empty>
 (3)
 (3)(5)
 (8)
 (8)(6)
 (14)

The primary reason to convert to RPN is not because it's necessary, it's because it makes the rest of your program much easier to implement. Imagine 3 + 5 * 7 converted to RPN, you have 3 5 7 * + which means that you don't have to do anything special with evaluation "machine" language. Note that (3 + 5) * 7 converts to RPN 3 5 + 7 *. In short, you reduce the complexity of the evaluation engine by massaging your input data to be less ambiguous.

Lexx and Yacc provide a lot of "configurability" to allow you to accomplish the same thing; however, you are not going to be configuring lexx and yacc to do anything special here, so the configurable interface doesn't buy you much. It's like having a multiple selection knob when you only need an on-off switch.

Now, if you want to build any kind of parser, where you are not aware of any kind of future rules which might be added; then definately choose lexx and yacc. But a simple algebraic expression parser is far too "solved" a problem to bring in the big guns. Use a shunting algorthim and break your problem down into

simple scanner to identify the main types of "tokens", NUMBER, +, -, /, *, (, and )
shunting algorithim to convert the "list" of tokens into a RPN list
a stack to hold the "memory" of the evaluation "machine"
the "machine" pull / push / evaluate loop

This has the added benefits of being able to develop the pieces independently, so you can verify each step without the entire framework being in place. Lexx and Yacc promote adding your code to their framework, so unless you take steps to do otherwise, you might have to debug the entire thing as one big piece.

What is the best way to evaluate mathematical expressions in C++?

Boost.Spirit is a C++ parser library.

Examples:

• in its distribution: classic version and current version (look for "calc");
• on Rosetta wiki;
• some applications using it.

(C++) Parse tree for evaluating simple arithmetic expressions returning incorrect value

The problem is that you are doing calculations with characters and not with integers. As you might know each character has a Ascii-code, a numerical representation of this character, which is used for calculations. Ascii codes for '5', '2' and '7' are 53, 50 and 55.

Thus '5' + '2' * '7' is indeed 2083, because it's actually 53 + 50 * 55.

A simple fix would be to replace

return tree -> get_root();

in eval_parse_tree with

return tree -> get_root() - '0';

---

Related Topics