Solved

String calculator in c or c++

Posted on 2000-03-09
19
859 Views
Last Modified: 2010-04-02
Hi,
I need to implement a calculator
that parse a string and give me
a formula that will be used
on a large number of records it must be fast and afisiant.

Where can i find such a thing ?

            Thanks Uri.
0
Comment
Question by:uritwig
  • 6
  • 6
  • 2
  • +4
19 Comments
 
LVL 7

Expert Comment

by:KangaRoo
ID: 2600044
Can you give a bit more details. what I read is that you want to parse a string, create a sort of function from that and apply that function to a large data set?
0
 

Expert Comment

by:jamanat
ID: 2600081
Hey, please be more clear. what ever i understood is you need a formula to parse a string.???? what do u actually want to do? please give the details.
0
 
LVL 22

Expert Comment

by:nietod
ID: 2600182
/* +++Date last modified: 05-Jul-1997 */



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

/*                                                                      */

/*  EVAL.C - A simple mathematical expression evaluator in C            */

/*                                                                      */

/*  operators supported: Operator               Precedence              */

/*                                                                      */

/*                         (                     Lowest                 */

/*                         )                     Highest                */

/*                         +   (addition)        Low                    */

/*                         -   (subtraction)     Low                    */

/*                         *   (multiplication)  Medium                 */

/*                         /   (division)        Medium                 */

/*                         \   (modulus)         High                   */

/*                         ^   (exponentiation)  High                   */

/*                         sin(                  Lowest                 */

/*                         cos(                  Lowest                 */

/*                         atan(                 Lowest                 */

/*                         abs(                  Lowest                 */

/*                         sqrt(                 Lowest                 */

/*                         ln(                   Lowest                 */

/*                         exp(                  Lowest                 */

/*                                                                      */

/*  constants supported: pi                                             */

/*                                                                      */

/*  Original Copyright 1991-93 by Robert B. Stout as part of            */

/*  the MicroFirm Function Library (MFL)                                */

/*                                                                      */

/*  The user is granted a free limited license to use this source file  */

/*  to create royalty-free programs, subject to the terms of the        */

/*  license restrictions specified in the LICENSE.MFL file.             */

/*                                                                      */

/*  Requires RMALLWS.C, also in SNIPPETS.                               */

/*                                                                      */

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



#include <stdlib.h>

#include <string.h>

#include <ctype.h>

#include <math.h>

#include "sniptype.h"

#include "snip_str.h"                     /* For rmallws(), strupr()    */

#include "snipmath.h"

#include "numcnvrt.h"



/*

**  Other SNIPPETS functions

*/



char *rmallws(char *);

char *strupr(char *);





struct operator {

      char        token;

      char       *tag;

      size_t      taglen;

      int         precedence;

};



static struct operator verbs[] = {

      {'+',  "+",       1, 2 },

      {'-',  "-",       1, 3 },

      {'*',  "*",       1, 4 },

      {'/',  "/",       1, 5 },

      {'\\', "\\",      1, 5 },

      {'^',  "^",       1, 6 },

      {'(',  "(",       1, 0 },

      {')',  ")",       1, 99},

      {'S',  "SIN(",    4, 0 },

      {'C',  "COS(",    4, 0 },

      {'A',  "ABS(",    4, 0 },

      {'L',  "LN(",     3, 0 },

      {'E',  "EXP(",    4, 0 },

      {'t',  "ATAN(",   5, 0 },

      {'s',  "SQRT(",   5, 0 },

      {NUL,  NULL,      0, 0 }

};



static char   op_stack[256];                    /* Operator stack       */

static double arg_stack[256];                   /* Argument stack       */

static char   token[256];                       /* Token buffer         */

static int    op_sptr,                          /* op_stack pointer     */

              arg_sptr,                         /* arg_stack pointer    */

              parens,                           /* Nesting level        */

              state;                            /* 0 = Awaiting expression

                                                   1 = Awaiting operator

                                                */

const double Pi = 3.14159265358979323846;



static int              do_op(void);

static int              do_paren(void);

static void             push_op(char);

static void             push_arg(double);

static int              pop_arg(double *);

static int              pop_op(int *);

static char            *get_exp(char *);

static struct operator *get_op(char *);

static int              getprec(char);

static int              getTOSprec(void);



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

/*                                                                      */

/*  evaluate()                                                          */

/*                                                                      */

/*  Evaluates an ASCII mathematical expression.                         */

/*                                                                      */

/*  Arguments: 1 - String to evaluate                                   */

/*             2 - Storage to receive double result                     */

/*                                                                      */

/*  Returns: Success_ if successful                                     */

/*           Error_ if syntax error                                     */

/*           R_ERROR if runtime error                                   */

/*                                                                      */

/*  Side effects: Removes all whitespace from the string and converts   */

/*                it to U.C.                                            */

/*                                                                      */

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



int evaluate(char *line, double *val)

{

      double arg;

      char *ptr = line, *str, *endptr;

      int ercode;

      struct operator *op;



      strupr(line);

      rmallws(line);

      state = op_sptr = arg_sptr = parens = 0;



      while (*ptr)

      {

            switch (state)

            {

            case 0:

                  if (NULL != (str = get_exp(ptr)))

                  {

                        if (NULL != (op = get_op(str)) &&

                              strlen(str) == op->taglen)

                        {

                              push_op(op->token);

                              ptr += op->taglen;

                              break;

                        }



                        if (Success_ == strcmp(str, "-"))

                        {

                              push_op(*str);

                              ++ptr;

                              break;

                        }



                        if (Success_ == strcmp(str, "PI"))

                              push_arg(Pi);



                        else

                        {

                              if (0.0 == (arg = strtod(str, &endptr)) &&

                                    NULL == strchr(str, '0'))

                              {

                                    return Error_;

                              }

                              push_arg(arg);

                        }

                        ptr += strlen(str);

                  }

                  else  return Error_;



                  state = 1;

                  break;



            case 1:

                  if (NULL != (op = get_op(ptr)))

                  {

                        if (')' == *ptr)

                        {

                              if (Success_ > (ercode = do_paren()))

                                    return ercode;

                        }

                        else

                        {

                              while (op_sptr &&

                                    op->precedence <= getTOSprec())

                              {

                                    do_op();

                              }

                              push_op(op->token);

                              state = 0;

                        }



                        ptr += op->taglen;

                  }

                  else  return Error_;



                  break;

            }

      }



      while (1 < arg_sptr)

      {

            if (Success_ > (ercode = do_op()))

                  return ercode;

      }

      if (!op_sptr)

            return pop_arg(val);

      else  return Error_;

}



/*

**  Evaluate stacked arguments and operands

*/



static int do_op(void)

{

      double arg1, arg2;

      int op;



      if (Error_ == pop_op(&op))

            return Error_;



      pop_arg(&arg1);

      pop_arg(&arg2);



      switch (op)

      {

      case '+':

            push_arg(arg2 + arg1);

            break;



      case '-':

            push_arg(arg2 - arg1);

            break;



      case '*':

            push_arg(arg2 * arg1);

            break;



      case '/':

            if (0.0 == arg1)

                  return R_ERROR;

            push_arg(arg2 / arg1);

            break;



      case '\\':

            if (0.0 == arg1)

                  return R_ERROR;

            push_arg(fmod(arg2, arg1));

            break;



      case '^':

            push_arg(pow(arg2, arg1));

            break;



      case 't':

            ++arg_sptr;

            push_arg(atan(arg1));

            break;



      case 'S':

            ++arg_sptr;

            push_arg(sin(arg1));

            break;



      case 's':

            if (0.0 > arg2)

                  return R_ERROR;

            ++arg_sptr;

            push_arg(sqrt(arg1));

            break;



      case 'C':

            ++arg_sptr;

            push_arg(cos(arg1));

            break;



      case 'A':

            ++arg_sptr;

            push_arg(fabs(arg1));

            break;



      case 'L':

            if (0.0 < arg1)

            {

                  ++arg_sptr;

                  push_arg(log(arg1));

                  break;

            }

            else  return R_ERROR;



      case 'E':

            ++arg_sptr;

            push_arg(exp(arg1));

            break;



      case '(':

            arg_sptr += 2;

            break;



      default:

            return Error_;

      }

      if (1 > arg_sptr)

            return Error_;

      else  return op;

}



/*

**  Evaluate one level

*/



static int do_paren(void)

{

      int op;



      if (1 > parens--)

            return Error_;

      do

      {

            if (Success_ > (op = do_op()))

                  break;

      } while (getprec((char)op));

      return op;

}



/*

**  Stack operations

*/



static void push_op(char op)

{

      if (!getprec(op))

            ++parens;

      op_stack[op_sptr++] = op;

}



static void push_arg(double arg)

{

      arg_stack[arg_sptr++] = arg;

}



static int pop_arg(double *arg)

{

      *arg = arg_stack[--arg_sptr];

      if (0 > arg_sptr)

            return Error_;

      else  return Success_;

}



static int pop_op(int *op)

{

      if (!op_sptr)

            return Error_;

      *op = op_stack[--op_sptr];

      return Success_;

}



/*

**  Get an expression

*/



static char * get_exp(char *str)

{

      char *ptr = str, *tptr = token;

      struct operator *op;



      if (Success_ == strncmp(str, "PI", 2))

            return strcpy(token, "PI");





      while (*ptr)

      {

            if (NULL != (op = get_op(ptr)))

            {

                  if ('-' == *ptr)

                  {

                        if (str != ptr && 'E' != ptr[-1])

                              break;

                        if (str == ptr && !isdigit(ptr[1]) && '.' != ptr[1])

                        {

                              push_arg(0.0);

                              strcpy(token, op->tag);

                              return token;

                        }

                  }



                  else if (str == ptr)

                  {

                        strcpy(token, op->tag);

                        return token;

                  }



                  else break;

            }



            *tptr++ = *ptr++;

      }

      *tptr = NUL;



      return token;

}



/*

**  Get an operator

*/



static struct operator * get_op(char *str)

{

      struct operator *op;



      for (op = verbs; op->token; ++op)

      {

            if (Success_ == strncmp(str, op->tag, op->taglen))

                  return op;

      }

      return NULL;

}



/*

**  Get precedence of a token

*/



static int getprec(char token)

{

      struct operator *op;



      for (op = verbs; op->token; ++op)

      {

            if (token == op->token)

                  break;

      }

      if (op->token)

            return op->precedence;

      else  return 0;

}



/*

**  Get precedence of TOS token

*/



static int getTOSprec(void)

{

      if (!op_sptr)

            return 0;

      return getprec(op_stack[op_sptr - 1]);

}



#ifdef TEST



#include <stdio.h>



#ifdef __WATCOMC__

 #pragma off (unreferenced);

#endif

#ifdef __TURBOC__

 #pragma argsused

#endif



main(int argc, char *argv[])

{

      int retval;

      double val;



      printf("evaluate(%s) ", argv[1]);

      printf("returned %d\n", retval = evaluate(argv[1], &val));

      if (0 == retval)

            printf("val = %f\n", val);

      return 0;

}



#endif /* TEST */

0
 
LVL 22

Expert Comment

by:nietod
ID: 2600186
+++Date last modified: 05-Jul-1997

  Basically, EVAL.C converts infix notation to postfix notation. If you're
not familiar with these terms, infix notation is standard human-readable
equations such as you write in a C program. Postfix notation is most familiar
as the "reverse Polish" notation used in Hewlett Packard calculators and in
the Forth language. Internally, all languages work by converting to postfix
evaluation. Only Forth makes it obvious to the programmer.

  EVAL.C performs this conversion by maintaining 2 stacks, an operand stack
and an operator stack. As it scans the input, each time it comes across a
numerical value, it pushes it onto the operand stack. Whenever it comes
across an operator, it pushes it onto the operator stack. Once the input
expression has been scanned, it evaluates it by popping operands off the
operand stack and applying the operators to them.

 For example the simple expression "2+3-7" would push the values 2, 3, and 7
onto the operand stack and the operators "+" and "-" onto the operator stack.
When evaluating the expression, it would first pop 3 and 7 off the operand
stack and then pop the "-" operator off the operator stack and apply it. This
would leave a value of -4 on the stack. Next the value of 2 would be popped
from the operand stack and the remaining operator off of the operator stack.
Applying the "+" operator to the values 2 and -4 would leave the result of
the evaluation, -2, on the stack to be returned.

  The only complication of this in EVAL.C is that instead of raw operators
(which would all have to be 1 character long), I use operator tokens which
allow multicharacter operators and precedence specification. What I push on
the operator stack is still a single character token, but its the operator
token which is defined in the 'verbs' array of valid tokens. Multicharacter
tokens are always assumed to include any leading parentheses. For example, in
the expression "SQRT(37)", the token is "SQRT(".

  Using parentheses forces evaluation to be performed out of the normal
sequence. I use the same sort of mechanism to implement precedence rules.
Unary negation is yet another feature which takes some explicit exception
processing to process. Other than these exceptions, it's pretty
straightforward stuff.
0
 
LVL 22

Expert Comment

by:nietod
ID: 2600191
Hmm, didn't see the other comments.  I may be wrong in what is needed.  I'll withdraw my answer.
0
 

Expert Comment

by:OlafHerrmann
ID: 2602230
Please try the code on this link:
http://www.codetools.com/cpp/FunctionParser.asp
0
 
LVL 22

Expert Comment

by:nietod
ID: 2605049
OlaffHerrmann, how is your answer different than what I posted?  The problem is the line

"a formula that will be used on a large number of records"

Its not clear what he means by this, therefore it is not clear if this will work for him.
0
 
LVL 2

Expert Comment

by:yairy
ID: 2609953
Sorry, All.
I was out for a few day's.
I will try to be more clear.
What I need is a parser that parses
A string like "a+b*c/d" and give me
some sort of data structure (Not a tree
because it wont be afisiant enough to work recursivlly). so i can change the values of a,b,c and d and use the formula on a large amount of values
(a table with 4 (a,b,c,d) columns with 40,000 records)
I realy appreciates your replay's
 Thanks Uri.

p.s- nietod ,I will go over your code
and see if it's Good for this problem
Thanks for the meantime.  
0
 
LVL 2

Expert Comment

by:yairy
ID: 2609960
Last message was from Uritweeg also
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 22

Expert Comment

by:nietod
ID: 2610025
>> and give me
>> some sort of data structure (Not a tree
>> because it wont be afisiant enough to
>> work recursivlly)
What sort of data structure do you want?  Usually you pick a data structure that has something to do with the problem.  In this case that would be a tree.

And why is a tree not efficient?  

If you are dealing with 40,000 records, you probably don't need to even consider the efficiency of the calculation, the bottleneck will be the disk i/O.  You can probably run the calculation 100 times per record and never notiice that it takes longer than running it once per record.
0
 
LVL 10

Expert Comment

by:RONSLOW
ID: 2620146
tree would be best .. as otherwise it won't be dynamic enough.

here is the sort of thing (probably doesn't compile .. just typing it out as I think of it...)  Note that we build an expression tree once (when the formula is given) and keep it. then give it the values and ask it to evaluate.

class Node {
public:
  static double& ValueFor(char letter) {
    static double value['Z'-'A'+1];
    return value[letter-'A'];
  }
  virtual double Value() = 0;
};

class Var : public Node {
public:
  Var(char l) : letter(l) {}
  virtual double Value() { return ValueFor(letter); }
private:
  char letter;
};

template <int opcode> class Operator : public Node {
  Operator(Node* l, Node* r) : left(l), right(r) {}
  ~Operator() {
    delete left;
    delete right;
  }
  virtual double Value();
private:
  Node* left;
  Node* right;
}

inline double Operator<'+'>::Value() {
  return left->Value()+right->Value();
}
inline double Operator<'-'>::Value() {
  return left->Value()-right->Value();
}
inline double Operator<'*'>::Value() {
  return left->Value()*right->Value();
}
inline double Operator<'/'>::Value() {
  return left->Value()/right->Value();
}

Node* ParseExpr(string s) {
  int pos = 0;
  Node* node = ParseAddSub(s,pos);
  // can check that remainder of s
  // from pos onward is empty
  return node;
}

Node* ParseAddSub(string s, int& pos) {
  Node* node = ParseMulDiv(s,pos);
  for (;;) {
    if (s[pos]=='+') {
      pos++;
      Node* other = ParseMulDiv(s,pos);
      node = new Operator<'+'>(node,other);
    } else if (s[pos]
      pos++;
      Node* other = ParseMulDiv(s,pos);
      node = new Operator<'-'>(node,other);
    } else {
      break;
    }
  }
  return l;
}

Node* ParseMulDiv(string s, int& pos) {
  Node* node = ParseSimple(s,pos);
  for (;;) {
    if (s[pos]=='+') {
      pos++;
      Node* other = ParseSimple(s,pos);
      node = new Operator<'*'>(node,other);
    } else if (s[pos]
      pos++;
      Node* other = ParseSimple(s,pos);
      node = new Operator<'/'>(node,other);
    } else {
      break;
    }
  }
  return l;
}

Node* ParseSimple(string s, int& pos) {
  Node* node = NULL;
  if (s[pos]=='(') {
    pos++;
    node = ParseAddSub(s,pos);
    if (s[pos]!=')') {
      // error...
    }
    pos++;
  } else if (s[pos] >= 'A' && s[pos] <= 'Z') {
    node = new Var(s[pos]);
    pos++;
  } else {
    // error...
  }
}

then what one would do is

Node* evaluator = ParseExpr(formula);
for (..each record..) {
  Node::ValueFor('a') = ..first value..
  Node::ValueFor('b') = ..second value..
  ...
  v = evaluator->Value();
  ...
}
0
 

Author Comment

by:uritwig
ID: 2620297
Sorry, OlafHerrmann's
But its not what i had in mind.
0
 

Author Comment

by:uritwig
ID: 2620306
Adjusted points from 300 to 400
0
 

Author Comment

by:uritwig
ID: 2620307
RONSLOW , I'll Get Back to you on that.
 Thanks :).
0
 
LVL 22

Expert Comment

by:nietod
ID: 2620338
untwig, what do you have in mind?

The code I posted can be used to evaluate complex expressions.  It uses a binary expression tree.  That is probably the best way to do this.

You say you are concerned with efficiency, but why do you think this is inefficient?  And does the efficiency of the calculation really matter.   Even a tremendously long calculations isn't going to take much time compared to the time needed to read a single record from the database.
0
 

Author Comment

by:uritwig
ID: 2620570
Hi RONSLOW.

 I tried your code and it works greate
 But, something I didnt mansion earlier
 Is that the names of the Variebles    are  strings and not charicters and
I cant use the global & static functions & varieble because it is a tiny fithur in the aplication.
How can I change the code So it will Suite me?
Thanks So far Uri.
0
 
LVL 10

Accepted Solution

by:
RONSLOW earned 450 total points
ID: 2621495
in that case, keep an array of the names.

In the ParseSimple code, build up the name character-by-character (or span over alphanumerics).  Then lookup the name in the table (a linear scan should be fine as you won't have too many names, and the parsing only happens once).  Use the index of the array rather than the letter code eg.

// max number of unique variable names
#define MAXVAR ...whatever...
class Node {
public:
  static double& ValueFor(int index) {
    static double values[MAXVAR];
    return values[index];
  }
  static int& IndexFor(string name) {
    static string names[MAXVAR];
    static int nnames = 0;
    int i;
    for (int i = 0; i < nnames; i++) {
      if (names[i] == name) return i;
    }
    i = nnames++;
    names[i] = name;
    return i;
  }
  virtual double Value() = 0;
};

change var a little too:

class Var : public Node {
public:
  Var(string name) { index = IndexFor(name); }
  virtual double Value() { return ValueFor(index); }
private:
  int index;
};

and in ParseSimple change this:
  } else if (s[pos] >= 'A' && s[pos] <= 'Z') {
    node = new Var(s[pos]);
    pos++;

to this:

  } else if (isalpha(s[pos])) {
    string name = s[pos++];
    while (isalnum(s[pos])) {
      name += s[pos++];
    }
    node = new Var(name);

also one needs to define numbers here too (forgot them).

  } else if (isdigit(s[pos]) || s[pos]=='.' || s[pos]=='+' || s[pos]=='-') {
    string number = s[pos++];
    while (isdigit(s[pos]) || s[pos]=='.') {
      number += s[pos++];
    }
    double v = atof(number);
    node = new Constant(number);

where we define Constant as

class Constant : public Node {
public:
  Constant(double v) : value(v) {}
  virtual double Value() { return value; }
private:
  double value;
};

0
 

Author Comment

by:uritwig
ID: 2622756
Adjusted points from 400 to 450
0
 

Author Comment

by:uritwig
ID: 2622757
Thank You Very Much.
You have been a greate help To me.

This comment was also added to the code
//This code was added Thanks to RONSLOW.

So,You'll be remmembered forever.
 Thanks again Uri.
0

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

747 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now