1 CMPSC 122 section 2 Homework 5 Due: Thursday, April 23, 2020 Calculator Reserve Polish Notation (RPN) is a form of mathematical expression that is written in a postfix notation. The following...

1 answer below »
C++ program



1 CMPSC 122 section 2 Homework 5 Due: Thursday, April 23, 2020 Calculator Reserve Polish Notation (RPN) is a form of mathematical expression that is written in a postfix notation. The following expression in infix notation ? + (? + ?) ∗(?−?) ∗? + ?/?; can be rewritten as postfix notation as follows ??? + ??−?∗??/+ ∗ + without losing correctness and accuracy. Converting infix notation to postfix notation is easily done using a stack. Even though infix notation is easier to read for humans, the postfix notation has several advantages over infix notation: 1) it does not need parenthesis, 2) it is easy to evaluate its value using a stack, and 3) it leads to faster calculation. The goal of this assignment is to implement two functions using stacks: one is to convert the infix notation to the postfix notation, and the other is to evaluate the postfix notation expression. To this end, you should implement series of classes and the two functions, as follows: • List class: a doubly linked list template class; • Stack class: a stack template class that uses List class; • InfixToPostfix(): a function that converts infix notation to postfix notation; • EvaluatePostfix(): a function that evaluates the postfix notation expression. You are provided the following startup files: list.h stack.h calculatortest.cpp calculatorimpl.cpp You can find the main function in calculatortest.cpp. You can compile and run the program using the following command: $ g++ -ansi –pedantic -Wall calculatortest.cpp calculatorimpl.cpp –o calculator $ ./calculator The calculator program runs 32 test cases for List class, Stack class, InfixToPostfix() function, and EvaluatePostfix() function. You should implement missing and incomplete functions and member functions, so that all test cases are passed. If you pass all tests successfully, you will find the following messages: 2 Congratulation! You successfully passed all tests! Followings describe what you should implement. 1. (15 points) doubly linked lists You are provided the header file of the template doubly linked list class: list.h Implement missing member functions in list.h. You can add additional member function(s) at the end of the classes if you need. 2. (15 points) stacks using the doubly linked lists You are provided the header file of the stack that uses the template doubly linked list class: stack.h Implement its missing member functions in stack.h. You can add additional member function(s) at the end of the classes if you need. 3. (30 points) infix to postfix You are provided the InfixToPostfix() function that converts infix expression to postfix expression in calculatorimpl.cpp. Its prototype is the same to the following: string InfixToPostfix(string infix). The function receives one parameter infix that is an expression string in the form of infix notation, and should return its postfix notation (or RPN) expression. The string infix ends with an ending delimiter ‘;’ and has two types of character: • a single character operand that is one of the element of {‘0’, ‘1’, ‘2’, …, ‘8’, ‘9’}, • a single character operator that is one of the element of {‘(‘, ‘)’, ‘+’, ‘-‘, ‘*’, ‘/’ }. For example, if the input is “(1+3)/8;” then its output should be “13+8/”. Complete the implementation of InfixToPostfix() function in calculatorimpl.cpp. 4. (30 points) evaluate postfix You are provided the EvaluatePostfix() function that evaluates the postfix expression in calculatorimpl.cpp. Its prototype is the same to the following: double EvaluatePostfix(string postfix). 3 The function receives one parameter postfix that is an expression string in the form of the postfix notation (or RPN) expression, and should return its calculated result in double. For example, if the input is “13+8/” then it should return 0.5 in double. Complete the implementation of EvaluatePostfix() function in calculatorimpl.cpp. 5. (10 points) memory management and coding style You will receive 10 points from dynamic memory allocation and your coding style such as creating and deleting Node objects, indentation, variable names, and comments. What to submit • Electronic submission is due April 23 at midnight. Please submit a zip file containing the two header files (list.h and stack.h) and calculatorimpl.cpp. Do not submit calculatortest.cpp.
homework51-gpv4pbtk.pdf stack-nnr0svbi.h list1-4py3jynn.h calcimpl-vg5bak34.cpp calctest-lc22gbdz.cpp
Answered Same DayApr 21, 2021

Answer To: 1 CMPSC 122 section 2 Homework 5 Due: Thursday, April 23, 2020 Calculator Reserve Polish Notation...

Pushpendra answered on Apr 22 2021
123 Votes
calculatorimpl.cpp
#include
using namespace std;
template
class Stack {
stack l;
public:
void Push(T val) {
l.push(val);
}
int Pop() {
int t = l.top();
l.pop();
return t;
}
T Top() {
return l.top();
};
operator string() {
if (l.empty())
return "()";
stack k = l; string s = "(";
long long size = k.size();
vector arr;
while (k.empty() == false) {
arr.push_back(k.top());
k.pop();
}
reverse(arr.begin(), arr.end());
for (int i = 0; i < size; i++)
{
s += char('0'+arr[i]);
if (i != size - 1)
s += ",";
}
s += ")";
return s;
}
};
template
class List {
list l;
public:
void AddToHead(T val) {
l.push_front(val);
}
void AddToTail(T val) {
l.push_back(val);
}
void RemoveHead() {
l.pop_front();
}
void RemoveTail() {
l.pop_back();
};
operator string() {
if (l.empty())
return "()";
list k = l; string s = "(";
unsigned long size = k.size();
int i = 0;
while (k.empty() == false) {
s += k.front();
i++;
if (i != size)
s += ",";
k.pop_front();
}
s += ")";
return s;
}
};
using namespace std;
string InfixToPostfix (string infix);
double EvaluatePostfix(string postfix);
void TestList();
void TestStack();
void TestInfixToPostfix (string infix, string expected_postfix);
void TestEvaluatePostfix(string postfix, double expected_value);
int main()
{
try
{
TestList();
}
catch (const char* message)
{
cout << "Exception in TestTList(): " << message << endl;
return -1;
}
try
{
TestStack();
}
catch (const char* message)
{
cout << "Exception in TestTStack(): " << message << endl;
return -1;
}
cout << endl << "Test Rpn() and Eval()" << endl;
cout << " test Rpn 1:"; try { TestInfixToPostfix ("1+2;", "12+;" ); } catch (string message) { cout << "Exception: " << message << endl; return -1; } cout << " success" << endl; cout << flush;
cout << " test Eval 1:"; try { TestEvaluatePostfix( "12+;", 3); } catch (string message) { cout << "Exception: " << message << endl; return -1; } cout << " success" << endl; cout << flush;
cout << " test Rpn 2:"; try { TestInfixToPostfix ("1+2*3;", "123*+;" ); } catch (string message) { cout << "Exception: " << message << endl; return -1; } cout << " success" << endl; cout << flush;
cout << " test Eval 2:"; try { TestEvaluatePostfix( "123*+;", 7); } catch (string message) { cout << "Exception: " << message << endl; return -1; } cout << " success" << endl; cout << flush;
cout << " test Rpn 3:"; try { TestInfixToPostfix ("1+2*3/4-5;", "123*4/+5-;" ); } catch (string message) { cout << "Exception: " << message << endl; return -1; } cout << " success" << endl; cout << flush;
cout << " test Eval 3:"; try { TestEvaluatePostfix( "123*4/+5-;", -2.5); } catch (string message) { cout << "Exception: " << message << endl; return -1; } cout << " success" << endl; cout << flush;
cout << " test Rpn 4:"; try { TestInfixToPostfix ("(1+2)*3;", "12+3*;" ); } catch (string message) { cout << "Exception: " << message << endl; return -1; } cout << " success" << endl; cout << flush;
cout << " test Eval 4:"; try { TestEvaluatePostfix( "12+3*;", 9); } catch (string message) { cout << "Exception: " << message << endl; return -1; } cout << " success" << endl; cout << flush;
cout << " test Rpn 5:"; try { TestInfixToPostfix ("1+2+3*(4+(5+6)*7);", "12+3456+7*+*+;" ); } catch (string message) { cout << "Exception: " << message << endl; return -1; } cout << " success" << endl; cout << flush;
cout << " test Eval 5:"; try { TestEvaluatePostfix( "12+3456+7*+*+;", 246); } catch (string message) { cout << "Exception: " << message << endl; return -1; } cout << " success" << endl; cout << flush;
cout << " test Rpn 6:"; try { TestInfixToPostfix ("1/(2+3)+4*(5-6/7)*8/9-0;", "123+/4567/-*8*9/+0-;" ); } catch (const char* message) { cout << "Exception: " << message << endl; return -1; } cout << " success" << endl; cout << flush;
cout << " test Eval 6:"; try { TestEvaluatePostfix( "123+/4567/-*8*9/+0-;", 14.930158730158730); } catch (const char* message) { cout << "Exception: " << message << endl; return -1; } cout << " success" << endl; cout << flush;
cout << endl << "Congratulation!" << endl;
cout << "You successfully passed all tests!" << endl; cout << flush;
}
void TestInfixToPostfix(string infix, string expected_postfix)
{
string postfix = InfixToPostfix(infix);
cout << postfix << endl;
if (postfix != expected_postfix)
{
ostringstream os;
os << "Rpn(" << infix << ") = " << postfix << " is not same to its solution " << expected_postfix;
throw os.str();
}
}
void TestEvaluatePostfix(string postfix, double expected_value)
{
double val = EvaluatePostfix(postfix);
double err = abs(val - expected_value);
double tolerance = 0.00001;
if (err > tolerance)
{
ostringstream msg;
msg << "Eval(" << postfix << ") = " << val << " is not same to its solution " << expected_value;
throw msg.str();
}
}
void TestList()
{
cout << endl << "Test List class" << endl; cout << flush;
List list;
string str;
string lstr;
cout << " test List 1:"; list.AddToHead('e'); lstr = (string)list; str = "(e)" ; if (str != lstr) throw "elements after calling list.AddToHead('e') != (\"e\") "; cout << " success" << endl; cout << flush;
cout << " test List 2:"; list.AddToHead('d'); lstr = (string)list; str = "(d,e)" ; if (str != lstr) throw "elements after calling list.AddToHead('d') != (\"d,e\") "; cout << " success" << endl; cout << flush;
cout << " test List 3:"; list.AddToTail('f'); lstr = (string)list; str = "(d,e,f)" ; if (str != lstr) throw "elements after calling list.AddToTail('f') != (\"d,e,f\") "; cout << " success" << endl; cout << flush;
cout << " test List 4:"; list.AddToTail('g'); lstr = (string)list; str = "(d,e,f,g)" ; if (str != lstr) throw "elements after calling list.AddToTail('g') != (\"d,e,f,g\") "; cout << " success" << endl; cout << flush;
cout << " test List 5:"; list.AddToHead('b'); lstr = (string)list; str = "(b,d,e,f,g)"; if (str != lstr) throw "elements after calling list.AddToHead('b') != (\"b,d,e,f,g\")"; cout << " success" << endl; cout << flush;
cout << " test List 6:"; list.RemoveHead() ; lstr = (string)list; str = "(d,e,f,g)" ; if (str != lstr) throw "elements after calling list.RemoveHead() != (\"d,e,f,g\") "; cout << " success" << endl; cout << flush;
cout << " test List 7:"; list.RemoveTail() ; lstr = (string)list; str = "(d,e,f)" ; if (str != lstr) throw "elements after calling list.RemoveTail() != (\"d,e,f\") "; cout << " success" << endl; cout << flush;
cout << " test List 8:"; list.RemoveHead() ; lstr = (string)list; str = "(e,f)" ; if (str != lstr) throw "elements after calling list.RemoveHead() != (\"e,f\") "; cout << " success" << endl; cout << flush;
cout << " test List 9:"; list.RemoveTail() ; lstr = (string)list; str = "(e)" ; if (str != lstr) throw "elements after calling list.RemoveTail() != (\"e\") "; cout << " success" << endl; cout << flush;
cout << " test List 10:"; list.RemoveHead() ; lstr = (string)list; str = "()" ; if (str != lstr) throw "elements after calling list.RemoveHead() != (\"\") "; cout << " success" << endl; cout << flush;
}
void TestStack()
{
cout << endl << "Test Stack class" << endl; cout << flush;
Stack stack;
string str;
string lstr;
int poped;
cout << " test List 1:"; lstr = (string)stack; str = "()" ; if (str != lstr) throw "not an empty stack"; cout << " success" << endl; cout << flush;
cout << " test List 2:"; stack.Push(1); lstr = (string)stack; str = "(1)" ; if (str != lstr) throw "elements after calling tstack.AddToHead('5') != (1) "; cout << " success" << endl; cout << flush;
cout << " test List 3:"; stack.Push(2); lstr = (string)stack; str = "(1,2)" ; if (str != lstr) throw "elements after calling tstack.AddToHead('3') != (1,2) "; cout << " success" << endl; cout << flush;
cout << " test List 4:"; stack.Push(3); lstr = (string)stack; str = "(1,2,3)"; if (str != lstr) throw "elements after calling tstack.AddToTail('7') != (1,2,3)"; cout << " success" << endl; cout << flush;
cout << " test List 5:"; poped = stack.Pop(); lstr = (string)stack; str = "(1,2)" ; if (str != lstr) throw "elements after calling...
SOLUTION.PDF
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here
Have files?