Data Structures and Algorithms Homework #5 Prefix to Postfix Expression Conversi

Question

Data Structures and Algorithms Homework #5 Prefix to Postfix Expression Conversion Your assignment is to write a program that converts a prefix expression to a postfix expression. input The input file "Prefix in" contains a series of error-free, simple arithmetic expressions in prefix notation. There is one expression per line. The expressions are made up of two types of symbols: (1) single-letter operands and (2) the operators and/. There may be zero, one, or more blanks between symbols. output All output should be written to the output file, "Postfix.out". Each prefix expression from the input should be echoprinted, with an appropriate label. After your program converts the input expression to its postfix equivalent, the postfix expression should be printed to the output file, with an appropriate label. Sample: A B C D Prefix: Postfix A B C D Prefix A B C D Postfix: Prefix A B C D E Postfix: A B C D Prefix A B C D Postfix: Although your program does not process or print infix, here are the four infix expressions that correspond to the above forms: A B+C/D A (B+ C/D) A (B+C/D)- E (A, B) (C D)

Explanation / Answer

Listing of source code:

Source Code:

#include <iostream>
#include <string>
#include <fstream>

using namespace std;

bool isOperator(char symbol) //definition of isOperator
{
if( (symbol == '*') || (symbol == '+') || (symbol == '/') || (symbol == '-' ) )
return true;
else
return false;
}

class Stack {

public:
int MaxStack;
int EmptyStack;
char* items;
int top;

Stack(int);
~Stack();
int TOP();
void push(char);
char pop();
int empty();
int full();

};
Stack::Stack(int size) {
MaxStack = size;
EmptyStack = -1;
top = EmptyStack;
items = new char[MaxStack];
}

Stack::~Stack() {delete[] items;}
int Stack::TOP(){
return items[top];
}
void Stack::push(char c) {
items[++top] = c;
}

char Stack::pop() {
return items[top--];
}

int Stack::full() {
return top + 1 == MaxStack;
}

int Stack::empty() {
return top == EmptyStack;
}

int main()
{
cout <<"WELCOME TO PROGRAM"<<endl;

// basic components
string line;
string outputLine;

//stacks

Stack stack(20);
char c;

ifstream myfile ("Prefix.in");
if (myfile.is_open())
{
while ( myfile.good() )
{
getline(myfile,line);
cout << line << endl;

}
}

else cout << "Unable to open file";

//flags, operator method
while (line.length()!=0) //while not end of blank line
{
Stack flags(20);
Stack operators(20);

for(int i=0; i < line.size(); i ++) //reiterate through ‘line’
{
char symbol = line [i];
if( isOperator(symbol)) //if the symbol is an operator
{
operators.push(symbol); //push operator on stack
flags.push(0); //push associated flag on stack
}
if((symbol != ' ') && !isOperator(symbol)) //then it’s a operand
{
outputLine += symbol; //append
while(flags.TOP()) //while top flag is ON on stack
{
outputLine += operators.TOP() ; //append the associated op
operators.pop(); //remove operator from stack
flags.pop(); //remove flag from stack
}
flags.pop(); //set next flag ON
flags.push(1);
}
}//end of for

if(!operators.empty() || (!flags.empty()) )
{
cout << "SOMETHING WENT WRONG. Prob incorrect input" << endl;
}
else
{
cout << line << endl;
cout << outputLine << endl;
}
} //end of while eof

ofstream outfile ("Postfix.out");
if (outfile.is_open())
{
outfile << outputLine << endl;
outfile << line << endl;

myfile.close();
}
else cout << "Unable to open file";
myfile.close();
//outFile.close();
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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