Expression Evaluator

This is a discussion on Expression Evaluator within the C Programming forums, part of the General Programming Boards category; I want to write a calculator that reads an expression from user input computes the expression and display the result ...

  1. #1
    hei
    hei is offline
    Registered User
    Join Date
    Oct 2001
    Posts
    12

    Smile Expression Evaluator

    I want to write a calculator that reads an expression from user input computes the expression and display the result correct to 3 decimal points. The expression is evaluated from left to right.
    I really don't know how to get started, please give a help. ^^


    for example,

    user input 15+3/2
    output will be 16.500

    user input 5*2.0^3+(1+4)*5
    output will be 65.000

    user input 3.5+2x=7.5
    output will be 2
    The calculator can solve x.

    user input 15+-5.20
    output will be 9.800


    Please give me a help, thank you so much.

  2. #2
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    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.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  3. #3
    hei
    hei is offline
    Registered User
    Join Date
    Oct 2001
    Posts
    12

    How ?

    I want to ask how to work out the precedence of each token,
    it seems difficult to me.^^

  4. #4
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    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.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  5. #5
    hei
    hei is offline
    Registered User
    Join Date
    Oct 2001
    Posts
    12
    Do i need to use array in my program?

    and how to extract the numbers?

    for example, 3+5-(-1)
    how to extract "+" and "-1" ??

    thanks.

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    One of the things that ........ me off so bad is the fact that these questions are asked EVERY WEEK! Some times EVERY DAY. Some times MORE THAN ONCE A DAY! BY THE SAME PERSON!

    Most of these questions could be answered if they spent a few minutes looking at previous posts. But hell, most people don't even read the very top post that says "READ THIS FIRST". I give up.

    I refuse to answer any homework related question that doesn't present code, or understandable pseudocode.

    Quzah.

  7. #7
    Registered User
    Join Date
    Nov 2001
    Posts
    2

    Post

    The following way isn't the easiest one, but it is more "official" (if quzah is right and this is a homework).

    some usefull thoughts:
    1. you can write an expression in 3 ways:
    a. the symbols between the numbers. (e.g. 5+7)
    b. the symbols before the numbers. (e.g. +57)
    c. the symbols after the numbers. (e.g. 57+)

    2. An example about the third way:
    5 + 7 - 3 / 2
    5.7+3.2/- (using . as separator for the numbers)

    3. The third way is very usefull for us.
    (but you have to use a symbol that separates the numbers)
    Why is it so usefull?
    Because if the expression is written this way, the operations have to be executed left to right. (no matter if the operation is + , - , * or anything else and it has no () )

    So if we have a stack, we have just to put a the numbers in the stack until we find an operator. Then we execute the operation using the 2 numbers who are in the top of the stack. When the expression ends the stack has only one number, the result.
    (about the arrays: you can implement the stack with an array)

    You have to write also some code for the convertion of the expression.

    I propose this solution because it is very difficult to do something wrong computing the expression if the expression is written in the third way.

    (sorry about my english)

    Does anybody knows how the 3 ways of writing the expression are in english?

  8. #8
    Registered User
    Join Date
    Sep 2001
    Posts
    164
    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)
    // Gliptic

  9. #9
    Registered User
    Join Date
    Sep 2001
    Posts
    164
    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
    {
     
    charsymb;
     
    long double value;
    CONSTANTS;

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

    long double Evaluate(long startlong stopcharexpr);

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

    long double Evaluate(long startlong stopcharexpr)
    {
     
    OPS op_found;
     
    OPS op_last None;
     
    unsigned long op_cursign 0xFFFFFFFF;
     
    long op_pos;
     
    long parnestparpair;
     
    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 startcurpos <= stopcurpos++)
      {
       if(
    expr[curpos] == '(')
       {
        
    parnest++;
       } else if(
    expr[curpos] == ')')
       {
        
    parnest--;
        if(
    parnest == 0parpair++;
       }
      }
      
      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 startcurpos <= stopcurpos++)
     {
      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 ab;
       
      
    Evaluate(startop_pos 1expr);
      
    Evaluate(op_pos 1stopexpr);

      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(ab);
      }
      return 
    true;
     }

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

      case 
    '-':
       return -
    Evaluate(start 1stopexpr);
     }

     
    //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 0sizeof(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 startstopi++)
     {
      if(
    expr[i] == '(')
      {
       
    expr[i] = 0;
       if(!
    strcmpi(&expr[start], "cos"))
        return 
    cosEvaluate(i+1stop-1expr) );
       else if(!
    strcmpi(&expr[start], "sin"))
        return 
    sinEvaluate(i+1stop-1expr) );
       else if(!
    strcmpi(&expr[start], "tan"))
        return 
    tanEvaluate(i+1stop-1expr) );
       else if(!
    strcmpi(&expr[start], "exp"))
        return 
    expEvaluate(i+1stop-1expr) );
       else if(!
    strcmpi(&expr[start], "sqrt"))
        return 
    sqrtEvaluate(i+1stop-1expr) );
       else
       {
        
    printf("\nError: Unidentified function: %s\n", &expr[start]);
        return 
    0;
       }
      }
     }
     
     
    //No matching constants. Evaluate as a literal
     
    return atof(&expr[start]);

    // Gliptic

  10. #10
    hei
    hei is offline
    Registered User
    Join Date
    Oct 2001
    Posts
    12

    Talking

    Thank you very much Gliptic,
    your code is very useful,
    i can understand more about c program now.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with making a Math Expression DLL
    By MindWorX in forum C Programming
    Replies: 19
    Last Post: 07-19-2007, 11:37 PM
  2. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  3. recursion error
    By cchallenged in forum C Programming
    Replies: 2
    Last Post: 12-18-2006, 08:15 AM
  4. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  5. Expression Evaluator Contest
    By Stack Overflow in forum Contests Board
    Replies: 20
    Last Post: 03-29-2005, 09:34 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21