Given intstackh usestackcpp and evalfullcpp You must write a

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

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

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

Just one stack is needed, and it is already created in the skeleton: stack<char *> 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:

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):

Example

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.

Solution

For Paranthesis matching, the algortihm would be to have the same no of left and right paranthesis at one particular time.Hence, whenever we encounter a left paranthesis, we push it to the stack. Whenever we encounter a right one, we need to pop on left paranthesis from the stack. Here if stack is empty, means we don\'t have a left paranthesis for a right one,, hence expression is unbalanced. The second case where expression will be unbalanced if stack is not empty after checking the complete expression, means there are some extra left paranthesis which have remained on the stack. This is also a failure scenario. Else other than these, stack is balanced.

/* 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

// evalfull.cpp - evaluates a fully-parenthesized expression */

#include <cstdlib> // for atof function

#include <cstdio> // for sscanf

#include <cstring> // for strcmp and strtok

#include <iostream>

#include <stack> // STL stack class

#include <string> // 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<TokenType> parans;

TokenType operation, type;

for (int i=0; i<numTokens; i++) {

type = identify(expression[i]);

if(type == LEFT) {

parans.push(type);

} else if(type == RIGHT) {

// for the right paranthesesis, we must have a left paranthesis in the stack

if (parans.empty()) {

return false;

}

// otherwise pop a left paranthesesis from stack

operation = parans.top();

parans.pop();

}

}

// if still some paranthesis is there in the stack, it it not balanced then

if (!parans.empty()) {

return false;

}

return true;

}

// 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<double> numbers;

stack<TokenType> ops;

double result = 0, leftValue, rightValue;

TokenType type, op;

for (int i=0; i<numTokens; i++) {

type = identify(expression[i]);

switch(type) {

case NUMBER:

numbers.push( atof(expression[i]) );

break;

case ADD: case SUBTRACT: case MULTIPLY: case DIVIDE:

ops.push(type);

break;

case LEFT:

break; // ignore left paren (know balanced already)

case RIGHT:

if (numbers.empty())

throw string(\"empty stack where two numbers expected\");

rightValue = numbers.top();

numbers.pop();

if (ops.empty())

throw string(\"empty stack where operator expected\");

op = ops.top();

ops.pop();

if (numbers.empty())

throw string(\"empty stack where one number expected\");

leftValue = numbers.top();

numbers.pop();

if (op == ADD)

numbers.push(leftValue + rightValue);

else if (op == SUBTRACT)

numbers.push(leftValue - rightValue);

else if (op == MULTIPLY)

numbers.push(leftValue * rightValue);

else // op == DIVIDE

numbers.push(leftValue / rightValue);

break; // end right paren case

default:

throw string(\"unknown token: \")

+ string(expression[i]);

}

}

if (!ops.empty())

throw string(\"operator(s) left on stack at end\");

if (numbers.empty())

throw string(\"empty stack where one result should be\");

result = numbers.top();

numbers.pop();

if (!numbers.empty())

throw string(\"number(s) left on stack at end\");

return result;

}

#define MAXLEN 100

// main gets expression from user and evaluates it

int main() {

char input[MAXLEN], *tokens[MAXLEN/2];

cout << \"enter expression: \";

cin.getline(input, MAXLEN);

char *ptr = strtok(input, \" \");

int count = 0;

while (ptr != 0) {

tokens[count] = ptr;

++count;

ptr = strtok(0, \" \");

}

try {

double result = evalFull(tokens, count);

cout << \"result: \" << result << endl;

}

catch(string error) {

cerr << \"bad expression: \" << error << endl;

return 1;

}

return 0;

}

// I don\'t have the sample library template with me, hence i can\'t provide you with output. Please do try it and let me know in case of any errors as i couldn\'t test it.