Convert expressions that are in infix notation to postfix notation. The expressi

Question

Convert expressions that are in infix notation to postfix notation. The expressions might contain parentheses and these operators: =, ONLY, NEVER, AND, OR.

Precedence rules

• Evaluate contents in () before others

• =, NEVER, ONLY - high precedence

• AND, OR - lower precedence

Create your code in p1abc123.c

int convertToPostfix(char *pszInfix, Out out)

It returns 0 if it converted successfully. Otherwise, it returns a value which indicates an error in the infix expression (e.g., missing left paren, missing right paren). It populates the out array using the addPostfixOut function (provided in the driver).

Have a program that reads infix notations and convert that to postfix notation

Examples Postfix Infix RECITN RECITY RECIT N- RECIT Y = PROF NEVER CLARK PROF ONLY CLARK PROF NEVER CLARK AND DEPT = CS RECIT = Y AND PROF = CLARK OR PROF = GIBSON PROF CLARK- PROF CLARK NEVER PROF CLARK ONLY PROF CLARK NEVER DEPT CS = AND RECIT Y = RECEPAOE CLARK-PADE CLARK = PROF GIBSON OR AND

Explanation / Answer

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

int convertToPostFix(std::string& expression, std::string& output)
{
  
   std::stack<std::string> operatorStack;
   std::istringstream stream(expression);
   std::string token;
   while(!stream.eof())
   {
       stream >> token;

       switch(token.size())
       {
           case 1:
               if(token.compare("(") == 0)
               {
                   operatorStack.push(token);
               }
               else if(token.compare(")") == 0)
               {
                   while(operatorStack.top() != "(" && !operatorStack.empty())
                   {
                       output = output + " " + operatorStack.top() ;
                       operatorStack.pop();
                   }
                   //pop the left parenthesis
                   if(!operatorStack.empty()) operatorStack.pop();
               }
               else if(token.compare("=") == 0)
               {
                   operatorStack.push(token);
               }
               else
                   output = output + " " + token;
           break;

           case 2:
               if (token.compare("OR") == 0)
               {
                   std::string top;
                   if (!operatorStack.empty()) top = operatorStack.top();
          
                   while(top.compare("=") == 0 ||
                       top.compare("NEVER") == 0 ||
                       top.compare("ONLY") == 0
                       )
                   {
                       output = output + " " + top;
                       operatorStack.pop();
                       if (!operatorStack.empty()) top = operatorStack.top();
                       else break;
                   }
                   operatorStack.push(token);
               }
               else
                   output = output + " " + token;
           break;

           case 3:
               if (token.compare("AND") == 0)
               {
                   std::string top;
                   if (!operatorStack.empty()) top = operatorStack.top();

                   while(top.compare("=") == 0 ||
                       top.compare("NEVER") == 0 ||
                       top.compare("ONLY") == 0
                       )
                   {
                       output = output + " " + top;
                       operatorStack.pop();
                       if (!operatorStack.empty()) top = operatorStack.top();
                       else break;
                   }
                   operatorStack.push(token);
               }
               else
                   output = output + " " + token;
           break;

           case 4:
               if (token.compare("ONLY") == 0)
               {
                   operatorStack.push(token);
               }
               else
                   output = output + " " + token;
           break;

           case 5:
               if (token.compare("NEVER") == 0)
               {
                   operatorStack.push(token);
               }
               else
                   output = output + " " + token;
           break;

           default:
               output = output + " " + token;
       }

   }

   while(!operatorStack.empty())
   {  
       output = output + " " + operatorStack.top();
       operatorStack.pop();
   }  
   return 0;
}

int main(int argc, char const *argv[])
{
   std::string expression[6] = { "RECIT = Y",
                                   "PROF = CLARK",
                                   "PROF NEVER CLARK",
                                   "PROF ONLY CLARK",
                                   "PROF NEVER CLARK AND DEPT = CS",
                                   "RECIT = Y AND ( PROF = CLARK OR PROF = GIBSON )"};
   std::string output[6];
   std::cout << "============================================================== ";
   for (int i = 0; i < 6; ++i)
   {
       int retCode = convertToPostFix(expression[i], output[i]);
       std::cout << "Input: " << expression[i] << " "
                   << "Output: " << output[i] << " "
                   << "============================================================== ";
   }
   return 0;
}

OUTPUT:
g++ p1abc123.cc && ./a.out
==============================================================
Input: RECIT = Y
Output: RECIT Y =
==============================================================
Input: PROF = CLARK
Output: PROF CLARK =
==============================================================
Input: PROF NEVER CLARK
Output: PROF CLARK NEVER
==============================================================
Input: PROF ONLY CLARK
Output: PROF CLARK ONLY
==============================================================
Input: PROF NEVER CLARK AND DEPT = CS
Output: PROF CLARK NEVER DEPT CS = AND
==============================================================
Input: RECIT = Y AND ( PROF = CLARK OR PROF = GIBSON )
Output: RECIT Y = PROF CLARK = PROF GIBSON = OR AND
==============================================================

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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