Logo Search packages:      
Sourcecode: hitop version File versions

maths.cc

// Operator precedence parser for evaluating simple mathematical expressions.

#include "maths.h"
#include <cstdio>
#include <vector>
#include <stack>
#include <cctype>

using namespace std;

typedef enum {NUMBER,OPERATOR,NEW,END} TokType;

typedef struct 
{
    TokType type;
    float value;
    char op;
}
Token;

// Very simple tokenizer. I've probably made some silly error in it
// somewhere, but it generally works.
static vector<Token> tokenize(string input,bool& error)
{
    vector<Token> ts;
    input+=" ";
    string tokText;
    char lastTok='\0';

    string::const_iterator lbo=input.end()-1;
    for(string::const_iterator pos=input.begin();pos!=input.end();++pos)
    //for(unsigned i=0;i<input.length();++i)
    {
      //char in=input[i];
        char in=*pos;
      if (isdigit(in) || in=='.' || in=='e' || in=='E' || (lastTok!=')' && tokText.empty() && in=='-') || (in=='-' && (lastTok=='e' || lastTok=='E')))
          tokText+=in;
      else if (in=='+' || in=='-' || in=='*' || in=='/' || in=='(' || in==')' || pos==lbo || in==' ')
      {
          // Process previous token, if there was one.
          Token newTok;

          if (!tokText.empty())
          {
            newTok.type=NUMBER;
            newTok.value=atof(tokText.c_str());
            ts.push_back(newTok);
            tokText.erase();
          }

          // Process the operator.
          if (pos!=lbo && in!=' ')
          {
            newTok.type=OPERATOR;
            newTok.op=(char)in;
            ts.push_back(newTok);
          }
      }
      else
      {
          // Error crisis!
          error=true;
          return ts;
      }
      lastTok=in;
    }
    Token endTok;
    endTok.type=END;
    endTok.value=0;
    endTok.op='!';
    ts.push_back(endTok);
    return ts;
}

// Returns -1 if a yields to b, 0 if a=b or 1 if a takes precedence over b
static int getPrecedence(Token a,Token b)
{
    int precTable[2][8]={
//        + - * / ( ) n $
/* f */  {2,2,4,4,0,6,6,0},
/* g */  {1,1,3,3,5,0,5,0}
    };

    int aPos,bPos;
    if (a.type==NUMBER) aPos=6;
    else
    {
      switch(a.op)
      {
      case '+': aPos=0; break;
      case '-': aPos=1; break;
      case '*': aPos=2; break;
      case '/': aPos=3; break;
      case '(': aPos=4; break;
      case ')': aPos=5; break;
      default: aPos=7; break;
      }
    }
    if (b.type==NUMBER) bPos=6;
    else
    {
      switch(b.op)
      {
      case '+': bPos=0; break;
      case '-': bPos=1; break;
      case '*': bPos=2; break;
      case '/': bPos=3; break;
      case '(': bPos=4; break;
      case ')': bPos=5; break;
      default: bPos=7; break;
      }
    }
    int fa=precTable[0][aPos];
    int fb=precTable[1][bPos];

    if (fa>fb) return 1;
    else if (fa==fb) return 0;
    else return -1;
}

float parse(vector<Token> ts,bool& error)
{
    vector<Token>::const_iterator ip;
    stack<Token> tokStack;
    stack<float> evalStack;

    Token endTok;
    endTok.type=END;

    tokStack.push(endTok);

    ip=ts.begin();
    do
    {
      Token top=tokStack.top();

      if (top.type==END && (*ip).type==END) break;
     
      int prec=getPrecedence(top,*ip);
      if (prec==-1 || prec==0)
      {
// Shift next token onto the stack.
          tokStack.push(*ip);
          ++ip;
      }
      else if (prec==1)
      {
// Reduce what's on the stack.
          Token popped;
          do
          {
            if(tokStack.empty()){
                  error=true;
                  return 0;
            }
            top=tokStack.top();
            tokStack.pop();
            popped=top;

            if (popped.type==NUMBER)
                evalStack.push(popped.value);
            else if (popped.type==OPERATOR)
            {
                float a=0.0,b=0.0;
                if (popped.op!='(' && popped.op!=')')
                {
                  if(evalStack.empty()){
                        error=true;
                        return 0;
                  }
                  a=evalStack.top();
                  evalStack.pop();
                  if(evalStack.empty()){
                        error=true;
                        return 0;
                  }
                  b=evalStack.top();
                  evalStack.pop();
                }
                switch(popped.op)
                {
                case '+':
                  evalStack.push(b+a);
                  break;
                case '-':
                  evalStack.push(b-a);
                  break;
                case '*':
                  evalStack.push(b*a);
                  break;
                case '/':
                  evalStack.push(b/a);
                  break;
                default:
// Ignore ( and ), as they've done their job already.
                  break;
                }
            }

          }
          while (getPrecedence(tokStack.top(),popped)!=-1);
      }
      else
      {
          // Error.
          error=true;
          return 0;
      }
    }
    while(true);
    return evalStack.top();
}

string evaluate(const string& expression)
{
    if(expression.empty()) return "0";
    bool error=false;

    vector<Token> t=tokenize(expression,error);

    if (error) return "[Error in expression]";

    float val=parse(t,error);

    if (error) return "[Error in expression]";

    char buf[80]; /* Ugh */
    sprintf(buf,"%g",val);
    return buf;
}

Generated by  Doxygen 1.6.0   Back to index