Convert expressions that are in infix notation to postfix notation. The expressi
ID: 3871348 • Letter: C
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 ANDExplanation / 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
==============================================================