tags:

views:

332

answers:

4

I am looking for a C++ class I can incorporate into a project I am working on. the functionality I need is evaluation of string operations to numerical form: for example "2 + 3*7" should evaluate to 23.

I do realize what I am asking is a kind of an interpreter, and that there are tools to build them, by my background in CS is very poor so I would appreciate if you can point me to a ready made class .

+4  A: 

This should do exactly what you want. You can test it live at: http://www.wowpanda.net/calc

It uses Reverse Polish Notation and supports:

  • Operator precedence (5 + 5 * 5 = 30 not 50)
  • Parens ((5 + 5) * 5 = 50)
  • The following operators: +, -, *, /

EDIT: you'll probably want to remove the Abs() at the bottom; for my needs 0 - 5 should be 5 and not -5!

static bool Rpn(const string expression, vector<string> &output)
{
    output.clear();
    char *end;
    vector<string> operator_stack;
    bool expecting_operator = false;

    for (const char *ptr = expression.c_str(); *ptr; ++ptr) {
     if (IsSpace(*ptr))
      continue;

     /* Is it a number? */
     if (!expecting_operator) {
      double number = strtod(ptr, &end);
      if (end != ptr) {
       /* Okay, it's a number */
       output.push_back(boost::lexical_cast<string>(number));
       ptr = end - 1;
       expecting_operator = true;
       continue;
      }
     }

     if (*ptr == '(') {
      operator_stack.push_back("(");
      expecting_operator = false;
      continue;
     }

     if (*ptr == ')') {
      while (operator_stack.size() && operator_stack.back() != "(") {
       output.push_back(operator_stack.back());
       operator_stack.pop_back();
      }

      if (!operator_stack.size())
       return false; /* Mismatched parenthesis */

      expecting_operator = true;
      operator_stack.pop_back(); /* Pop '(' */
      continue;
     }

     if (*ptr == '+' || *ptr == '-') {
      while (operator_stack.size() && IsMathOperator(operator_stack.back())) {
       output.push_back(operator_stack.back());
       operator_stack.pop_back();
      }

      operator_stack.push_back(boost::lexical_cast<string>(*ptr));
      expecting_operator = false;
      continue;
     }

     if (*ptr == '*' || *ptr == '/') {
      while (operator_stack.size() && (operator_stack.back() == "*" || operator_stack.back() == "/")) {
       output.push_back(operator_stack.back());
       operator_stack.pop_back();
      }

      operator_stack.push_back(boost::lexical_cast<string>(*ptr));
      expecting_operator = false;
      continue;
     }

     /* Error */
     return false;
    }

    while (operator_stack.size()) {
     if (!IsMathOperator(operator_stack.back()))
      return false;

     output.push_back(operator_stack.back());
     operator_stack.pop_back();
    }

    return true;
} // Rpn

/***************************************************************************************/

bool Calc(const string expression, double &output)
{
    vector<string> rpn;

    if (!Rpn(expression, rpn))
     return false;

    vector<double> tmp;
    for (size_t i = 0; i < rpn.size(); ++i) {
     if (IsMathOperator(rpn[i])) {
      if (tmp.size() < 2)
       return false;
      double two = tmp.back();
      tmp.pop_back();
      double one = tmp.back();
      tmp.pop_back();
      double result;

      switch (rpn[i][0]) {
       case '*':
        result = one * two;
        break;

       case '/':
        result = one / two;
        break;

       case '+':
        result = one + two;
        break;

       case '-':
        result = one - two;
        break;

       default:
        return false;
      }

      tmp.push_back(result);
      continue;
     }

     tmp.push_back(atof(rpn[i].c_str()));
     continue;
    }

    if (tmp.size() != 1)
     return false;

    output = Abs(tmp.back());
    return true;
} // Calc

/***************************************************************************************/
Andreas Bonini
Ahh rpn. How I do <3 thee.
GrayWizardx
Maybe I'm being silly, but why is "5 + 5 * 5 = 15 not 20"?
GMan
Because I fail at basic math (the calculator works fine though, I apparently don't).. Edited my post
Andreas Bonini
Ha, ok, I feel better. :P
GMan
How in the world would "5 + 5 * 5" = 20 (or 15)? By normal precedence rules, that's (5*5)+5, which should be 30. If you reverse the precedence, it become "(5 + 5) * 5", which should give 50...
Jerry Coffin
@Jerry Coffin: Read the comments above..
Andreas Bonini
`ouput.empty()` should probably be `output.clear()`.
avakar
@avakar: err, yes, thanks
Andreas Bonini
@GrayWizardx, don't you mean "How I thee <3 do"?
Eric
A: 

C++ in Action, in addition to being a great book on C++, includes a fully working calculator, doing what you need (and actually much more). And the book is available for free online

Eli Bendersky
+3  A: 

boost::spirit comes with a calculator example which would do what you need: http://www.boost.org/doc/libs/1%5F33%5F1/libs/spirit/example/fundamental/ast%5Fcalc.cpp

aneccodeal
+1  A: 

muParser is written in C++ and does just what you need.

mcdave