Question

Arithmetic Expression Evaluation

Write a program that reads an infix expression (that contains only A, B and/or C as operands) from

the user and prints out the value of the expression as an output.

Implement the following methods:

o String infixToPostfix(String expr)

Converts the given infix expression expr and returns the corresponding postfix notation

of expr.

o Integer evaluatePostfixExpr(String expr)

Evaluates and returns the value of the given postfix expression expr.

Sample Input/Output #1

Enter your arithmetic expression: A+B-C*A

Enter the value of A: 5

Enter the value of B: 10

Enter the value of C: 2

The postfix expression is AB+CA*-

The above expression evaluates to 5.

Sample Input/Output #2

Enter your arithmetic expression: A+BC

Enter the value of A: 5

Enter the value of B: 10

Enter the value of C: 2

The above expression is invalid and can't be evaluated.

Answer 1

#include<bits/stdc++.h> 
using namespace std; 

//Function to return precedence of operators 
int prec(char c) 
{ 
        if(c == '^') 
        return 3; 
        else if(c == '*' || c == '/') 
        return 2; 
        else if(c == '+' || c == '-') 
        return 1; 
        else
        return -1; 
} 

string infixToPostfix(string s) 
{ 
        stack<char> st; 
        st.push('N'); 
        int l = s.length(); 
        string ns; 
        for(int i = 0; i < l; i++) 
        { 
                if(s[i] >= 'A' && s[i] <= 'C')
                ns+=s[i]; 
                else if(s[i] == '(') 
                st.push('('); 
                else if(s[i] == ')') 
                { 
                        while(st.top() != 'N' && st.top() != '(') 
                        { 
                                char c = st.top(); 
                                st.pop(); 
                        ns += c; 
                        } 
                        if(st.top() == '(') 
                        { 
                                char c = st.top(); 
                                st.pop(); 
                        } 
                } 
                else{ 
                        while(st.top() != 'N' && prec(s[i]) <= prec(st.top())) 
                        { 
                                char c = st.top(); 
                                st.pop(); 
                                ns += c; 
                        } 
                        st.push(s[i]); 
                } 
        } 
        while(st.top() != 'N') 
        { 
                char c = st.top(); 
                st.pop(); 
                ns += c; 
        } 
        return ns;
} 
int operation(int a, int b, char op) {
   if(op == '+')
      return b+a;
   else if(op == '-')
      return b-a;
   else if(op == '*')
      return b*a;
   else if(op == '/')
      return b/a;
   else if(op == '^')
      return pow(b,a); //find b^a
   else
      return INT_MIN; //return negative infinity
}
int evaluatePostfixExpr(string postfix,int Aval,int Bval,int Cval) {
   int a, b;
   stack<int> stk;
   string::iterator it;
   for(it=postfix.begin(); it!=postfix.end(); it++) {
      if((*it) == '+'|| (*it) == '-'|| (*it) == '*'|| (*it) == '/' || (*it) == '^') 
      {
         a = stk.top();
         stk.pop();
         b = stk.top();
         stk.pop();
         stk.push(operation(a, b, *it));
      }
      else if((*it)>='A' && (*it)<='C') {
          {
              if((*it)=='A')
              stk.push(Aval);
              else if((*it)=='B')
              stk.push(Bval);
              else
              stk.push(Cval);
          }
      }
   }
   return stk.top();
}
bool isvalidpostfix(string postfix)
{
    stack<int>myStack;
    for(int i = 0; postfix[i] != '\0'; i++)
    {
         if(postfix[i] != '+' && postfix[i] != '-' && postfix[i] != '/' && postfix[i] != '*')
         myStack.push(postfix[i]);
         else        
         {                           
             if(myStack.size() >= 2)
                {
                    myStack.pop();
                    myStack.pop();
                }
             else
             {
                 return 1;
             }
         }
    }
    return 0;
}
int main() 
{ 
        string exp;
        int aval,bval,cval;
        cout<<"Enter your arithmetic expression: ";
        cin>>exp;
        cout<<"NOW ENTER VALUES OF VARIABLES PRESENT IN EQUATION AND IF NOT PRESENT THEN ENTER ZERO\n";
        cout<<"Enter the value of A: ";
        cin>>aval;
        cout<<"\nEnter the value of B: ";
        cin>>bval;
        cout<<"\nEnter the value of C: ";
        cin>>cval;
        string postfix=infixToPostfix(exp);
        if(isvalidpostfix(postfix)==0)
        cout<<"\nThe above expression is invalid and can't be evaluated.";
        else
        {
            cout<<"\nThe postfix expression is "<<postfix;
            cout<<"\nThe above expression evaluates to "<<evaluatePostfixExpr(postfix,aval,bval,cval);
        }
        return 0; 
}