Modify the following code below to use Stack to program a simple calculator, that can handle +, -, *, /, and ( ). We will assume that all numbers are integers (therefore, we perform integer division, which produces an integer; in other words, 3 / 2 = 1).

Also, this is a simple calculator and we will impose the following constraints on the expressions that can be calculated (that can be entered by the user).

The entire expression will be contained within (). (In other words, 3 + 2 is not a valid expression. We will have to write as ( 3 + 2 )

We will use single spaces to separate the tokens the calculator that I wrote will not work correctly, if there are multiple spaces and will not work if there are no spaces between tokens. For instance, (3 + 2 ) is not valid as there is no space between ( and 3. You need to write as ( 3 + 2 )

To program such a calculator, there are two steps

Convert the expression string into a special format (called post fix representation). This representation might look a bit weird to you. For this, we use a stack. I have written the code that will transform the expression string into a postfix representation. Again, remember, this will work only If the string is in the format specified above.

Evaluate the value of the postfix expression. Again, you will use a stack, and this is what you will do for this project.

Note that you can use Stack that uses dynamic array or stack that uses linked list. Nothing needs to be modified in the header files. You need to implement the eval method that takes as input the postfix expression and returns the integer result obtained by evaluating the expression.

As an example, consider the expression entered by the user as: ( 5 + 3 * 2 )

The postfix expression will be 5 3 2 * +

To evaluate the postfix expression, we do the following:

For each token in the postfix representation

If it is a number, (not an operator), push the number on the stack

If it is an operator, pop 2 numbers from the stack, do the appropriate operation and push the result on to the stack.

When we have looked at the entire expression, there will be one number on the stack, which is the result.

For example, consider the postfix expression: 5 3 2 * +

When we see: 5, we push 5 onto the stack; then we push 3 onto the stack; then we push 2 onto the stack.

Now we see *, the stack (from top to bottom) is: (2, 3, 5)

Now we pop two elements, store them as num2 and num1, num2 = 2; num1 = 3; we then perform num1 op num2 (where op = *), in other words, we do 3 * 2 and compute the result as 6. We push 6 on to the stack. So now our stack is (6, 5) (Note that to do and /, we need to have num2 is the top of the stack, and num1 is the next element on the stack and we compute: num1 op num2).

Now we see op = +, the stack (from top to bottom) is: (6, 5)

Now we pop 2 elements and set them appropriately, i.e., num2 = 6, num1 = 5. We compute num1 + num2, which is 11. We push 11 on to the stack. So now our stack is (11).

Now we have seen the entire expression and come to (b). We pop the stack, and get 11. This is the result, which will be returned by the eval function.

Code is below:

#include #include #include #include #include "StackArrayHeader.h"

using namespace std;

bool lowerPrec(string s1, string s2) { if (((s1 == "+") || (s1 == "-")) && ((s2 == "*") || (s2 == "/"))) return true; return false; }

string convertToPostFix(string s) { stringstream ss; ss.str(s); ss.seekg(0); string item; string postFixExpr = ""; Stack stack1; while (getline(ss, item, ' ')) { if (item == "(") stack1.push(item); else if (item == "+" || item == "-") { string next; while (true) { stack1.peek(next); if (!(next == "+" || next == "-" || next == "*" || next == "/")) break; if (lowerPrec(next, item)) break; stack1.pop(next); postFixExpr = postFixExpr + " " + next; } stack1.push (item); } else if (item == "*" || item == "/") { string next; while (true) { stack1.peek(next); if (!(next == "+" || next == "-" || next == "*" || next == "/")) break; if (lowerPrec(next, item)) break; stack1.pop(next); postFixExpr = postFixExpr + " " + next; } stack1.push (item); } else if (item == ")") { string next; while (true) { stack1.pop(next); if (next == "(") break; postFixExpr = postFixExpr + " " + next; } if (stack1.isEmpty()) break; } else { // it is a number postFixExpr = postFixExpr + " " + item; } } return postFixExpr; }

int eval(string expr) { return 0; }

int main() { string s; getline(cin, s); string postFixExpr = convertToPostFix(s); cout << "Final postFixExpr = " << postFixExpr << endl; int res = eval(postFixExpr); cout << "result = " << res << endl; return 0; }

#ifndef STACKARRAYHEADER_H_INCLUDED #define STACKARRAYHEADER_H_INCLUDED

#include "Array.h"

template class Stack { public: Stack(); void push (DT el); bool pop (DT & el); bool peek (DT & el); bool isEmpty(); void makeEmpty(); void display(); private: Array

elements; int top; };

template Stack

::Stack (): elements(2), top (-1) { }

template void Stack

::push (DT el) { ++top; if (top == elements.length()) elements.changeSize(elements.length() * 2); elements[top] = el; }

template bool Stack

::pop (DT & el) { if (top == -1) return false; el = elements[top]; --top; return true; }

template bool Stack

::peek (DT & el) { if (top == -1) return false; el = elements[top]; return true; }

template bool Stack

::isEmpty () { if (top == -1) return true; return false; }

template void Stack

::makeEmpty () { top = -1; }

template void Stack

::display () { cout << "Stack contents" << endl; cout << "--------------" << endl; for (int i = top; i >= 0; i--) cout << elements[i] << endl; cout << endl; }

#endif // STACKARRAYHEADER_H_INCLUDED

#ifndef ARRAY_H_INCLUDED #define ARRAY_H_INCLUDED

#include #include

using namespace std;

/* error codes 0 -- no error 1 -- non-positive size for constructor 2 -- invalid index was used 4 -- non-postitive newSize for changeSize */

template class Array { public: Array(int size); ~Array(); Array(const Array & a); Array & operator = (const Array & a);

T & operator [] (int index); void changeSize (int newSize); int length(); string err();

private: T * els; int capacity; T dud; int errorCode; void deepCopy(const Array & a); };

template Array::Array(int size) { if (size < 1) { size = 1; errorCode = 1; } else { errorCode = 0; } els = new T[size]; capacity = size; }

template Array::~Array() { delete [] els; }

template Array::Array(const Array & a) { deepCopy(a); }

template Array & Array::operator = (const Array & a) { if (this == & a) return *this; delete [] els; deepCopy (a); return * this; }

template void Array::deepCopy (const Array & a) { capacity = a.capacity; errorCode = a.errorCode; els = new T[capacity]; for (int i = 0; i < capacity; i++) { els[i] = a.els[i]; } }

template T & Array::operator [](int index) { if (index < 0 || index >= capacity) { errorCode |= 2; return dud; } return els[index]; }

template void Array::changeSize(int newSize) { if (newSize < 0) { errorCode |= 4; return; } int numEls = (capacity > newSize ? newSize : capacity); T * temp = new T [newSize]; for (int i = 0; i < numEls; i++) { temp[i] = els[i]; } delete [] els; els = temp; capacity = newSize; }

template int Array::length() { return capacity; }

template string Array::err() { if (errorCode == 0) return "No error. "; string s = ""; if (errorCode & 1) s = s + "non-positive size for constructor. Size set to 1. "; if (errorCode & 2) s = s + "index out of range. "; if (errorCode & 4) s = s + "non-positive newSize for changeSize. Size not changed. "; return s; }

#endif // ARRAY_H_INCLUDED