Use Application of Stack and Queue for the code.

Question

2. Write a code in C++ [using object oriented approach] that will take a mathematical expression as input and output whether the parentheses are balanced or not in the expression.                          [10 points]

Sample Input: (5 + (9-(3+2))+ 4)

Sample Output: Balanced 

Sample Input: (5 + (9-(3+2)+ 4)

Sample Output: Not Balanced

(Note:Sir,please use object oriented approach)

Answer 1

using namespace std;

#include <iostream>

#include <stack>

#include <queue>

#include <string.h>

/****************************************

* if LEFT PARENTHESIS '(' is encountered: pushes onto the stack...

*if RIGHT PARENTHESIS ')' is encountered:

if the stack is empty, then NOT BALANCED !!! (too many RIGHT PARENTHESIS)

otherwise pops off th stack;

* AFTER the loop if the stack is empty, then the parenthesis are BALANCED!

Otherwise they are not!! (too many LEFT Parenthesis)

**************************************************************/

DoStack(char * mathExpression)

{

cout << "** Using the STACK to Verify that the parenthesis are BALANCED *** "<< endl;

cout << "The math expression is:>"<<mathExpression<<"<" <<endl;

int nStrLen = strlen(mathExpression);

stack<int> _stack;

int x=1;

bool boolBalancedFlag = true;

for (int iLoop=0; iLoop<nStrLen; iLoop++)

{

if (mathExpression[iLoop]=='(')

{

_stack.push(x);

}

if (mathExpression[iLoop]==')')

{

if ( _stack.empty())

{

boolBalancedFlag=false;

break;

}

else

{

_stack.pop();

}

}

}

boolBalancedFlag=_stack.empty();

if (boolBalancedFlag)

{

cout << " YES , PARENTHESIS ARE BALANCED " << endl;

}

else

{

cout << " NO! UNBALANCED MISMATCHED PARENTHESIS " << endl;

}

cout << endl << endl;

}

/***************************************************

if LEFT PARENTHESIS '(' is encountered, pushes onto the queue;

if RIGHT PARENTHESIS ')' is encountred, pops off the queue;

after the loop, if the queue is empty, then the parenthesis are BALANCED!

********************************************************/

DoQueue(char * mathExpression)

{

cout << "** Using the QUEUE to verify that the parenthesis are BALANCED *** "<< endl;

cout << "The math expression is:>"<<mathExpression<<"<" <<endl;

int nStrLen = strlen(mathExpression);

queue<int> Q;

int x=1;

for (int iLoop=0; iLoop<nStrLen; iLoop++)

{

if (mathExpression[iLoop]=='(')

{

Q.push(x);

}

if (mathExpression[iLoop]==')')

{

Q.pop();

}

}

if (Q.empty())

{

cout << " YES , PARENTHESIS ARE BALANCED " << endl;

}

else

{

cout << " NO! UNBALANCED MISMATCHED PARENTHESIS " << endl;

}

cout << endl << endl;

}

Go(char * mathExpression)

{

DoStack(mathExpression);

DoQueue(mathExpression);

}

main()

{

char balancedMathExpression[]= "(5+(9-(3+2))+4)";

char unbalancedMathExpression[]= "(5+(9-(3+2)+4)";

Go(balancedMathExpression);

Go(unbalancedMathExpression);

}