C++ : Modify the following C++ code to use Stack to program a simple calculator

Note: This question is updated with more info on how to do

In this project, we will 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 (see chapter 2 in the textbook if you would like to. I outline the entire steps that you need to do here).

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.

See that this program requires us to do the following, which we have not learnt in class.

Split a string into tokens using space as separator

While processing the postfix expression, we read numbers and operators as strings. We push numbers as strings onto the stack. When we see an operator, we pop the strings, convert them to numbers, compute the result of the operation and push the number as a string onto the stack.

For (a) and (b), we will use stringstream. This requires that we include .

For (a), we do the following: // let expr be the postfix expression string

stringstream ss; // declare the stringstream object

ss.str (expr); // initialize ss to have the expr string

string item; // the string that will hold the number (or) operator from the ss object

while (getline(ss, item, )) { // read ss till we get to a space, and store that string in item object

// process as appropriate

}

For (b), reading a number as a string and pushing it onto the stack, we do the following (already the string is in item object)

if (item is not operator) { // write the necessary code to check item is not operator

stack1.push(item); // requires stack1 to have been declared already as

// Stack stack1;

continue; // finished processing the number from the postfix expression. So

// continue to the next item

}

// we come here only if the item is an operator, i.e., one of +, -, *, /

// We need to pop 2 elements from the stack and set them to num2 and num1

stringstream ss1; // this should have been declared before the loop. We will reuse

// this stringstream object for all number to string conversions and

// vice versa

string s; // string to hold the string that will be popped. We will reuse this

// for the 2 numbers tha twill be popped

int num1, num2; // to hold the 2 numbers that will be popped

stack1.pop(s); // pop one element from stack

ss1.str(s); // ss1 holds s

ss1 >> num2; // the token from ss1 will be stored in num2

ss1.seekg(0); // we need to start read/write ss1 from position 0

stack1.pop (s); // pop one more element from stack

ss1.str(s); // ss1 holds s

ss1 >> num1; // the token from ss1 will be stored in num1

ss1.seekg(0); // we need to start reading ss1 from position 0

int res; // to hold result of operation

if (item == +) res = num1 + num2;

else if (item == -) res = num1 num2;

// similarly handle * and /

// res should be converted to string and pushed onto stack1

ss1.str(); // set ss1 to have empty string. See that we are reusing ss1 again

ss1 << res; // ss1 now has the res as a string

ss1.seekg(0); // set ss1 to read/write from position 0

s = ss1.str(); // ss1.str() gets the string in ss1. This string is stored in s

stack1.push(s); // push s onto stack1

// When we come out of the loop, we have to pop from the stack, convert that to an integer

// and return that integer.

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