Using the code BELOW the instructions (stack.hpp and node.hpp) implement the fol
ID: 3815435 • Letter: U
Question
Using the code BELOW the instructions (stack.hpp and node.hpp) implement the following instructions in C++. All instructions must be implemented.
Instructions:
Implementation:
1) Construct a free function that converts infix to postfix and put it in utilities.cpp.
2) Read in a fully parenthesized infix expression and covert it to postfix.
3) When reading, preserve the spaces in the expression so you can use the string split method to tokenize.
4) Algorithm: Infix-to-Postfix. Input: expr - a string containing fully parenthesized valid infix expression with each token separated by a space
stack is an empty stack
tokens = split string
for each token in tokens doif token is a ")" then
right = pop stack
oper = pop stack
left = pop stack
push(left + right + oper)
else if token is not a "("
push(token)
end if
end for
top of stack is a postfix expression
return postfix expression
5) Create a main file named postfix.cpp that reads a set of infix expressions from a file and writes the infix and postfix expressions to another file. It will include utilities.hpp
6) Input file format: A fully parenthesized valid infix expression. There will be a blank between each token. Operands are 1 to 6 charaters in length and the operators: +, -, *, /. One expression per line, read until end of file is reached. Each expression will end in a semi-colon (;). You may assume that all input is valid.
------------------------------------------------------------------------------------------
stack.hpp
------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------
node.hpp
--------------------------------------------------------------------------------------------------
Explanation / Answer
Stack.hpp
#ifndef STACK_HPP_
#define STACK_HPP_
#include <cassert>
#include "node.hpp"
#define nullptr NULL
template<typename type>
class stack {
private:
node<type>* tos;
public:
~stack();
bool operator==(const stack<type>& st) const;
void swap(stack<type>&);
stack(const stack<type>& s);
stack<type>& operator=(stack<type> st);
stack() : tos(nullptr) {}
/** @pre non-full stack */
void push(const type & object) {
node<type>* temp = new node<type>(object);
temp->next = tos;
tos = temp;
}
/** @pre non-empty stack */
type pop() {
assert(!isEmpty());
type result = tos->data;
node<type> *temp = tos;
tos = tos->next;
delete temp;
return result;
}
/** @pre non-empty stack */
type top() const {
assert(!isEmpty());
return tos->data;
}
/** @pre non-empty stack */
type & top() {
assert(!isEmpty());
return tos->data;
}
bool isEmpty() const {
return tos == nullptr;
}
bool isFull() const {
node<type>* temp = new (std::nothrow) node<type>;
if(temp == nullptr){
return true;
}
delete temp;
return false;
}
};
template<typename type>
void stack<type>::swap(stack<type>& st){
node<type>* temp_tos = tos;
tos = st.tos;
st.tos = temp_tos;
}
template <typename type>
bool stack<type>::operator==(const stack<type>& st) const{
if(isEmpty() && st.isEmpty()){
return true;
}
if((isEmpty() && !st.isEmpty()) || (!isEmpty() && st.isEmpty())){
return false;
}
stack<type> copy(*this);
stack<type> copyTwo(st);
while(!copyTwo.isEmpty() && !copy.isEmpty()){
if(copy.pop() != copyTwo.pop()){
return false;
}
if((copyTwo.isEmpty() && !copy.isEmpty()) || (!copyTwo.isEmpty() && copy.isEmpty())){
return false;
}
}
return true;
}
template<typename type>
stack<type>::stack(const stack<type>& s){
tos = nullptr;
node<type>* temp = s.tos;
node<type>* bottom = nullptr;
while(temp != nullptr){
if(tos == nullptr){
tos = new node<type>(temp->data);
bottom = tos;
}
else{
bottom->next = new node<type> (temp->data);
bottom = bottom->next;
}
temp = temp->next;
}
}
template <typename type>
stack<type> & stack<type>::operator=(stack<type> st){
swap(st);
return *this;
}
template<typename type>
stack<type>::~stack(){
node<type>* temp;
while(tos != nullptr){
temp = tos;
tos = tos->next;
delete temp;
}
}
#endif
node.hpp
#ifndef NODE_HPP_
#define NODE_HPP_
#include <iostream>
template <typename type>
class node{
public:
node() : data(), next(0) {};
node(const type& st) : data(st), next(0) {};
type data;
node<type>* next;
};
#endif
utilities.hpp
#ifndef POSTFIXOF_H
#define POSTFIXOF_H
#include <string>
#include "stack.hpp"
using namespace std;
string postfix_of(string infix);
#endif
utilities.cpp
#include <sstream>
#include <iostream>
#include <vector>
#include <string.h>
#include "utilities.hpp"
#include "stack.hpp"
string postfix_of(string infix)
{
vector<string> strings;
stack<string> stackOfTokens; //initialize a stack
istringstream f(infix);
string s;
while (getline(f, s, ' ')) { // get tokens in variable 's'
if(s.compare(")")==0){ // if s matches ')'
string right=stackOfTokens.pop(); //pop three time
string oper=stackOfTokens.pop();
string left=stackOfTokens.pop();
stackOfTokens.push(right+" "+left+" "+oper); //push rearranging
}else if(s.compare("(")!=0){
stackOfTokens.push(s);
}
strings.push_back(s);
}
return stackOfTokens.pop();
}
main.cpp
#include <iostream>
#include <fstream>
#include <sstream>
#include "utilities.hpp"
using namespace std;
int main()
{
string expression;
ifstream infile( "input.txt" );
ofstream outfile;
outfile.open("output.txt");
if (infile)
{
while (getline( infile, expression))
{
outfile<<"infix:"<<expression<<" "<<"postfix:"<<postfix_of(expression)<<endl;
}
infile.close();
outfile.close();
}
else cout << "file open error";
}
Note: 1) make a file named input.txt with infix expressions in each line giving proper spacing .
2) put all the files in the same directory
3) use of only the above provided code for stack.hpp
4) compilation
g++ -c main.cpp
g++ -c utilities.cpp
g++ main.o utilities.o
./a.out
5) input.txt example
( ( 8 + 4) + 5)
( 7 + 8 + 9 )
6) output will be in output.txt generated in same directory
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.