Thread: can someone teach me how to write a program softing math equations?

  1. #1
    Registered User
    Join Date
    Oct 2001
    Posts
    101

    can someone teach me how to write a program softing math equations?

    I'm writing a program that can soft mathematical equations. The euquations are user specified including +, -, ^, *, /, operations. The program are required to scan the equation from the user and soft it for them. My biggest difficulty is that I don't know how to scan an equation from the user and store it for later use. Can some kind people help me out?! Thanks!

  2. #2
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    Use a binary tree and presedence rules with each node representing an operation and each leaf representing a value.

  3. #3
    Registered User
    Join Date
    Oct 2001
    Posts
    101
    thanks for the suggestion. sadly I haven't had any class and experience on data structure. Is there any other simpler approach that avoid the use of using binery tree??

  4. #4
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    If you're not concerned about operator presedence and about physically storing the expression, then the problem isn't too tough. Just perform the calculations as you read them from the string.

  5. #5
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    If you understand stacks you can easily make a way of calculating expressions in reverse-polish notation.

  6. #6
    Registered User
    Join Date
    Aug 2001
    Posts
    403
    Disclaimer : this is all theoretical, I only wrote an expression parser once before and I did it with trees as Polymorphic suggested.

    "4/2+3^2"

    break it up into 2 arrays:
    (doubles)
    4.0, 2.0, 3.0, 2.0

    and the operators:
    (chars)
    / + ^

    Then I would go through the operators array and look for the first one with priority ^, * or /, + or -.

    Since the operators and numbers were stored in order you can find that 3.0 and 2.0 were associated with the ^ yielding
    3.0^2.0

    now the arrays look like:
    4.0 2.0 9.0
    and
    / +

    Now you'd determine that / has priority and the equation is 4/2 yielding 2

    2.0 and 9.0 with the + operator --> 11.0


    Splitting it up into arrays should be pretty easy, and I believe from there you should be able to figure out how to loop through until you have only one number and 0 operators.

  7. #7
    Registered User Cela's Avatar
    Join Date
    Jan 2003
    Posts
    362
    Expression trees can get confusing when you bring in precedence. Here's a parser that uses stacks and postfix notation to solve the problem. It's not perfect, I just wrote it up real quick, and it's in C...sorry :-)
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <ctype.h>
    
    enum {integral, op, nesting};
    
    typedef struct {
      int token_type;
      char token_value[50];
    } token;
    
    void remove_ws(char *src)
    {
      char *p;
      char *q;
    
      for (p = q = src; (*p = *q) != '\0'; q++)
      {
        if (!isspace(*q))
        {
          p++;
        }
      }
    }
    
    token fill_token(char *start, size_t n)
    {
      token new_token;
    
      new_token.token_value[0] = '\0';
    
      if (isdigit(*start))
      {
        new_token.token_type = integral;
      }
      else if (strspn(start, "()") == 0)
      {
        new_token.token_type = op;
      }
      else
      {
        new_token.token_type = nesting;
      }
    
      strncat(new_token.token_value, start, n);
    
      return new_token;
    }
    
    int convert(token list[], token new_list[], size_t n_tokens)
    {
      size_t i;
      size_t top;
      size_t index;
      token  t_stack[100];
    
      top = 0;
      index = 0;
      for (i = 0; i < n_tokens; i++)
      {
        if (strchr(list[i].token_value, '(') == 0 && 
            list[i].token_type == nesting)
        {
          new_list[index++] = t_stack[--top];
        }
        else if (list[i].token_type == op)
        {
          t_stack[top++] = list[i];
        }
        else if (list[i].token_type == integral)
        {
          new_list[index++] = list[i];
        }
      }
    
      return index;
    }
    
    int eval(token list[], size_t n_tokens)
    {
      size_t i;
      size_t top;
      int    i_stack[100];
    
      top = 0;
      for (i = 0; i < n_tokens; i++)
      {
        if (list[i].token_type == op)
        {
          int a = i_stack[--top];
          int b = i_stack[--top];
    
          if (strcmp(list[i].token_value, "+") == 0)
          {
            i_stack[top++] = b + a;
          }
          else if (strcmp(list[i].token_value, "-") == 0)
          {
            i_stack[top++] = b - a;
          }
          else if (strcmp(list[i].token_value, "*") == 0)
          {
            i_stack[top++] = b * a;
          }
          else if (strcmp(list[i].token_value, "/") == 0)
          {
            if (a > 0)
            {
              i_stack[top++] = b / a;
            }
          }
        }
        else if (list[i].token_type == integral)
        {
          i_stack[top++] = atoi(list[i].token_value);
        }
      }
    
      return i_stack[--top];
    }
    
    int evaluate(token list[], size_t n_tokens)
    {
      size_t n;
      token  new_list[100];
    
      /* Convert to postfix notation */
      n = convert(list, new_list, n_tokens);
    
      /* Evaluate the postfix expression */
      return eval(new_list, n);
    }
    
    int tokenize(char *buff, token token_list[])
    {
      char  *start;
      size_t end;
      size_t i;
    
      i = 0;
      start = buff;
      while (*start != '\0')
      {
        if ((end = strcspn(start, "()/*+-")) == 0)
          /* Look for an operand first */
        {
          if ((end = strspn(start, "/*+-")) == 0)
            /* Look for an operator second */
          {
            /* Look for a nesting last */
            end = strspn(start, "()");
          }
        }
    
        token_list[i++] = fill_token(start, end);
        start += end;
      }
    
      return i;
    }
    
    int main(void)
    {
      token  token_list[100];
      char   buff[100];
      int    n;
    
      printf("Enter a fully parenthesized infix expression. Ex. ((4+6)*2)\n");
      printf("%% ");
      fflush(stdout);
    
      gets(buff);
      remove_ws(buff);
    
      n = tokenize(buff, token_list);
    
      printf("%s = %d\n", buff, evaluate(token_list, n));
    
      return 0;
    }
    *Cela*

  8. #8
    samurai warrior nextus's Avatar
    Join Date
    Nov 2001
    Posts
    196
    i wrote this program along time ago to solve math expressions..hope this helps

    Code:
    #include <iostream>                 // For stream input/output
    #include <cstdlib>                  // For the exit() function
    #include <cctype>                   // For the isdigit() function
    #include <string>                   // For the strcpy function
    using namespace std;
    
    void eatspaces(char* str);          // Function to eliminate blanks
    double expr(char* str);             // Function evaluating an expression
    double term(char* str, int& index);   // Function analyzing a term
    double number(char* str, int& index); // Function to recognize a number
    char* extract(char* str, int& index); //Function to extract a substring
    
    const int MAX = 80;         // Maximum expression length including '\0'
    
    int main(void)
    {
       char buffer[MAX] = {0};    // Input area for expression to be evaluated
    
       cout << endl
            << "Welcome to your friendly calculator."
            << endl
            << "Enter an expression, or an empty line to quit."
            << endl;
    
       for(;;)
       {
          cin.getline(buffer, sizeof buffer);   // Read an input line
          eatspaces(buffer);                    // Remove blanks from input
    
          if(!buffer[0])                      // Empty line ends calculator
             return 0;
    
          cout << "\t= " << expr(buffer)      // Output value of expression
               << endl << endl;
       }
    }
    
    
    // Function to eliminate blanks from a string
    void eatspaces(char* str)
    {
       int i=0;         // 'Copy to' index to string
       int j=0;         // 'Copy from' index to string
    
       while((*(str+i) = *(str+j++)) != '\0')   // Loop while character
                                                // copied is not \0
          if(*(str+i) != ' ')                   // Increment i as long as
             i++;                               // character is not a blank
       return;
    }
    
    
    // Function to evaluate an arithmetic expression
    double expr(char* str)
    {
       double value = 0;          // Store result here
       int index = 0;             // Keeps track of current character position
    
       value = term(str, index);  // Get first term
    
       for(;;)                    // Infinite loop, all exits inside
       {
          switch(*(str+index++))  // Choose action based on current character
          {
             case '\0':                 // We're at the end of the string
                return value;           // so return what we have got
    
             case '+':                         // + found so add in the
                value += term(str, index);     // next term
                break;
    
             case '-':                         // - found so subtract
                value -= term(str, index);     // the next term
                break;
    
             default:                       // If we reach here the string
                cout << endl                // is junk
                     << "Arrrgh!*#!! There's an error"
                     << endl;
                exit(1);
          }
       }
    }
    
    
    // Function to get the value of a term
    double term(char* str, int& index)
    {
       double value = 0;              // Somewhere to accumulate the result
    
       value = number(str, index);    // Get the first number in the term
    
       // Loop as long as we have a good operator
       while((*(str+index)=='*')||(*(str+index)=='/'))
       {
    
          if(*(str+index)=='*')                  // If it's multiply,
             value *= number(str, ++index);      // multiply by next number
    
          if(*(str+index)=='/')                  // If it's divide,
             value /= number(str, ++index);      // divide by next number
       }
       return value;             // We've finished, so return what we've got
    }
    
    
    // Function to recognize an expression in parentheses
    // or a number in a string
    double number(char* str, int& index)
    {
       double value = 0.0;              // Store the resulting value
    
       if(*(str+index) == '(')             // Start of parentheses
       {
          char* psubstr = 0;               // Pointer for substring
          psubstr = extract(str, ++index); // Extract substring in brackets
          value = expr(psubstr);           // Get the value of the substring
          delete[]psubstr;                 // Clean up the free store
          return value;                    // Return substring value
       }
    
       while(isdigit(*(str+index)))     // Loop accumulating leading digits
          value=10*value + (*(str+index++) - 48);
    
                                         // Not a digit when we get to here
       if(*(str+index)!='.')             // so check for decimal point
          return value;                  // and if not, return value
    
       double factor = 1.0;              // Factor for decimal places
       while(isdigit(*(str+(++index))))  // Loop as long as we have digits
       {
          factor *= 0.1;                 // Decrease factor by factor of 10
          value=value + (*(str+index)-48)*factor;   // Add decimal place
       }
    
       return value;                     // On loop exit we are done
    }
    
    
    // Function to extract a substring between parentheses 
    // (requires string)
    char* extract(char* str, int& index)
    {
       char buffer[MAX];         // Temporary space for substring
       char* pstr=0;             // Pointer to new string for return
       int numL = 0;             // Count of left parentheses found
       int bufindex = index;     // Save starting value for index
    
       do
       {
          buffer[index-bufindex] = *(str+index);
          switch(buffer[index-bufindex])
          {
             case ')':
                if(numL==0)
                {
                   buffer[index-bufindex] = '\0';  // Replace ')' with '\0' 
                   ++index;
                   pstr = new char[index-bufindex];
                   if(!pstr)
                   {
                      cout << "Memory allocation failed,"
                           << " program terminated.";
                      exit(1);
                   }
                   strcpy(pstr,buffer);  // Copy substring to new memory
                   return pstr;          // Return substring in new memory
                }
                else
                   numL--;           // Reduce count of '(' to be matched
                break;
    
             case '(':
                numL++;              // Increase count of '(' to be matched
                break;
          }
       } while(*(str+index++) != '\0');// Loop - don't overrun end of string
    
       cout << "Ran off the end of the expression, must be bad input."
            << endl;
       exit(1);
       return pstr;
    }
    nextus, the samurai warrior

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Program to write to memory map addresses
    By modest in forum C Programming
    Replies: 15
    Last Post: 06-03-2008, 03:20 PM
  2. Replies: 13
    Last Post: 01-13-2008, 09:38 PM
  3. write a program
    By angelgemini in forum C Programming
    Replies: 13
    Last Post: 12-05-2007, 11:39 AM
  4. Replies: 6
    Last Post: 01-01-2007, 07:36 AM
  5. how could i write this program: cat < apa | wc | wc > bepa
    By strugglingman in forum C Programming
    Replies: 2
    Last Post: 04-26-2006, 04:40 PM