Question

Write a program that takes an infix expression as input and produces a postfix expression. The infix and postfix expressions are in the form of vectors of strings. We will test with a main method that takes a file name as input from the command line. We will test your implementation using printPostFix() method.   There are sample input and output files in this folder. You may edit the header file.

Example 1

infix expression = apple + banana * cat

vector inFixTokens = {"apple", "+", "banana", "*", "cat"}

postfix expression = apple banana cat * +

vector postFixTokens = {"apple", "banana", "cat", "*", "+"}

Example 2

infix expression = (apple + banana) * cat ^ dog + egg

vector inFixTokens = {"(", "apple", "+", "banana", ")" , "*", "cat", "^", "dog", "+", "egg"}

postfix expression = apple banana + cat dog ^ * egg +

vector postFixTokens = {"apple", "banana", "+", "cat", "dog", "^", "*", "egg", "+"}

Use the algorithm given in the lecture slides on stacks.

Use the following header file to create a PostFixTokens class.

PostFixTokens.h

We will test your implementation by creating instances of PostFixTokens and calling createPostFix and printPostFix. *Do not change the method signatures because we will use them to test your implementation.*

Operators: ^, *, /, +, -

Precedence: ^ > * / > + -

You must account for parentheses ), (

Only binary operators. No unary operators. Minus sign (-) is not used for negation, only as a binary operator.

If the tokens of inFixTokens are an invalid expression, then any call to getPostFixTokens, printPostFix, or createPostFix should throw a std::invalid_argument exception.

Header Given:

#ifndef PostFixTokens_h
#define PostFixTokens_h
#include 
#include 
#include 

using namespace std;

class PostFixTokens {
public:
PostFixTokens();
PostFixTokens(vector inFix);
~PostFixTokens();

    vector getPostFixTokens();
    vector getInFixTokens();
    void setInFixTokens(vector inFix);
    void printPostFix();
    void printInFix();
    void createPostFix();


private:
vector inFixTokens;
vector postFixTokens;
    
};


#endif /* PostFixTokens_h */

Tester File given:

#include
#include
#include
#include
#include "PostFixTokens.h"

class ostream_suppressor {
std::ostream &out;
std::ostringstream buffer;
std::streambuf *old_buffer;
public:
ostream_suppressor(std::ostream &out) : out(out) {
old_buffer = out.rdbuf(buffer.rdbuf());
}

~ostream_suppressor() {
out.rdbuf(old_buffer);
}
};

static const std::list token_types = {
std::regex("^(-?\\d+)"), // numbers
std::regex("^[\\(\\)\\+\\-\\*\\/%\\^]"), // operators
std::regex("^[[:alpha:]]([[:alnum:]_-]*)") // variables
};

std::vector tokenize(const std::string infixExp) {
auto tokens = std::vector{};
auto matches = std::smatch{};

auto it = begin(infixExp), endIt = end(infixExp);
while(it != endIt) {
for(const auto &token_type: token_types) {
if(std::regex_search(it, endIt, matches, token_type)) {
tokens.push_back(matches[0]);
// move the iterator forward to the end of the found token
it += matches[0].length()-1;
break;
}
}
++it;
}

return tokens;
}

void printTokens(std::vector &tokens) {
if(tokens.size() == 0) return;

std::cout << tokens[0];
std::for_each(begin(tokens)+1, end(tokens), [](const auto &token) {
std::cout << " " << token;
});
std::cout << std::endl;
}

int main() {
std::string infixExp;

while(std::getline(std::cin, infixExp)) {
try {
auto inFixTokens = tokenize(infixExp);

std::vector postFixTokens;
{
ostream_suppressor supressor(std::cout);
PostFixTokens tokens(inFixTokens);
tokens.createPostFix();
postFixTokens = tokens.getPostFixTokens();
}

printTokens(postFixTokens);
} catch (std::invalid_argument &e) {
std::cout << "Invalid infix expression\n";
} catch (std::exception &e) {
std::cout << "Unexpected exception thrown with message " << e.what() << "\n";
}
}
}

Answer 1

The c++ code for the PostFixTokens.h Headerfile is shown below:

#ifndef PostFixTokens_h
#define PostFixTokens_h
#include<bits/stdc++.h>
using namespace std;
class PostFixTokens {
public:
PostFixTokens();
PostFixTokens(vector<string> inFix);
~PostFixTokens();

vector<string> getPostFixTokens();
vector<string> getInFixTokens();
void setInFixTokens(vector<string> inFix);
void printPostFix();
void printInFix();
void createPostFix();

private:
vector<string> inFixTokens;
vector<string> postFixTokens;
  
};
bool isOperator(string s){
   if(s=="+" || s=="*" || s=="^" || s=="/" || s=="-")
       return true;
   else
       return false;
}
int precition(string s){
   if(s=="^"){
       return 3;
   }
   else if(s=="*" || s=="/"){
       return 2;
   }
   else if(s=="+"|| s=="-"){
       return 1;
   }
}
void PostFixTokens::createPostFix(){
   stack<string> Stack;
   Stack.push("$");
   for(string s:inFixTokens){
       if(isOperator(s)==false){
           postFixTokens.push_back(s);
       }
       else if(s=="("){
           Stack.push("(");
       }
       else if(s==")"){
           while(Stack.top()!="$" && Stack.top()!="("){
               postFixTokens.push_back(Stack.top());
               Stack.pop();
           }
           if(Stack.top()=="("){
               Stack.pop();
           }
       }
       else{
           while(Stack.top()!="$" && precition(s)<=precition(Stack.top())){
               postFixTokens.push_back(Stack.top());
               Stack.pop();
           }
           Stack.push(s);
       }

   }
   while(Stack.top()!="$"){
       postFixTokens.push_back(Stack.top());
       Stack.pop();
   }
}
void PostFixTokens::printPostFix(){
   for(string s:postFixTokens){
       cout<<s<<" ";
   }
   cout<<endl;
}
void PostFixTokens::printInFix(){
   for(string s:inFixTokens){
       cout<<s<<" ";
   }
   cout<<endl;
}
void PostFixTokens::setInFixTokens(vector<string> inFix){
   for(string s:inFix){
       inFixTokens.push_back(s);
   }
}
vector<string> PostFixTokens::getPostFixTokens(){
   return postFixTokens;
}
vector<string> PostFixTokens::getInFixTokens(){
   return inFixTokens;
}

#endif