62

I'm searching for a simple way to evaluate a simple math expression from an string, like this:

3*2+4*1+(4+9)*6

I just want + and * operations plus ( and ) signs. And * has more priority than +.

0

7 Answers 7

52

One can try : http://partow.net/programming/exprtk/index.html

  1. very simple
  2. only need to include "exprtk.hpp" to your source code.
  3. you can change the value of variables of the expression dynamically.
  4. good starting point: http://partow.net/programming/exprtk/code/exprtk_simple_example_01.cpp
5
  • 19
    This should be the accepted answer! exprtk is really powerful and simple, worth trying first! Nov 13, 2016 at 19:17
  • out of all the files that I downloaded from the link, which ones are the bare minimum to include to use the library in a qt project? May 29, 2020 at 9:18
  • 2
    @mLstudent33: "only need to include "exprtk.hpp" to your source code." Sep 9, 2020 at 15:58
  • One drawback is that this only works with double, float or any type compatible with standard floating point type. This won't work with integers, for example.
    – blue_whale
    Nov 2, 2021 at 11:43
  • @blue_whale that is not true. You can define a custom numeric type that wraps an integer etc and then specialise the parser/expression types on that numeric type. github.com/ArashPartow/exprtk-custom-types Nov 5, 2021 at 9:36
39

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;
}
1
  • 4
    I don't think recursive decent is good for arithmetic as it's entirely left-recursive.
    – Pubby
    Feb 17, 2012 at 14:12
17

Just to add another alternative, consider trying TinyExpr for this problem. It's open source and self-contained in one source code file. It is actually written in C, but it will compile cleanly as C++ in my experience.

Solving your example expression from above is as simple as:

#include "tinyexpr.h"
#include <stdio.h>

int main()
{
    double answer = te_interp("3*2+4*1+(4+9)*6", 0);
    printf("Answer is %f\n", answer);
    return 0;
}
5

So I was searching an answer for this question. And I was trying to create my own programming language. For math expressions I was in need of that function.

Oke give I'll give it to you. Use it the way you want.

/* Code here before is useless now */

This is kind a long and probably an unefficient way of doing such a task. But it gets job done so go for it. Soon I'm planning on adding variable support. But you can do it too, it's pretty easy (I suppose :P).

EDIT: I just tidied up the function now it works like magic XD..

using namespace std;

double eval(string expr)
{
    string xxx; // Get Rid of Spaces
    for (int i = 0; i < expr.length(); i++)
    {
        if (expr[i] != ' ')
        {
            xxx += expr[i];
        }
    }

    string tok = ""; // Do parantheses first
    for (int i = 0; i < xxx.length(); i++)
    {
        if (xxx[i] == '(')
        {
            int iter = 1;
            string token;
            i++;
            while (true)
            {
                if (xxx[i] == '(')
                {
                    iter++;
                } else if (xxx[i] == ')')
                {
                    iter--;
                    if (iter == 0)
                    {
                        i++;
                        break;
                    }
                }
                token += xxx[i];
                i++;
            }
            //cout << "(" << token << ")" << " == " << to_string(eval(token)) <<  endl;
            tok += to_string(eval(token));
        }
        tok += xxx[i];
    }

    for (int i = 0; i < tok.length(); i++)
    {
        if (tok[i] == '+')
        {
            //cout << tok.substr(0, i) + " + " +  tok.substr(i+1, tok.length()-i-1) << " == " << eval(tok.substr(0, i)) + eval(tok.substr(i+1, tok.length()-i-1)) << endl;
            return eval(tok.substr(0, i)) + eval(tok.substr(i+1, tok.length()-i-1));
        } else if (tok[i] == '-')
        {
            //cout << tok.substr(0, i) + " - " +  tok.substr(i+1, tok.length()-i-1) << " == " << eval(tok.substr(0, i)) - eval(tok.substr(i+1, tok.length()-i-1)) << endl;
            return eval(tok.substr(0, i)) - eval(tok.substr(i+1, tok.length()-i-1));
        }
    }

    for (int i = 0; i < tok.length(); i++)
    {
        if (tok[i] == '*')
        {
            //cout << tok.substr(0, i) + " * " +  tok.substr(i+1, tok.length()-i-1) << " == " << eval(tok.substr(0, i)) * eval(tok.substr(i+1, tok.length()-i-1)) << endl;
            return eval(tok.substr(0, i)) * eval(tok.substr(i+1, tok.length()-i-1));
        } else if (tok[i] == '/')
        {
            //cout << tok.substr(0, i) + " / " +  tok.substr(i+1, tok.length()-i-1) << " == " << eval(tok.substr(0, i)) / eval(tok.substr(i+1, tok.length()-i-1)) << endl;
            return eval(tok.substr(0, i)) / eval(tok.substr(i+1, tok.length()-i-1));
        }
    }

    //cout << stod(tok.c_str()) << endl;
    return stod(tok.c_str()); // Return the value...
}
1
  • 2
    This code isn't working well with negative numbers. This ruins the order of operations and the functionality. I fixed by adding a simple rule to fix this else if (tok[i] == '-') { if (tok.substr(0, i).length() != 0 && tok[i - 1] != '*' && tok[i - 1] != '/') return eval(tok.substr(0, i)) + eval("-" + tok.substr(i + 1, tok.length() - i - 1)); } and changing - to + while passing the - to rest of evaluation so the order of operation doesn't break. May 26, 2021 at 18:50
2

While searching a library for a similar task I found libmatheval. Seems to be a proper thing. Unfortunately, GPL, which is unacceptable for me.

2

I've written a very simple expression evaluator in C# (minimal changes required to make it C++-compliant). It is based on expression tree building method, only that tree is not actually built but all nodes are evaluated in-place.

You can find it on this address: Simple Arithmetic Expression Evaluator

2

Convert your infix expression to postfix one. Then evaluate.

Postfix might look like 3 2 * 4 1 * + 4 9 + 6 * +

Evaluating that is very easy using stack.

Not the answer you're looking for? Browse other questions tagged or ask your own question.