In this lab you will reuse the code from the previous lab file. The previous lab
ID: 3819786 • Letter: I
Question
In this lab you will reuse the code from the previous lab file. The previous lab’s postfix expression string will be used to build a Binary Expression Tree (BET). The BET will be displayed by traversing the expression tree using the three transversal types (pre-order, in-order, post-order). The Algorithm Post order traversal of a tree displays the children of the node first, and then displays the data inside the node. In-Order traversal goes to the left node first and then displays the node data and then goes to the right. Preorder traversal displays the node data first and the children nodes from left to right.
refactor this code to finish the assigment
// InfixToPostFix.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
#include<cstring>
#include<fstream>
#include<stack>
#include<string>
using namespace std;
#define max 100
//template class for finding priority
template <class A_Type> class OperatorMapClass {
public:
A_Type getPriority(A_Type ch);
};
template <class A_Type> A_Type OperatorMapClass<A_Type>::getPriority(A_Type ch) {
switch (ch) {
case '/':
case '*': return 2;
case '+':
case '-': return 1;
default: return 0;
}
}
//class that handles stack operations
template <class A_Type> class OperatorStackClass
{
public:
A_Type shuntingYard(A_Type infix[], A_Type postfix[], A_Type size);
};
template <class A_Type> A_Type OperatorStackClass<A_Type>::shuntingYard(A_Type infix[], A_Type postfix[], A_Type size) {
stack<char> s;
int weight;
int i = 0;
int k = 0;
char ch;
OperatorMapClass <int> priority;
while (i < size) {
ch = infix[i];
if (ch == '(') {
s.push(ch);
i++;
continue;
}
if (ch == ')') {
while (!s.empty() && s.top() != '(') {
postfix[k++] = s.top();
s.pop();
}
if (!s.empty()) {
s.pop();
}
i++;
continue;
}
weight = priority.getPriority(ch);
if (weight == 0) {
postfix[k++] = ch;
}
else {
// we saw an operator
if (s.empty()) {
// simply push the operator onto stack if
// stack is empty
s.push(ch);
}
else {
while (!s.empty() && s.top() != '(' &&
weight <= priority.getPriority(s.top())) {
postfix[k++] = s.top();
s.pop();
}
s.push(ch);
}
}
i++;
}
// pop of the remaining operators present in the stack
// and append it to postfix expression
while (!s.empty()) {
postfix[k++] = s.top();
s.pop();
}
postfix[k] = 0; // null terminate the postfix expression
return 0;
}
//application class that
template <class A_Type> class ShuntingYardClass {
public:
A_Type infixToPostfix();
};
template <class A_Type> A_Type ShuntingYardClass<A_Type>::infixToPostfix() {
OperatorStackClass <char> shunting;
ifstream myfile("input.txt");
if (myfile.is_open())
{
string infix;
string postfix;
char infixToChange[max];
char postfixAfterChange[max];
while (getline(myfile, infix))
{
int size = strlen(infix.c_str());
strcpy(infixToChange, infix.c_str());
strcpy(postfixAfterChange, postfix.c_str());
shunting.shuntingYard(infixToChange, postfixAfterChange, size);
cout << " Infix Expression :: " << infix;
cout << " Postfix Expression :: " << postfixAfterChange;
cout << endl;
}
myfile.close();
}
else
{
cout << "can not open file";
}
}
int main() {
ShuntingYardClass <void> infxToPostfx;
infxToPostfx.infixToPostfix();
return 0;
}
Explanation / Answer
#include "stdafx.h"
#include<iostream>
#include<cstring>
#include<fstream>
#include<stack>
#include<string>
using namespace std;
#define max 100
//template class for finding priority
template <class A_Type> class OperatorMapClass {
public:
A_Type getPriority(A_Type ch);
};
template <class A_Type> A_Type OperatorMapClass<A_Type>::getPriority(A_Type ch) {
switch (ch) {
case '/':
case '*': return 2;
case '+':
case '-': return 1;
default: return 0;
}
}
//class that handles stack operations
template <class A_Type> class OperatorStackClass
{
public:
A_Type shuntingYard(A_Type infix[], A_Type postfix[], A_Type size);
};
template <class A_Type> A_Type OperatorStackClass<A_Type>::shuntingYard(A_Type infix[], A_Type postfix[], A_Type size) {
stack<char> s;
int weight;
int i = 0;
int k = 0;
char ch;
OperatorMapClass <int> priority;
while (i < size) {
ch = infix[i];
if (ch == '(') {
s.push(ch);
i++;
continue;
}
if (ch == ')') {
while (!s.empty() && s.top() != '(') {
postfix[k++] = s.top();
s.pop();
}
if (!s.empty()) {
s.pop();
}
i++;
continue;
}
weight = priority.getPriority(ch);
if (weight == 0) {
postfix[k++] = ch;
}
else {
// we saw an operator
if (s.empty()) {
// simply push the operator onto stack if
// stack is empty
s.push(ch);
}
else {
while (!s.empty() && s.top() != '(' &&
weight <= priority.getPriority(s.top())) {
postfix[k++] = s.top();
s.pop();
}
s.push(ch);
}
}
i++;
}
// pop of the remaining operators present in the stack
// and append it to postfix expression
while (!s.empty()) {
postfix[k++] = s.top();
s.pop();
}
postfix[k] = 0; // null terminate the postfix expression
return 0;
}
//application class that
template <class A_Type> class ShuntingYardClass {
public:
A_Type infixToPostfix();
};
template <class A_Type> A_Type ShuntingYardClass<A_Type>::infixToPostfix() {
OperatorStackClass <char> shunting;
ifstream myfile("input.txt");
if (myfile.is_open())
{
string infix;
string postfix;
char infixToChange[max];
char postfixAfterChange[max];
while (getline(myfile, infix))
{
int size = strlen(infix.c_str());
strcpy(infixToChange, infix.c_str());
strcpy(postfixAfterChange, postfix.c_str());
shunting.shuntingYard(infixToChange, postfixAfterChange, size);
cout << " Infix Expression :: " << infix;
cout << " Postfix Expression :: " << postfixAfterChange;
cout << endl;
}
myfile.close();
}
else
{
cout << "can not open file";
}
}
int main() {
ShuntingYardClass <void> infxToPostfx;
infxToPostfx.infixToPostfix();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.