I have this project for my c++ data structures. I do not want the project done f
ID: 665372 • Letter: I
Question
I have this project for my c++ data structures. I do not want the project done for me, rather I would just like some help on how I should get started and what my header files should look like. Here is the project:
Overview
In this project, you will implement a calculator that evaluates mathematical expressions.
Discussion
Mathematical expressions are normally written in infix notation. Operators are inserted between operands when using infix notation: 5 + 9. Infix expressions may also contain matching parentheses, mathematical operators (+, -, *, /), digits (0 to 9), a decimal point (‘.’), and blank characters (‘ ‘): ((2.5 * 1.6) – (3/6)).
Postfix notation writes the operator after the operands: 5 9 +.
Postfix notation uses a stack for evaluating expressions. An expression is initially tokenized into operators and operands, which are then pushed onto the stack. Calculations are performed when an operator is popped off the stack. Intermediate results are pushed back onto the stack until the evaluation is completed.
The logic for evaluating postfix expressions is easier to implement than that for infix expressions. Note that postfix notation does not use parentheses to override operator precedence. The algorithm for evaluating a postfix expression is as follows:
while the end of the postfix expression has not been reached
Read the next token from the postfix expression
if the token is a number
Push the token onto the stack
else (the token must be an operator)
Pop an element from the stack, call it operand2
if operand2 is 0 and the token is a division or modulus operator
output error: Division by zero
stop
(end if)
Pop another element from the stack: call it operand1
Perform the operation: operand1 token operand2
Push the result of the operation onto the stack
(end else)
(end while)
Pop the stack (the popped element is the answer)
2
To evaluate an infix expression, it must first be converted to a postfix expression. Insert one blank as a separator after each token in the postfix expression except for the last token. The algorithm for turning an infix expression into a postfix expression is as follows:
while the end of the infix expression has not been reached
Read the next token from the infix expression
if the token is a digit (0 to 9) or period (‘.’)
Add the token to the end of the postfix expression
else if the token is a ‘(‘
Push the token onto the stack
else if the token is an operator (+, -, *, /)
while stack is not empty, and the top of the stack is either an operator with precedence
>= token or not a ‘(‘
Pop the element c from the stack
Place element c at the end of the postfix expression preceded by blank (‘ ‘)
(end while)
Add a blank to the end of the postfix expression (‘ ‘)
Push the token onto the stack
else if the token is a ‘)’
while stack is not empty, and the top of the stack is not a ‘(‘
Pop the element c from the stack
Place element c at the end of the postfix expression preceded by blank (‘ ‘)
(end while)
if top of the stack is a ‘(‘
Pop the element c from the stack, but don’t save it.
(end else)
(end while)
while the stack is not empty
Pop the element c from the stack
Place c at the end of the postfix expression preceded by blank (‘ ‘)
(end while)
Project Requirements
Important Note: You may not use any of the Standard Class Library (STL) classes for this project. You may use any code discussed in class or in the book.
1. Implement a stack class using templates. You may use the stack class discussed in class, the one in the book, or create your own.
2. Define a static Calculator class that uses the stack to calculate the value of a mathematical expression given in infix notation. The public evaluate(…) method will evaluate the infix expression. You may use whatever additional private methods you need to implement the solution.
3. Create the following custom exception classes inheriting from std::logic_error: o UnbalancedParenthesesException o InvalidCharactersException o DivideByZeroException.
4. Validate the incoming expression for unbalanced parentheses using a stack; throw an UnbalancedParenthesesException if the expression contains unbalanced parentheses.
5. Validate the incoming expression for invalid characters; throw an InvalidCharactersException if the expression contains invalid characters.
6. If a divide-by-zero exception occurs when evaluating the postfix expression, throw a DivideByZeroException.
Please use the following class definition for the Calculator class:
namespace cs20
{
static class Calculator
{
public:
static double evaluate(const char* infix);
static char* infixToPostfix(const char* infix);
static double evaluatePostfix(const char* postfix);
static bool checkDelimiters(const char* infix);
static bool checkValidChars(const char* infix);
privat:
static bool isOperator(char ch);
static bool isValidChar(char ch);
static int weight(char ch);
}; }
The following is a short description of each of the methods in the Calculator class:
evaluate(…): calculate the value of a mathematical expression given in infix notation.
infixToPostfix(…): uses the stack to convert an input string (including parentheses) from infix notation to postfix notation. If the input string does not contain balanced parentheses, or if it contains invalid characters, throw a custom exception and stop.
evaluatePostfix(…): uses the stack to evaluate an input string in postfix notation. If a divide-by-zero error occurs, throw a custom exception and stop.
checkDelimiters(…): checks an input string in infix notation for unbalanced parentheses using a stack.
checkValidChars(…): checks an input string in infix notation for illegal characters (anything other than operators, blanks, parentheses, or digits); no stack is needed here.
isOperator(…): helper method that returns true/false depending on whether a character is an operator (+, -, *, /).
isValidChar(…): helper method that returns true/false depending on whether character is a valid character (+, -, *, /, 0, 1,2 3, 4, 5, 6, 7, 8, 9, ‘(‘, ‘)’, ‘ ‘).
weight(…): helper method that returns a weight for the incoming character. This method is used when evaluating the precedence of operators on the stack. Assign a value of “2” to the operators “*” and “/”; assign a value of “1” to the operators “+” and “-“; assign a value of “0” to everything else.
Sample Driver and Output
#include <iostream> #include "Calculator.h"
using namespace std; using namespace cs20;
int main() { char* expr[] = { "12+(14*10+9)", "7 * 122 - (100 + 1/2) * 14", "50 * 2 * 3 * (6/0)", "((17.2+2.9)*15-12.7)/(7-4.0)", "5 + ((1 + 2) * 4) - 3", "12 * (4 + 6)", "1 + 2)/10", "2.21/6*1.1+(3.145 -1.1)", "1 * 2.2 + x" };
cout << endl; cout << " " << "Stack Calculator Assignment" << endl << endl;
int size = sizeof(expr)/sizeof(expr[0]); for (int i=0; i < size; i++) { try { cout << " " << "Infix Expression: " << expr[i] << endl; cout << " " << "Postfix Expression: " << Calculator::infixToPostfix(expr[i]) << endl; cout << " " << "Result = " << Calculator::evaluate(expr[i]) ; } catch (exception e) { cout << " " << expr[i]<< ": " << e.what(); } cout << endl << endl; } return 0; }
Explanation / Answer
// File: Calculator.h
#ifndef CALCULATOR_H
#define CALCULATOR_H
namespace cs20
{
static class Calculator
{
public:
static double evaluate(const char* infix);
static char* infixToPostfix(const char* infix);
static double evaluatePostfix(const char* postfix);
static bool checkDelimiters(const char* infix);
static bool checkValidChars(const char* infix);
private:
static bool isOperator(char ch);
static bool isValidChar(char ch);
static int weight(char ch);
};
}
#endif
-------------------------------------------------------------------
// File: Calculator.cpp
#include "Calculator.h"
#include <string>
#include <stack>
namespace cs20
{
double Calculator::evaluate(const char* infix)
{
return 0;
}
char* Calculator::infixToPostfix(const char* infix)
{
stack<char> stk;
string postfix = "";
char token;
char c;
for(int i = 0; i < strlen(infix); i++)
{
token = infix[i];
if(isdigit(token) || token == '.')
{
postfix.append(1, token);
}
else if(token == '(')
{
stk.push(token);
}
else if(isOperator(token))
{
while(!stk.empty() && (weight(stk.top()) >= weight(token)/* || stk.top() != '('*/))
{
c = stk.top();
stk.pop();
postfix.append(" ");
postfix.append(1, c);
}
postfix.append(" ");
stk.push(token);
}
else if(token == ')')
{
while(!stk.empty() && stk.top() != '(')
{
c = stk.top();
stk.pop();
postfix.append(" ");
postfix.append(1, c);
}
if(!stk.empty() && stk.top() == '(')
stk.pop();
}
else if(token == '(')
{
c = stk.top();
stk.pop();
}
}
while(!stk.empty())
{
c = stk.top();
stk.pop();
postfix.append(" ");
postfix.append(1, c);
}
char *postfixPtr = new char[postfix.length() + 1];
strcpy(postfixPtr, postfix.c_str());
return postfixPtr;
}
double Calculator::evaluatePostfix(const char* postfix)
{
return 0;
}
bool Calculator::checkDelimiters(const char* infix)
{
return false;
}
bool Calculator::checkValidChars(const char* infix)
{
for(int i = 0; i < strlen(infix); i++)
{
if(!isValidChar(infix[i]))
return false;
}
return true;
}
bool Calculator::isOperator(char ch)
{
if(ch == '+' || ch == '-' || ch == '*' || ch == '/')
return true;
else
return false;
}
bool Calculator::isValidChar(char ch)
{
if(ch == '+' || ch == '-' || ch == '*' || ch == '/'
|| ch == '0' || ch == '1' || ch == '2' || ch == '3'
|| ch == '4' || ch == '5' || ch == '6' || ch == '7'
|| ch == '8' || ch == '9' || ch == '(' || ch == ')'
|| ch == '.' || ch == ' ')
return true;
else
return false;
}
int Calculator::weight(char ch)
{
if(ch == '*' || ch == '/')
return 2;
else if(ch == '+' || ch == '-')
return 1;
else
return 0;
}
}
---------------------------------------------------------------------
// File: Driver.cpp
#include <iostream>
#include "Calculator.h"
using namespace std;
using namespace cs20;
int main()
{
char* expr[] =
{ "12+(14*10+9)",
"7 * 122 - (100 + 1/2) * 14",
"50 * 2 * 3 * (6/0)",
"((17.2+2.9)*15-12.7)/(7-4.0)",
"5 + ((1 + 2) * 4) - 3",
"12 * (4 + 6)",
"1 + 2)/10",
"2.21/6*1.1+(3.145 -1.1)",
"1 * 2.2 + x" };
cout << endl;
cout << " " << "Stack Calculator Assignment" << endl << endl;
int size = sizeof(expr)/sizeof(expr[0]);
for (int i=0; i < size; i++)
{
try
{
cout << " " << "Infix Expression: " << expr[i] << endl;
cout << " " << "Postfix Expression: " << Calculator::infixToPostfix(expr[i]) << endl;
cout << " " << "Result = " << Calculator::evaluate(expr[i]) ;
}
catch (exception e)
{
cout << " " << expr[i]<< ": " << e.what();
}
cout << endl << endl;
}
system("pause");
return 0;
}