Thread: Expression Evaluator

some pseudocode to get you going...

1) get the input from user using fgets(). Remember to replace the newline in the buffer with a null char.If you are not sure about this look up fgets() in your helpfiles or texts.
2) parse the string into tokens
3) work out the precedence of each token.Then I would use a stack to push them in order of precedence from least to most.
4) pop the tokens off the stack evaluating as necessary.
5) print the result.

try and code it yourself and come back if you are stuck.

cmon. Use your head!

work out the insides of parentheses first. From there you know to do division and multiplication before addition and subtraction etc. If you think about it a bit and i suspect you haven't too much or there would be some code posted for us to peruse, you will see that the problem is not too hard.

It's very easy.

You have a function called Evaluate(long start, long stop, char* expr)

In that function, you first test if the expression is enclosed in parathesis. Count the paranthesis pairs and check if it's equal to 1. Then check if the character at expr[start] is '(' and the character at expr[stop] is ')'. If all that is true, the expression is enclosed into paranthesis. To remove the paranthesis, just add one to start and subtract one from stop. Loop this procedure until there aren't any parathesis left.

Then you walk through the string from start to stop. If you find a '(' you increase a paranthesis counter. If you find an operator and the paranthesis counter is 0 you test if the operator has lower significans than the last found operator. If it does, set it as the last found operator and save the position. If you find a ')' you decrease the paranthesis counter.

When you have done that, you'll probably have an operator you can play with. If you have an operator, call Evaluate() for both sides of the operator like this:

float a = Evaluate(start, op_pos-1, expr);
float b = Evaluate(op_pos+1, stop, expr);

Then check which operator you have found. Something like this:

switch(op_found)
{
case Plus:
return a+b;

case Minus:
return a-b;

//etc...
}

If you haven't got an operator, try to evaluate the expression as a constant or a variable and return the value of that.

If you need unary operators, you'll have to have a flag when you search for operators which tells if there has been any non-white characters since the last operator. If there haven't been non-white characters, any found operator should be ignored. Then you check for unary operators later by simply check what the first character is and if there is an unary operator, do like this:

1. Call Evalute(start+1,stop,expr)
2. Process the return with the operator. It can be '-', '!' or anything.
3. Return the processed value.

Isn't it simple? (Sorry for my bad explanations)

Okay, I wrote this in a minute. Copy and paste:

PHP Code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

typedef enum Ops
{
 None,
 Plus,
 Minus,
 Multiply,
 Divide,
 Power
} OPS;

long signif[] =
{
 0xFFFFFFFF,
 10,
 10,
 11,
 11,
 12
};

typedef struct _constants
{
 char* symb;
 long double value;
} CONSTANTS;

CONSTANTS constants[] =
{
 {"pi", 3.14159265358979323846264338327950}
};

long double Evaluate(long start, long stop, char* expr);

int main()
{
  char buffer[256];
  long c;
  do
  {
   printf("Enter expression to evaluate: ");
   scanf("%s", buffer);
   printf("Result: %f \n\n", (float)Evaluate(0, strlen(buffer)-1, buffer));
   
   printf("Again? (1/0)");
   scanf("%d", &c);
  } while(c);
  
  return 0;
}

long double Evaluate(long start, long stop, char* expr)
{
 OPS op_found;
 OPS op_last = None;
 unsigned long op_cursign = 0xFFFFFFFF;
 long op_pos;
 long parnest, parpair;
 long curpos;
 bool nonwhite;

 //Remove enclosing whitespaces paranthesis
 while(1)
 {
  //Remove enclosing white spaces
  while(start <= stop)
  {
   if(expr[start] != ' '
   && expr[start] != '\t'
   && expr[start] != '\n'
   && expr[start] != '\r') break;
   
   start++;
  }
  
  while(stop >= start)
  {
   if(expr[stop] != ' '
   && expr[stop] != '\t'
   && expr[stop] != '\n'
   && expr[stop] != '\r') break;
   
   stop--;
  }
  
  if(start > stop)
  {
   printf("\nWarning: Empty expression interpreted as 0\n");
   return 0;
  }
  
  //Remove enclosing parathesis
  parnest = 0;
  parpair = 0;
  for(curpos = start; curpos <= stop; curpos++)
  {
   if(expr[curpos] == '(')
   {
    parnest++;
   } else if(expr[curpos] == ')')
   {
    parnest--;
    if(parnest == 0) parpair++;
   }
  }
  
  if(expr[start] == '(' && expr[stop] == ')' && parpair == 1)
  {
   start++;
   stop--;
  } else break; //Break if there are no more paranthesis
 }
 
 //Search for operators  
 nonwhite = false;
 parnest = 0;
 op_cursign = 0xFFFFFFFF;
 op_last = None;
 for(curpos = start; curpos <= stop; curpos++)
 {
  if(parnest == 0) // Are we in paranthesis
  {
   op_found = None;
   if(nonwhite)
   {
    switch(expr[curpos])
    {
     case '+':
      op_found = Plus;
      break;
     case '-':
      op_found = Minus;
      break;
     case '*':
      op_found = Multiply;
      break;
     case '/':
      op_found = Divide;
      break;
     case '^':
      op_found = Power;
      break;
    }
   } else
   {
    switch(expr[curpos])
    {
     //Interpret the operators as white spaces
     case '+':
     case '-':
     case '*':
     case '/':
     case '^':
     
     case ' ':
     case '\t':
     case '\n':
     case '\r':
      break; //Ignore white spaces
     default:
      nonwhite = true;
    }
   }

   if(op_found != None)
   {
    nonwhite = false;
    if(signif[op_found] <= op_cursign)
    {
     op_cursign = signif[op_found];
     op_last = op_found;
     op_pos = curpos;
    }
   }
  }

  if(expr[curpos] == '(')
  {
   parnest++;
  } else if(expr[curpos] == ')')
  {
   parnest--;
  }
 }

 if(parnest != 0)
 {
  printf("\nError: Parenthesis nesting error!\n");
  return 0;
 }
 
 //Did we find any operators?
 if(op_last != None)
 {
  long double a, b;
   
  a = Evaluate(start, op_pos - 1, expr);
  b = Evaluate(op_pos + 1, stop, expr);

  switch(op_last)
  {
   case Plus:
    return a+b;

   case Minus:
    return a-b;
 
   case Multiply:
    return a*b;
    
   case Divide:
    return a/b;
    
   case Power:
    return pow(a, b);
  }
  return true;
 }

 //Check for unary operators
 switch(expr[start])
 {
  case '!':
   return (Evaluate(start + 1, stop, expr) == 0);

  case '-':
   return -Evaluate(start + 1, stop, expr);
 }

 //Put in a null terminator
 expr[stop+1] = 0; //This is pretty safe even though it may not look like that
 
 //Check if the value matches any constants
 for(long i = 0; i < sizeof(constants)/sizeof(CONSTANTS); i++)
 {
  if(strcmpi(&expr[start], constants[i].symb) == 0)
  {
   return constants[i].value;
  }
 }
 
 //Check if the expression is a function
 for(long i = start; i < stop; i++)
 {
  if(expr[i] == '(')
  {
   expr[i] = 0;
   if(!strcmpi(&expr[start], "cos"))
    return cos( Evaluate(i+1, stop-1, expr) );
   else if(!strcmpi(&expr[start], "sin"))
    return sin( Evaluate(i+1, stop-1, expr) );
   else if(!strcmpi(&expr[start], "tan"))
    return tan( Evaluate(i+1, stop-1, expr) );
   else if(!strcmpi(&expr[start], "exp"))
    return exp( Evaluate(i+1, stop-1, expr) );
   else if(!strcmpi(&expr[start], "sqrt"))
    return sqrt( Evaluate(i+1, stop-1, expr) );
   else
   {
    printf("\nError: Unidentified function: %s\n", &expr[start]);
    return 0;
   }
  }
 }
 
 //No matching constants. Evaluate as a literal
 return atof(&expr[start]);
}