Data Structure and Algorithm Analysis---COP3530 Program 5– Unit 7 Total Points:

Question

Data Structure and Algorithm Analysis---COP3530 Program 5– Unit 7 Total Points: 100 NO LATE ASSIGNMENTS WILL BE ACCEPTED!! In this assignment you will write a program called "infix.cpp", that uses a stack, implemented as a singly-linked list, to convert a postfix expression to the corresponding fully-parenthesized infix expression. Consider the following examples: 1. the postfix expression a b + c d - * will be converted to the infix ((a + b) * (c - d)) 2. the the postfix expression a b + will be converted to the infix (a + b) 3. the postfix expression a b / c d / / will be converted to infix ((a / b) / (c / d)) 4. for the postfix expression a b / c * + the program should print the error message "too many operators and not enough operands". 5. for the postfix expression a b c d / + e * f the program should print the error message "too many operands and not enough operators". 6. for postfix expression a will be converted to the infix (a) 7. for an empty (string) expression an empty (string) expression will be returned 8. for postfix + the program should print the error message “too many operators not enough operands” Notes: 1. Include one space between operands ( eg. a b c d ) and operator (eg. + - * /) in your input to the program. 2. The only operators to consider are +, -, * and /. Your program should ask the user for a postfix expression as input, and it should output the corresponding fully-parenthesized infix expression. The program should also ask the user if he/she would like to do another conversion. If so, the user should be able to enter another posfix expression; otherwise the program should terminate. Also, the stack must be implemented using a singly-linked list. Your driver, infix.cpp, should include the definition and declaration files for the class STACK, stack.cpp and stack.h, respectively. Your program should do error-checking. For example, if the infix expression is invalid, your program should print an error message stating so. You should submit infix.cpp, stack.cpp, and stack.h. in a zip file called "program5_stack" to Blackboard before the due date and time

Explanation / Answer

#include <string>

using namespace std;

struct Node
{
string value;
struct Node *nextNode;
};

class stack
{
struct Node *top;

public:

stack()
{
top = 0;
}

void push(string value);
string pop();
};

// stack.cpp

#include "stack.h"

void stack::push(string value)
{
struct Node *pn;
pn = new Node();
pn->value = value;
pn->nextNode = (top != 0) ? top : 0;
top = pn;
}

string stack::pop()
{
struct Node *pn;
if (top == 0) return ""; // slight alteration on this line
pn = top;
string result = pn->value;
top = top->nextNode;
delete pn;
return result;
}

// infix.cpp

#include "stack.cpp"
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() // a lot of alterations in here
{
int error;
stack s;
string postfix, infix, operand1, operand2, expr, choice;
do
{
cout << "Enter postfix expression" << endl;
getline(cin, postfix);
error = 0;
for(int i = 0; i < postfix.length(); i++)
{
string c = postfix.substr(i, 1);
if (c == "+" || c == "-" || c == "*" || c == "/")
{
operand2 = s.pop();
if (operand2 == "")
{
cout << "Too many operators and not enough operands" << endl;
error = 1;
break;
}
operand1 = s.pop();
if (operand1 == "")
{
cout << "Too many operators and not enough operands" << endl;
error = 1;
break;
}
expr = "(" + operand1 + " " + c + " " + operand2 + ")";
s.push(expr);
}
else if (c == " ")
{
continue;
}
else
{
s.push(c);
}
}

if (!error)
{
infix = s.pop();
if (s.pop() == "")
{
cout << "The infix expression is" << endl << infix << endl;
}
else
{
cout << "Too many operands and not enough operators" << endl;
// make sure stack is clear
while(s.pop() != "");
}
}
cout << "Convert another y/n : ";
cin >> choice;
getchar(); // swallow new line character
cout<< endl;
}
while(choice == "y" || choice == "Y");

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.