Write a C++ program that will take any input infix computation consisting of (,

Question

Write a C++ program that will take any input infix computation consisting of (, ), +, -, *, / and positive numeric operands and convert it to postfix. Use a stack, as was demonstrated in class. Secondly, use the postfix form of the computation to actually calculate the result of applying the operators to the operands. In other words, use the output of the first part (a postfix string) to calculate the result.

The precedence order is as follows:

•* / = operators which have same precedence

•+ - = operators which have same precedence

•) = lower precedence than the operators

•( = lowest precedence

The computation should be input as a single string.  Assume it is always correct with regard to format and parenthesis balancing, so you don't need to address errors.

Explanation / Answer

Please find the required program below :

#include<iostream>
#include<stack>
#include<string>

using namespace std;

string InfixToPostfix(string expression);

int HasHigherPrecedence(char operator1, char operator2);

bool IsOperator(char C);

bool IsOperand(char C);

const char * expressionToParse;
// = "3*2+4*1+(4+9)*6";

char peek()
{
return *expressionToParse;
}

char get()
{
return *expressionToParse++;
}

int expression();

int number()
{
int result = get() - '0';
while (peek() >= '0' && peek() <= '9')
{
result = 10*result + get() - '0';
}
return result;
}

int factor()
{
if (peek() >= '0' && peek() <= '9')
return number();
else if (peek() == '(')
{
get(); // '('
int result = expression();
get(); // ')'
return result;
}
else if (peek() == '-')
{
get();
return -factor();
}
return 0; // error
}

int term()
{
int result = factor();
while (peek() == '*' || peek() == '/')
if (get() == '*')
result *= factor();
else
result /= factor();
return result;
}

int expression()
{
int result = term();
while (peek() == '+' || peek() == '-')
if (get() == '+')
result += term();
else
result -= term();
return result;
}

int main()
{
   string exp;
   cout<<"Enter Infix Expression ";
   getline(cin,exp);
   string postfix = InfixToPostfix(exp);
   cout<<"Postfix = "<<postfix<<" ";
   expressionToParse = postfix.c_str();
   int result = expression();
   cout << "Output = "<<result<<" ";
}

string InfixToPostfix(string expression)
{
   stack<char> S;
   string postfix = "";
   for(int i = 0;i< expression.length();i++) {

       if(expression[i] == ' ' || expression[i] == ',') continue;

       else if(IsOperator(expression[i]))
       {
           while(!S.empty() && S.top() != '(' && HasHigherPrecedence(S.top(),expression[i]))
           {
               postfix+= S.top();
               S.pop();
           }
           S.push(expression[i]);
       }
       else if(IsOperand(expression[i]))
       {
           postfix +=expression[i];
       }

       else if (expression[i] == '(')
       {
           S.push(expression[i]);
       }

       else if(expression[i] == ')')
       {
           while(!S.empty() && S.top() != '(') {
               postfix += S.top();
               S.pop();
           }
           S.pop();
       }
   }

   while(!S.empty()) {
       postfix += S.top();
       S.pop();
   }

   return postfix;
}

bool IsOperand(char C)
{
   if(C >= '0' && C <= '9') return true;
   if(C >= 'a' && C <= 'z') return true;
   if(C >= 'A' && C <= 'Z') return true;
   return false;
}

bool IsOperator(char C)
{
   if(C == '+' || C == '-' || C == '*' || C == '/' || C== '$')
       return true;

   return false;
}

int IsRightAssociative(char op)
{
   if(op == '$') return true;
   return false;
}

int GetOperatorWeight(char op)
{
   int weight = -1;
   switch(op)
   {
   case '+':
   case '-':
       weight = 1;
   case '*':
   case '/':
       weight = 2;
   case '$':
       weight = 3;
   }
   return weight;
}

int HasHigherPrecedence(char op1, char op2)
{
   int op1Weight = GetOperatorWeight(op1);
   int op2Weight = GetOperatorWeight(op2);

   if(op1Weight == op2Weight)
   {
       if(IsRightAssociative(op1)) return false;
       else return true;
   }
   return op1Weight > op2Weight ? true: false;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.