Given intstack.h, usestack.cpp, and evalfull.cpp.

You must write a C++ function balanced to complete this program the evalfull.cpp.

. Edit evalFull.cpp so that balanced implements the following algorithm:

// Balanced Parentheses Algorithm loop through all the tokens in the expression (up to numTokens): identify the token (using the utility function named identify) if token is a left parenthesis: push it on the stack named s if token is a right parenthesis (means a left should be on the stack): if stack is empty - done: found out not balanced, so return false else pop a left parenthesis ignore any other token end of loop (stack should be empty) - done: return true if empty, else false 

Just one stack is needed, and it is already created in the skeleton: stack s is an object of the STL stack class that is set up to store C strings like "(".

Compile and test it on some balanced and some unbalanced expressions. If balanced, the program should print a result, or at least throw a different exception string like the following sample runs of our solution:

enter expression: ( 4 + 7 ) result: 11 enter expression: ( 4 + 7 / 2 ) bad expression: operator(s) left on stack at end enter expression: ( 4 7 ) bad expression: empty stack where operator expected 

Then Edit usestack.cpp again to try this algorithm on a postfix expression (remember the stack in usestack.cpp only handles int values), and print the results to cout. For example, here is how the second expression from above could be evaluated (starts with a fresh stack):

// Postfix Expression Evaluation Algorithm create a stack for numbers (just need this one stack) loop through all the tokens in the expression: identify the token if token is a number: push it on the stack if token is an operator (means time to perform a calculation): pop a number - last one pushed, so it is on right side of calculation pop a second number - for the left side of the calculation perform the calculation, and push the result on the stack Done: result is on top of stack 

Example

// evaluating "7 5 3 * +" // start with an empty stack Stack numbers; // first three tokens all numbers to push "7 5 3": numbers.push(7); numbers.push(5); numbers.push(3); // fourth token is calculation to do "*": int right = numbers.top(); numbers.pop(); int left = numbers.top(); numbers.pop(); numbers.push(left * right); // last token is another calculation "+": right = numbers.top(); numbers.pop(); left = numbers.top(); numbers.pop(); numbers.push(left + right); // done - print result: cout << numbers.top() << endl; 

Please select a different expression - make up a simple one, but not too simple, so you know you understand the steps. Don't make it so complicated that you won't have time to complete it before lab ends. Show the expression you are evaluating in a comment at the top. Compile and test it.

// intstack.h - stack class  // The class is implemented here too. All very bare bones, // with no error-checking nor even pre-condition stating. // But know two things: (1) don't push on full stack, which // is a stack currently holding 10 ints; (2) don't pop or // top from empty stack - use bool empty() to check. #ifndef INTSTACK_H #define INTSTACK_H #define CAPACITY 10 class Stack { public: Stack() : next(0) { } void push(int n) { data[next++] = n; } void pop() { --next; } int top() const { return data[next-1]; } bool empty() const { return next <= 0; } private: int next, data[CAPACITY]; }; #endif 

// usestack.cpp - for practice using stacks #include "intstack.h" #include  using namespace std; int main() { Stack s; s.push(10); s.push(20); while (!s.empty()) { cout << s.top() << endl; s.pop(); } return 0; } 

// evalfull.cpp - evaluates a fully-parenthesized expression #include  // for atof function #include  // for sscanf #include  // for strcmp and strtok #include  #include  // STL stack class #include  // for throwing string exceptions using namespace std; // constants used to identify a token - DO NOT CHANGE enum TokenType {LEFT, RIGHT, ADD, SUBTRACT, MULTIPLY, DIVIDE, NUMBER, OTHER}; TokenType identify(char *t); // balanced - returns true only if parentheses are balanced // in the expression, where expression is an array of C // string tokens like { "(", "4.2", ")" } and numTokens // is the number of tokens in the array (3 in the sample) bool balanced(char *expression[], int numTokens) { stack s; // USE s TO SOLVE THE PROBLEM - it is an STL // (Standard Template Library) structure with // all of the same operations as the stack from // Step 2 of this lab, but it won't get full // and it can store any type -  here return false; // REPLACE THIS return WITH ACTUAL IMPLEMENTATION } // DO NOT CHANGE ANYTHING BELOW - BUT DO READ IT // utility function returns one of those constants TokenType identify(char *t) { if (strcmp(t, "(") == 0) return LEFT; if (strcmp(t, ")") == 0) return RIGHT; if (strcmp(t, "+") == 0) return ADD; if (strcmp(t, "-") == 0) return SUBTRACT; if (strcmp(t, "*") == 0) return MULTIPLY; if (strcmp(t, "/") == 0) return DIVIDE; double value; if (sscanf(t, "%g", &value) == 1) return NUMBER; return OTHER; } // evalFull - evaluates a fully-parenthesized expression; // relies on function balanced; // returns result of the expression if it is formed properly // throws string message if expression is not proper double evalFull(char *expression[], int numTokens) { if ( !balanced(expression, numTokens) ) throw string("parentheses are not balanced"); stack numbers; stack ops; double result = 0, leftValue, rightValue; TokenType type, op; for (int i=0; i