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 »
Code C++


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.
homework5-vqwvtjqc.pdf calctest-xjobtjym.cpp calcimpl-oxpumrir.cpp list-2-p3ss43cn.h stack-gkjmrhg3.h
Answered Same DayApr 22, 2021

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

Ria answered on Apr 24 2021
152 Votes
solution/calculatorimpl.cpp
#include
#include
#include
#include
#include
#include "list.h"
#include "stack.h"
using namespace std;
double CharToDouble(char ch);
int operation(char c) // returns each operator's priority
{
if (c == '*' || c == '/')
return 2;
else if (c == '+' || c == '-')
return 1;
else
return -1;
}
string InfixToPostfix(string infix)
{
///////////////////////////////////////////
// Implement function body

throw "Rpn(const char* expr, int n, std::ostringstream& os) is not implemented.";
Stack s; // create object of Stack class of character type
int l = infix.length(); // get length of the infix equation
string postfix;
for (int i = 0; i < l; i++)
{
if (infix[i] >= '0' and infix[i] <= '9') // if numbers
{
postfix += infix[i];
}
else if (infix[i] == '(') // if '('
s.Push('(');
else if (infix[i] == ')') // if ')'
{
while (s.Top() != -1 && s.Top() != '(')
{
char c = s.Top(); // get top element of stack
s.Pop(); // pop the element
postfix += c; // store it into postfix
}
if (s.Top() == '(')
{
char c = s.Top();
s.Pop();
}
}
else
{
while (s.Top() != -1 && operation(infix[i]) <= operation(s.Top())) // depends on operator's priority
{
char c = s.Top();
s.Pop();
postfix += c;
}
s.Push(infix[i]);
}
}
s.Clear(); // delete all stack elements
// Implement function body
///////////////////////////////////////////
}
double EvaluatePostfix(string postfix)
{
///////////////////////////////////////////
// Implement function body
throw "Eval(const char* rpnexpr, int n) is not implemented.";
Stack s; // create object of Stack class of double type
int l = postfix.length();
for (int i = 0; i < l; ++i)
{
if (isdigit(postfix[i]))
s.Push(CharToDouble(postfix[i])); // convert character to double

else
{
double a = s.Pop();
double b = s.Pop();
switch (postfix[i])
{
case '+': s.Push(b + a); break;
case '-': s.Push(b - a); break;
case '*': s.Push(b * a); break;
case '/': s.Push(b / a); break;
}
}
}
double result = s.Pop(); // get the last element of stack i.e. result
s.Clear(); // delete all stack elements
return result;
// Implement function body
///////////////////////////////////////////
}
solution/calculatortest.cpp
#include
#include
#include
#include
#include
#include "list.h"
#include "stack.h"
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...
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?