CS255 – Project 03– Infix to Postfix and Postfix Evaluation Page 6 of 7 Input /Output Requirements: • Your program must read an infix expression represented as a string. o Operands: Single decimal digits o Operators: +, -, *, / , ^ • Your program must output the corresponding expression and then the result of the postfix evaluation. Use sample runs shown below • Use integer division. Check for division by zero. • Your program should keep reading infix expressions and processing each one until an empty string is read. • Use the given code as an outline for implementing this project and complete the code to accomplish the above requirements. Sample Run: Enter an infix expression: 3 ^ 2 ^ (1+2) The postfix form is XXXXXXXXXX + ^ ^ Value of the expression = 6561 Enter an infix expression: 3 * (4 - 2 ^ XXXXXXXXXXThe postfix form is XXXXXXXXXX ^ - * 6 + Value of the expression = -78 Enter an infix expression: (7 + 8*7 infix2Postfix: Missing ')' Enter an infix expression: CS255 – Project 03– Infix to Postfix and Postfix Evaluation Page 7 of 7 Design and Implementation Requirements: InfixToPostfixDriver.cpp: Main driver class. Use the given code. Study and understand it. MyStack.h: Template stack class. You must implement the template Stack class using singly-linked list without a header node or a tail pointer. It has a single member variable that is a reference to a StackNode, nodes put on the stack. (StackNode is defined as a struct within the MyStack.h file.) It will be used by both the InfixToPostfix and the PostfixEval class. Member functions top(), topAndPop(), and pop() should throw an UnderflowException for accessing an empty stack. See the “CS255Exceptions.h” below. • Complete isEmpty() • Complete makeEmpty() • Complete pop() • Complete push() InfixToPostfix.h: Converts an infix string to a postfix expression. Use the starter code and complete the member function so that the given infix expression is converted to the correct postfix expression. • Complete the postfix() member function PostfixEval.h: Use the starter code and complete the member functions so the postfix expression is evaluated and produces the correct result. • Complete the compute() member function: watch for integer division by zero and 0^0 error. • Complete the evaluate() member function ExpressionSymbol.h: Used to set the stack and input precedence of operators. CS255Exceptions.h: This is used for exceptions and error processing and is limited for this program. Your program must utilize the exception classes given in this file. Your MyStack class should check for empty stack. The InfixToPostfix class and member function, postfix(), should throw an ExpressionException when an infix expression has a missing right parenthesis. See the above sample runs. Also watch for integer division by zero and 0^0 indeterminate form error. Due Date: See Programming Projects on Course Blackboard Site.Plus:// TO BE COMPLETED:// compute()// evaluate()
// SOLUTION: PostfixEval.h#ifndef POSTFIX_EVAL#define POSTFIX_EVAL
#include #include #include #include "MyStack.h"#include "CS255Exceptions.h" // for expressionError exception
using namespace std;
class PostfixEval {public: // default constructor. postfix expression is NULL string PostfixEval();
// return the postfix expression string getPostfixExp() const;
// change the postfix expression void setPostfixExp(const string& postfixExp);
// evaluate the postfix expression and return its value. // the function throws expressionError // if an error (e.g. divison by zero) occurs during evaluation int evaluate();
private: // the postfix expression to evaluate string postfixExpression;
// stack of operands myStack operandStack;
// pop left and right operands from stack. // Precondition: the stack must have at least two entries. // if the stack is empty prior to a pop() operation, the // function throws the exception expressionError void getOperands(int& left, int& right);
// compute "left op right". if right is 0 and op // is '/' , the function throws expressionError int compute(int left, int right, char op) const;
// is ch one of '+','-','*','/' ,'^' bool isOperator(char ch) const;};
void PostfixEval::getOperands(int& left, int& right) { // can we pop the right operand? if (operandStack.isEmpty()) throw ExpressionError("postfixEval: Too many operators");
// pop right operand right = operandStack.top(); operandStack.pop();
// can we pop the left operand? if (operandStack.isEmpty()) throw ExpressionError("PostfixEval: Too many operators");
// pop left operand left = operandStack.top(); operandStack.pop();}
int PostfixEval::compute(int left, int right, char op) const { /**** TO BE COMPLETED *****/} // end compute()
bool PostfixEval::isOperator(char ch) const { return ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^';}
// default constructorPostfixEval::PostfixEval() {}
string PostfixEval::getPostfixExp() const { return postfixExpression;}
void PostfixEval::setPostfixExp(const string& postfixExp) { postfixExpression = postfixExp;}
int PostfixEval::evaluate() { /**** TO BE COMPLETED *****/} // end evaluate();#endif // POSTFIX_EVAL