Thread: Calculator program

  1. #1
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374

    Calculator program

    Ok I’m having trouble with my simple expression evaluator. Basically, I need this to work so I can use it to form the structure of a generic algebra solver, which I plan to revise later.

    Description:
    The program uses ‘Reverse Polish Notation’ to handle nested parenthesis and evaluates these cases quite nicely:-

    Code:
    1) Can it solve basic cases like:
    1+1+7+3-2
    
    2) Does it correctly handle order of operation cases without any parenthesis:
    1+7*3-4
    
    3) Does it handle order of operations for simple parenthesis cases:
    3*(2+4)-5
    
    4.) Does it handle multiple parenthesis cases, not nested:
    (2+5) * (4+1)
    
    5) Does it handle nested parenthesis:
    (2*((4+3)/(4-2))) * 9
    I’ve used part of the code from another source and have adapted it to suit my needs.

    However, the trouble I am having with is evaluating cases such as these:-

    Code:
    -7*-8
    and

    Code:
    2*(-3+4)
    If a negative number is found without another number preceding it my program gets ‘fubared’. Or so it seems.

    Does anyone have any bright ideas to overcome this bug? I’ve highlighted the section of my code which is causing concern.

    Code:
    /*  
        A Simple expression evaluator which uses infix to postfix notation
        to evaluate an expression. Still has bugs which need to be fixed!!!
    */
    
    #include <iostream>
    #include <sstream>
    #include <string>
    #include <stack>
    #include <vector>
    
    using namespace std;
    //function declarations
    void Convert(const string & Infix, string & Postfix);
    bool IsOperand(char ch);
    bool TakesPrecedence(char OperatorA, char OperatorB);
    
    /*My functions I've added*/
    string Change_me(string);
    string Insert_comma(string);
    bool Check_valid(string);
    double Eval(string[]);
    void Next(string);
    
    int main()
    {
       
       char Reply;
    
       do
          {
          string Infix, Postfix; // local to this loop
    
          cout <<"\n    Enter your expression with No spaces!\n\n";
          cout <<"     e.g. (4+2)*3/2 "<< endl;
          cout <<"    Unknown variables such as 'a' and 'x' are not allowed:\n\n>>";
          cin >> Infix;
          
            if(Check_valid(Infix)==true)
            {
    
             string temp;
             temp = Change_me(Infix);
    
             Convert(temp, Postfix);
          
             cout << "The equivalent postfix expression is:" << endl
             <<Insert_comma(Postfix);
    
             string hold;
             hold = Insert_comma(Postfix);
             
             cout<<"\n\nThe answer is:";
             Next(hold);
     
             cout << endl << "\nDo another (y/n)? ";
             cin >> Reply;
            }
            else
            {
                cout<<"Now what did I say about using variables huh?\n";
                cout << endl << "Do another (y/n)? ";
                cin >> Reply;
                
            }       
              
          }while (tolower(Reply) == 'y');
    
       return 0;
    }
    
    
    /* Given:  ch   A character.
       Task:   To determine whether ch represents an operand (here understood
               to be a single letter or digit).
       Return: In the function name: true, if ch is an operand, false otherwise.
    */
    bool IsOperand(char ch)
    {
       if (((ch >= 'a') && (ch <= 'z')) ||
          ((ch >= 'A') && (ch <= 'Z')) ||
          ((ch >= '0') && (ch <= '9')))
          return true;
       else
          return false;
    }
    
    
    /* Given:  OperatorA    A character representing an operator or parenthesis.
               OperatorB    A character representing an operator or parenthesis.
       Task:   To determine whether OperatorA takes precedence over OperatorB.
       Return: In the function name: true, if OperatorA takes precedence over
               OperatorB.
    */
    bool TakesPrecedence(char OperatorA, char OperatorB)
    {
       if (OperatorA == '(')
          return false;
       else if (OperatorB == '(')
          return false;
       else if (OperatorB == ')')
          return true;
       //else if ((OperatorA == '^') && (OperatorB == '^'))
          //return false;
       //else if (OperatorA == '^')
          //return true;
       //else if (OperatorB == '^')
          //return false;
       else if ((OperatorA == '*') || (OperatorA == '/'))
          return true;
       else if ((OperatorB == '*') || (OperatorB == '/'))
          return false;
       else
          return true;
          
    }
    
    /* Given:  Infix    A string representing an infix expression (no spaces).
       Task:   To find the postfix equivalent of this expression.
       Return: Postfix  A string holding this postfix equivalent.
    */
    void Convert(const string & Infix, string & Postfix)
    {
       stack<char> OperatorStack;
       char TopSymbol, Symbol;
       int k;
    
       for (k = 0; k < Infix.size(); k++)
          {
          Symbol = Infix[k];
          if (IsOperand(Symbol))
             Postfix = Postfix + Symbol;
          else
             {
             while ((! OperatorStack.empty()) &&
                (TakesPrecedence(OperatorStack.top(), Symbol)))
                {
                TopSymbol = OperatorStack.top();
                OperatorStack.pop();
                Postfix = Postfix + TopSymbol;
                }
             if ((! OperatorStack.empty()) && (Symbol == ')'))
                OperatorStack.pop();   // discard matching (
             else
                OperatorStack.push(Symbol);
             }
          }
    
       while (! OperatorStack.empty())
          {
          TopSymbol = OperatorStack.top();
          OperatorStack.pop();
          Postfix = Postfix + TopSymbol;
          }
    }
    /*---------------------------------------------
      My function needed to tokenise the expression
      --------------------------------------------*/  
          
    string Change_me(string my_string)
    {
        for(int i = 0; i <my_string.length(); i++)
        {
          if(isdigit(my_string[i])!=0)
          {
              if(isdigit(my_string[i+1])==0)
              {  
                  my_string.insert(i+1, "v");
                  //v is just an arbitary choice
                  //it could be any other letter
                  //but it has to be a LETTER
                     
              }    
          }    
        }
    
        return my_string;
    }  
    
    /*-----------------------------------------
      My function needed to tokenise expression
      -----------------------------------------*/ 
    string Insert_comma(string my_string)
    {
        for(int i = 0; i <my_string.length(); i++)
        {
          if((my_string[i]=='*')||
             (my_string[i]=='-')||
             (my_string[i]=='/')||
             (my_string[i]=='+'))
              {
                my_string.insert(i+1, ",");
                //Insert a comma after all
                //found operators
              } 
               else if(my_string[i]=='v')
               {
                  my_string.replace(i,1,",");
                  //replace the v with a comma
                  //for clarity
               }               
        }
        return my_string; 
    }   
    
    /*-----------------------------------------
      My function to check that no variables
      were entered
      -----------------------------------------*/ 
    bool Check_valid(string my_string)
    {
        string array="0123456789+-*/()";
    
        int count=0;
        for (int i=0; i<my_string.length(); i++)
        {
            for(int j=0; j<array.length(); j++)
            {
                if(my_string[i]==array[j])
                {
                   count++;
                }
            }
        }
        
        if (count == my_string.length())
        {
          return true;   
        }
        else
        {   
          return false;   
        }
                
    }  
    
    /*-----------------------------------
      My function to actually evaluate
      postfix expression
      ----------------------------------*/
    
    void Next(string my_string)
    {
      vector <string> array; 
      string tempy;
      
      int comma_count=0;
      for (int a=0; a<my_string.length();a++)
      {
          if(my_string[a]==',')
          {
              comma_count++;
          }
      }        
    
      //Evaluate tokens using the "," as a delimiter
      while (my_string.find(",", 0) != string::npos)
      { 
        //lifted from the FAQ
        //does the string have a comma in it?
        size_t pos = my_string.find(",", 0); 
        tempy = my_string.substr(0, pos);      
        my_string.erase(0, pos + 1);           
        array.push_back(tempy); //store in vector              
      }
    
      //array.push_back(my_string);//the last token is all alone 
      
      stack <string> my_stack;//initialise stack
      string temp[100];
      string ch;
      
      for (int i=0; i<comma_count; i++)
      {
          
          string s;
          s=array[i]; //make it easier to read
          
          if ((s!="+")&&
              (s!="*")&&
              (s!="-")&&
              (s!="/"))
               {
                 my_stack.push(s);
                 //push numbers onto the stack
               }
             else //i.e if it encounters an operator
             {
                   my_stack.push(s);//push operator onto stack
                   temp[0]= my_stack.top();//store value
                   my_stack.pop(); //erase from the stack
                 
                   temp[1]= my_stack.top();//store value
                   my_stack.pop();//erase from the stack
                   
                   if (! my_stack.empty())
                   {
                   temp[2]= my_stack.top();//store value
                   my_stack.pop();//erase from the stack
                   }
                   else
                   {
                       //for the rogue case -2-3...
                       //but doesn't work for everything
                       my_stack.push("0");
                       temp[2]= my_stack.top();
                       my_stack.pop();
                   }         
    
                   double z;
                   z = Eval(temp);
                   ostringstream outs;  // Declare an output string stream.
                   outs << z;   // Convert value into a string.
                   ch = outs.str(); 
    
                   my_stack.push(ch);
      
               }                
      }
      cout<<ch;  
      cin.get(); 
    } 
    /*------------------------------
      My function to do the math:
      Converts string to double
      then back to string
      ------------------------------*/
    double Eval(string temp[])
    {
        string a,b,c;
        a=temp[2]; b=temp[0]; c=temp[1];
        double x,y,z;
        istringstream ins,inse;
        ins.str(a);inse.str(c);
        ins >> x;
        inse >> y;
        
         if (b=="+")
         {
            z = x + y;
            return z;
         } 
         else if (b=="-")
         {
            z = x - y;
            return z;
         } 
         else if (b=="*")
         {
            z = x * y;
            return z;
         }
         else if (b=="/")
         {
            z = x / y;
            return z;
         }                    
    }
    There are other problems such as these cases:

    Code:
    7-+7  - two operators found consecutively
    and

    Code:
    ((2+3)   - missing a bracket
    However, I plan to deal with these later.

  2. #2
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    When I worked on this type of problem in the past I determined the char immediateyly before the current char and depending on the result I determined how to handle the current char. As a possibility, consider the following sequence:

    If the current char is a - sign:
    A) and there was no previous char or the previous char was a (, +, or a -, then the operator indicates a negative sign
    B) the previous char was a digit or a ) or a decimal point, then the operator indicates subtraction
    C) else input error.

    You can do a similar analysis for the + sign.
    You're only born perfect.

  3. #3
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    Yes that was what I was originally thinking. I guess I just have to implement it!


    Oh and while we're on the subject, I know that you and Hunter2 managed to get your program working for equations that have multiple nesting. Like:-


    Code:
    (x*(x+2) -3) + (x-1)*(x-2) = 9
    With the design I have at the moment I don't see this to be a problem.

    Let's be honest once you can do this you're halfway there.

    However, I noticed neither of you developed a reliable system to handle a fraction. At least that is what I discovered after testing.

    Anyway, I was thinking that the case of division should be given its own special function or class...


    Code:
      4         6
    ------  =  ------
    x + 3      4 -x
    I was thinking the above equation might be parsed like:-

    Code:
    [4/x+3]=[6/4-x]
    So the square brackets would indicate a fraction was being entered.

    Then it would make life easier for the parsing algorithm to cross multiply off the bottom so as to arrive at:-

    Code:
    4*(4-x) = 6*(x+3)
    Which can then be easily evaluated using the system you already have in place?

    Although I've noticed the software powered by mathematica you would parse the fraction like so:-

    4/(x+3) = 6/(4-x)

    http://www.algebra.com/algebra/homework/general/#Solve

    One other question. How long do you think it might take to develop a program to handle first order multi-variable equations?
    Like the ones used in the above link?

    Great to see you BTW.

  4. #4
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    Ok I need people to test my amended 'simple expression evaluator' and report any bugs.

    So far I have restricted my program to handling only numbers.
    If you find any bugs please post them along with the error they produced. Thank you!!!

    Code:
    /*  
        A Simple expression evaluator which uses infix to postfix notation
        to evaluate an expression. Still has bugs which need to be fixed!!!
        V.0.2 -> To handle operator anomolies such as:
        -7*-4    and  2*(-5+6)
    */
    
    #include <iostream>
    #include <sstream>
    #include <string>
    #include <stack>
    #include <vector>
    
    using namespace std;
    //function declarations
    void Convert(const string & Infix, string & Postfix);
    bool IsOperand(char ch);
    bool TakesPrecedence(char OperatorA, char OperatorB);
    
    /*My functions I've added*/
    string Change_me(string);
    string Insert_comma(string);
    bool Check_valid(string);
    double Eval(string[]);
    void Next(string);
    
    int main()
    {
       
       char Reply;
    
       do
          {
          string Infix, Postfix; // local to this loop
    
          cout <<"\n    Enter your expression with No spaces!\n\n";
          cout <<"     e.g. (4+2)*3/2 "<< endl;
          cout <<"    Unknown variables such as 'a' and 'x' are not allowed:\n\n>>";
          cin >> Infix;
          
            if(Check_valid(Infix)==true)
            {
    
             string temp;
             temp = Change_me(Infix);
             //cout<<temp;
             //cin.get();
    
             Convert(temp, Postfix);
          
             cout << "The equivalent postfix expression is:" << endl
             <<Insert_comma(Postfix);
    
             string hold;
             hold = Insert_comma(Postfix);
             
             cout<<"\n\nThe answer is:";
             Next(hold);
     
             cout << endl << "\nDo another (y/n)? ";
             cin >> Reply;
            }
            else
            {
                cout<<"***Syntax error***\n";
                cout << endl << "Do another (y/n)? ";
                cin >> Reply;
                
            }       
              
          }while (tolower(Reply) == 'y');
    
       return 0;
    }
    
    
    /* Given:  ch   A character.
       Task:   To determine whether ch represents an operand (here understood
               to be a single letter or digit).
       Return: In the function name: true, if ch is an operand, false otherwise.
    */
    bool IsOperand(char ch)
    {
       if (((ch >= 'a') && (ch <= 'z')) ||
          ((ch >= 'A') && (ch <= 'Z')) ||
          ((ch >= '0') && (ch <= '9')))
          return true;
       else
          return false;
    }
    
    
    /* Given:  OperatorA    A character representing an operator or parenthesis.
               OperatorB    A character representing an operator or parenthesis.
       Task:   To determine whether OperatorA takes precedence over OperatorB.
       Return: In the function name: true, if OperatorA takes precedence over
               OperatorB.
    */
    bool TakesPrecedence(char OperatorA, char OperatorB)
    {
       if (OperatorA == '(')
          return false;
       else if (OperatorB == '(')
          return false;
       else if (OperatorB == ')')
          return true;
       //else if ((OperatorA == '^') && (OperatorB == '^'))
          //return false;
       //else if (OperatorA == '^')
          //return true;
       //else if (OperatorB == '^')
          //return false;
       else if ((OperatorA == '*') || (OperatorA == '/'))
          return true;
       else if ((OperatorB == '*') || (OperatorB == '/'))
          return false;
       else
          return true;
          
    }
    
    /* Given:  Infix    A string representing an infix expression (no spaces).
       Task:   To find the postfix equivalent of this expression.
       Return: Postfix  A string holding this postfix equivalent.
    */
    void Convert(const string & Infix, string & Postfix)
    {
       stack<char> OperatorStack;
       char TopSymbol, Symbol;
       int k;
    
       for (k = 0; k < Infix.size(); k++)
          {
          Symbol = Infix[k];
          if (IsOperand(Symbol))
             Postfix = Postfix + Symbol;
          else
             {
             while ((! OperatorStack.empty()) &&
                (TakesPrecedence(OperatorStack.top(), Symbol)))
                {
                TopSymbol = OperatorStack.top();
                OperatorStack.pop();
                Postfix = Postfix + TopSymbol;
                }
             if ((! OperatorStack.empty()) && (Symbol == ')'))
                OperatorStack.pop();   // discard matching (
             else
                OperatorStack.push(Symbol);
             }
          }
    
       while (! OperatorStack.empty())
          {
          TopSymbol = OperatorStack.top();
          OperatorStack.pop();
          Postfix = Postfix + TopSymbol;
          }
    }
    /*---------------------------------------------
      My function needed to tokenise the expression
    
      --------------------------------------------*/  
          
    string Change_me(string my_string)
    {
        
        for(int i = 0; i <my_string.length(); i++)
        {
          if(isdigit(my_string[i])!=0)
          {
              if(isdigit(my_string[i+1])==0)
              {  
                  my_string.insert(i+1, "v");
                  //v is just an arbitary choice
                  //it could be any other letter
                  //but it has to be a LETTER
                     
              }    
          }    
        }
        //Changed -7*-7 case
        for (int i = 0; i <my_string.length(); i++)
        {
            if(my_string[i]=='-')
            {
                if(my_string[i-1]!='v')
                {
                   my_string.replace(i,1,"y"); 
                }
            }
        } 
    
        return my_string;
    }  
    
    /*-----------------------------------------
      My function needed to tokenise expression
      -----------------------------------------*/ 
    string Insert_comma(string my_string)
    {
        for(int i = 0; i <my_string.length(); i++)
        {
          if((my_string[i]=='*')||
             (my_string[i]=='-')||
             (my_string[i]=='/')||
             (my_string[i]=='+'))
              {
                my_string.insert(i+1, ",");
                //Insert a comma after all
                //found operators
              } 
               else if(my_string[i]=='v')
               {
                  my_string.replace(i,1,",");
                  //replace the v with a comma
                  //for clarity
               }               
        }
        //Changed
        for (int i = 0; i <my_string.length(); i++)
        {
            if(my_string[i]=='y')
            {
                 my_string.replace(i,1,"-");
             }
         }    
        return my_string; 
    }   
    
    /*-----------------------------------------
      My function to check that no variables
      were entered
      -----------------------------------------*/ 
    bool Check_valid(string my_string)
    {
        //Changed check that consecutive '+', '-' 
        //signs do not exist
        for (int i = 0; i<my_string.length(); i++)
        {
            if((my_string[i]=='+')||(my_string[i]=='-'))
            {
                if((my_string[i+1]=='+')||(my_string[i+1]=='-'))
                {
                    return false;
                }
            }
        }            
            
            
        string array="0123456789+-*/()";
    
        int count=0;
        for (int i=0; i<my_string.length(); i++)
        {
            for(int j=0; j<array.length(); j++)
            {
                if(my_string[i]==array[j])
                {
                   count++;
                }
            }
        }
        
        if (count == my_string.length())
        {
          return true;   
        }
        else
        {   
          return false;   
        }
                
    }  
    
    /*-----------------------------------
      My function to actually evaluate
      postfix expression
      ----------------------------------*/
    
    void Next(string my_string)
    {
      vector <string> array; 
      string tempy;
      
      int comma_count=0;
      for (int a=0; a<my_string.length();a++)
      {
          if(my_string[a]==',')
          {
              comma_count++;
          }
      }        
    
      //Evaluate tokens using the "," as a delimiter
      while (my_string.find(",", 0) != string::npos)
      { 
        //lifted from the FAQ
        //does the string have a comma in it?
        size_t pos = my_string.find(",", 0); 
        tempy = my_string.substr(0, pos);      
        my_string.erase(0, pos + 1);           
        array.push_back(tempy); //store in vector              
      }
    
      //array.push_back(my_string);//the last token is all alone 
      
      stack <string> my_stack;//initialise stack
      string temp[100];
      string ch;
      
      for (int i=0; i<comma_count; i++)
      {
          
          string s;
          s=array[i]; //make it easier to read
          
          if ((s!="+")&&
              (s!="*")&&
              (s!="-")&&
              (s!="/"))
               {
                 my_stack.push(s);
                 //push numbers onto the stack
               }
             else //i.e if it encounters an operator
             {
                   my_stack.push(s);//push operator onto stack
                   temp[0]= my_stack.top();//store value
                   my_stack.pop(); //erase from the stack
                 
                   temp[1]= my_stack.top();//store value
                   my_stack.pop();//erase from the stack
                   
                   temp[2]= my_stack.top();//store value
                   my_stack.pop();//erase from the stack
                
    
                   double z;
                   z = Eval(temp);
                   ostringstream outs;  // Declare an output string stream.
                   outs << z;   // Convert value into a string.
                   ch = outs.str(); 
    
                   my_stack.push(ch);
      
               }                
      }
      cout<<ch;  
      cin.get(); 
    } 
    /*------------------------------
      My function to do the math:
      Converts string to double
      then back to string
      ------------------------------*/
    double Eval(string temp[])
    {
        string a,b,c;
        a=temp[2]; b=temp[0]; c=temp[1];
        double x,y,z;
        istringstream ins,inse;
        ins.str(a);inse.str(c);
        ins >> x;
        inse >> y;
        
         if (b=="+")
         {
            z = x + y;
            return z;
         } 
         else if (b=="-")
         {
            z = x - y;
            return z;
         } 
         else if (b=="*")
         {
            z = x * y;
            return z;
         }
         else if (b=="/")
         {
            z = x / y;
            return z;
         }                    
    }

  5. #5
    Registered User
    Join Date
    Mar 2005
    Posts
    140
    Bug

    Code:
    >>((2*2)-1)/3
    The equivalent postfix expression is:
    2,2,*,-1,3,/,
    
    The answer is:-0.333333
    should be
    2 2 * 1 - 3 /


    Actually I believe the 5th case in your original post fails as well. In other words looks like a nested paren problem.

  6. #6
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    ***Fixed

    Code:
    /*---------------------------------------------
      My function needed to tokenise the expression
    
      --------------------------------------------*/  
          
    string Change_me(string my_string)
    {
        
        for(int i = 0; i <my_string.length(); i++)
        {
          if(isdigit(my_string[i])!=0)
          {
              if(isdigit(my_string[i+1])==0)
              {  
                  my_string.insert(i+1, "v");
                  //v is just an arbitary choice
                  //it could be any other letter
                  //but it has to be a LETTER
                     
              }    
          }    
        }
        //Changed -7*-7 case
        for (int i = 0; i <my_string.length(); i++)
        {
            if(my_string[i]=='-')
            {
                if((my_string[i-1]!='v')&&(my_string[i-1]!=')'))
                {
                   my_string.replace(i,1,"y"); 
                }
            }
        } 
    
        return my_string;
    }

    Actually I believe the 5th case in your original post fails as well. In other words looks like a nested paren problem.
    I don't think this was a problem to begin with but appears to work...

    My sample input/output:


    Code:
        Enter your expression with No spaces!
    
         e.g. (4+2)*3/2
        Unknown variables such as 'a' and 'x' are not allowed:
    
    >>(2*((4+3)/(4-2)))*9
    The equivalent postfix expression is:
    2,4,3,+,4,2,-,/,*,9,*,
    
    The answer is:63
    
    Do another (y/n)?
    Spydoor thank you for testing this. If anyone sees any other glaring bugs please let me know. Thank you for you time.

Popular pages Recent additions subscribe to a feed