Question

C++ PROGRAMING

Implement a program to evaluate simple mathematical expressions. Assume that the original expression is provided to the program as a text string. Allowed expression tokens: brackets “(” and “)”, integers like “4”, “15”, addition “+”, subtraction “-”, multiplication “*”, division “/”. Output can be float. Trim spaces from an expression. Brackets should contain at least one operation. Make sure that an expression is validated before it is calculated; reject the invalid expressions with appropriate message. The program must have easy interface (could be console-based) to interact with. Hint: use two stacks to store operands (integers) and operators (+,-,*,/). For brackets – develop a tracking system that could allow solving expressions orderly. After you have implemented and tested the functionality listed above, please make sure to follow the running script and show your results in screenshots.

Running Script

1. Enter expression “(5 + 9) * (4 – 5) / 9 + 5”. Validate it, reject with error if it is invalid. 2. Process the expression. Display the answer if the expression was valid. 3. Enter expression “( 9 ) * 5 – 9 / 10 + 0”. Validate it, reject with error if it is invalid. 4. Process the expression. Display the answer if the expression was valid. 5. Enter expression “(((((((5 + 1)))) 2 - 4)))”. Validate it, reject with error if it is invalid. 6. Process the expression. Display the answer if the expression was valid. 7. Enter expression “(15 * 2 – (5 + 3 / (4 + 5)))”. Validate it, reject with error if it is invalid. 8. Process the expression. Display the answer if the expression was valid. 9. Enter an inherently valid expression of your own (make a complex one!). Validate it, reject with error if it is invalid. 10. Process the expression. Display the answer if the expression was valid

Answer 1

N.B. Enter input expression without blank space, and enter single digit numbers only.

Program

#include<iostream>
#include<ctype.h>
#include<string.h>

using namespace std;

const int SIZE = 50;

class Stack
{
   char stk[SIZE];
   int tos;
public:
   void init();
   void push(char);
   char pop(void);
   int preced(char);
   char* infixToPostfix(char[]);
   float valueOf(char, char, char);
   float evaluate(char []);
};

void Stack::init()
{
   tos = -1;
}

void Stack::push(char item)
{
   if(tos==SIZE-1)
       printf("stack overflow");
   else
   {
       tos++;
       stk[tos]=item;
   }
}

char Stack::pop()
{
   if(tos==-1){
       printf("stack underflow");
       return ' ';
   }
  
   char c;
   c=stk[tos];
   tos--;
   return c;
}

int Stack::preced(char x)
{
   switch(x)
   {
       case '(':
           return 0;

       case '+':
       case '-':
           return 1;

       case '*':
       case '/':
           return 2;
   }
}

char* Stack::infixToPostfix(char input[])
{
   char *output = new char[SIZE];
  
   int i=0,j=0;
   char p1, p2;
  
   push('(');

   while(input[i]!='\0')
   {
       if(isdigit(input[i]))
       {
           output[j]=input[i];
           j++;
       }
       else if(input[i]=='(')
       {
           push('(');
       }
       else if(input[i]==')')
       {
           while(stk[tos]!='(')
           {
           output[j]=pop();
           j++;
           }
           pop();
       }
       else
       {
       p1=preced(input[i]);
       p2=preced(stk[tos]);

       while(stk[tos]!='(' && p1<=p2)
       {
           output[j]=pop();

           j++;
           p2=preced(stk[tos]);
       }
       push(input[i]);
       }
       i++;
   }
   while(stk[tos]!='(')
   {
       output[j]=pop();
       j++;
   }
   output[j]='\0';
  
   return output;
}

float Stack::evaluate(char expr[])
{
int c, i;
char opnd1,opnd2;
float value;

   for(i=0;(c=expr[i])!='\0';i++)
   {
       if(isdigit(c))
           push(c-'0');
       else{
           opnd2=pop();
           opnd1=pop();
           value=valueOf(c,opnd1,opnd2);
           push(value);
       }
   }
return(pop());
}

float Stack::valueOf(char symb, char op1, char op2)
{
   switch(symb)
{
   case '+':
       return(op1+op2);
   case '-':
       return(op1-op2);
   case '*':
       return(op1*op2);
   case '/':
       return(op1/op2);
   default:
       printf("Illegal operation.\n");
       return(0);
   }
}

int main()
{
   Stack s;
   char *output = new char[SIZE];
   char input[SIZE], ch;
  
   do
   {
       s.init();
       cout<<"Enter the expression: ";
       gets(input);
      
       output = s.infixToPostfix(input);
       float f = s.evaluate(output);
          
       cout<<"Value of the expression is "<<f<<endl;
      
       cout<<"Are you want to continue?(y/n): ";
      
       cin>>ch;
       cin.ignore();
      
   }while(ch=='y' || ch=='Y');
  
   system("pause");
  
   return 0;
}

Output

Modified Program

#include<iostream>
#include<string>
#include <bits/stdc++.h>

using namespace std;

const int SIZE = 50;

class Stack
{
private:
   string stk[SIZE];
   int tos;
public:
   void init();
   void push(string);
   string pop(void);
   int preced(string);
   string* infixToPostfix(string []);
   float valueOf(string, string, string);
   float evaluate(string []);
   void checkValidity(string []);
};

void Stack::init()
{
   tos = -1;
}

void Stack::push(string item)
{
   if(tos==SIZE-1) throw "stack overflow";
   stk[++tos]=item;
}

string Stack::pop()
{
   if(tos==-1) throw "stack underflow";
   return stk[tos--];
}

int Stack::preced(string y)
{
   char x = y[0];
  
   switch(x)
   {
       case '+':
       case '-':
           return 1;

       case '*':
       case '/':
           return 2;
   }
}

bool isNumber(string line)
{
char* p;
strtol(line.c_str(), &p, 10);
return *p == 0;
}

void Stack::checkValidity(string input[])
{
   init();
   for(int i=0; input[i]!=""; i++)
   {
       if(input[i]=="(") push("(");
       else if(input[i]==")") pop();
   }
  
   if(tos!=-1) throw "Invalid expression";
}

string* Stack::infixToPostfix(string input[])
{
   string *output = new string[SIZE];
  
   int j=0;
   string p1, p2;
  
   init();
  
   push("(");

   for(int i=0; input[i]!=""; i++)
   {
       if(isNumber(input[i]))
       {
           output[j++]=input[i];
       }
       else if(input[i]=="(")
       {
           push("(");
       }
       else if(input[i]==")")
       {
           while(stk[tos]!="(")
           {
           output[j++]=pop();
           }
           pop();
       }
       else
       {
       p1=preced(input[i]);
       p2=preced(stk[tos]);

       while(stk[tos]!="(" && p1<=p2)
       {
           output[j++]=pop();
           p2=preced(stk[tos]);
       }
       push(input[i]);
       }
   }
   while(stk[tos]!="(")
   {
       output[j++]=pop();
   }
  
   return output;
}

float Stack::evaluate(string expr[])
{
   int i;
   string c, opnd1,opnd2;
   float value;

   init();

   for(i=0;(c=expr[i])!="";i++)
   {
       if(isNumber(c))
           push(c);
       else{
           opnd2 = pop();
           opnd1 = pop();
           value = valueOf(c,opnd1,opnd2);
           string s = to_string(value);
           push(s);
       }
   }

value = stof(pop());
return value;
}

float Stack::valueOf(string sym, string ops1, string ops2)
{
   char symb = sym[0];
float op1 = stof(ops1);
float op2 = stof(ops2);
  
   switch(symb)
{
   case '+':
       return(op1+op2);
   case '-':
       return(op1-op2);
   case '*':
       return(op1*op2);
   case '/':
       return(op1/op2);
   }
}

int main()
{
   Stack s;
   string *output = new string[SIZE];
   char *inchars = new char[SIZE];
   string *tokens = new string[SIZE];
   char ch;
   string input;
  
   do
   {
       try{
  
       cout<<"Enter the expression: ";
       getline(cin, input);
  
   strcpy(inchars, input.c_str());
   int i=0;
   char* token;
   const char *delim = "+-*/()";
  
   for(int j=0; j<inchars[j]!='\0'; j++)
   {
       char c = inchars[j];
       if(c==' ') continue;
       if(strrchr(delim, c)!=NULL)
       {
           string s(1, c);
       tokens[i++] = s;
           }
           else if(isdigit(c))
           {
               int x = 0;
               while(isdigit(c))
               {
                   x = x*10 + (c - '0');
                   c = inchars[++j];
               }
               string s = to_string(x);
               tokens[i++] = s;
               j--;
           }
       }
       s.checkValidity(tokens);
       output = s.infixToPostfix(tokens);
       float f = s.evaluate(output);
          
       cout<<"Value of the expression is "<<f<<endl;
      
       }catch(const char se[]){
           cout<<"Exception: "<<se<<endl;
       }
      
       cout<<"Are you want to continue?(y/n): ";
      
       cin>>ch;
       cin.ignore();
      
   }while(ch=='y' || ch=='Y');
  
   system("pause");
  
   return 0;
}

N.B. In this program you can enter blank space while entering expression, you can use multiple digit numbers. You should use the following command to compile this program:

g++ -std=c++11 expression.cpp

Enter the expression: 9*5 value of the expression is 45 Are you want to continue?(y/n): y Enter the expression: (2+4) *7 Value of the expression is Are you want to continue?( y/n) : y Enter the expression: ((9+7) ) Value of the expression is 16 Are you want to continue?(y/n): n