Question

Write a program to validate parenthesis of any given equation by using the following criteria (you MUST use stacks); Number of open parenthesis “(“must be same as number of close parentheses “)” For example if I input “3 + 4 * (98+34*(34+8)*34*(3+x)” the program should display an error message, because number of open parenthesis “(“is 3 and number of closed “)” parenthesis is 2.

Stack-Driver.cpp:

#include "stack.h"
#include "stack.cpp"
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int main() {
   stack<int> my_stack(100);
   srand(time(NULL));
   for (int i = 0; i < 10; i++) {
       my_stack.push(rand() % 10 + 1);
   }
   cout << "stack size is: " << my_stack.getSize() << endl;
   cout << "top of the stack: " << my_stack.peek() << endl;
   while (!my_stack.isEmpty())
       cout << my_stack.pop() << " - ";
   cout << endl;
   //my_stack.~stack();

}

Stack.h:

#pragma once
#ifndef STACK_H
#define STACK_H
#include<iostream>
using namespace std;
template<class T>
class stack
{
public:
   stack(int ); // constructor
   ~stack();
   T peek(); // returns the top item from stack without removing
   void push(T anItem);
   T pop(); // remove top element and return it
   bool isEmpty(); // check if teh stack is empty
   //void print_the_stack();
   int getSize(); // return size of stack
private:
   T* a;
   int size;// count howmany items are in the stack
   int capacity;// maximum capacity of the stack

};
#endif // !STACK_H

Stack.cpp:

#include "stack.h"
template<class T>
stack<T>::stack(int capacity) {

   size = 0;
   this->capacity = capacity;
   a = new T[capacity];
}
template<class T>
T stack<T>::peek() {
   return a[size-1];
}

template<class T>
void stack<T>::push(T anItem) {
   a[size] = anItem;
   size++;
}
template<class T>
T stack<T>::pop() {
   if (size >0) {
       size--;
       return a[size];
   }
}

template<class T>
int stack<T>::getSize() {
   return size;
}
template<class T>
bool stack<T>::isEmpty() {
   return size > 0 ? false : true;
}
template<class T>
stack<T>::~stack() {
   delete[] a;
}

Answer 1

C++ program for the provided problem statement

// c++ program to validate the parenthesis in the expression
// using stack
#include<iostream>
#include<stack>
#include<string>
using namespace std;

// this function will check if the opening and closing parenthesis
// are of the same type
bool isParenthesisPair(char openingParenthesis, char closingParenthesis)
{
   if(openingParenthesis == '(' && closingParenthesis == ')'){
   return true;
   }else if(openingParenthesis == '{' && closingParenthesis == '}'){
   return true;
   }else if(openingParenthesis == '[' && closingParenthesis == ']'){
   return true;
   } else{
   return false;
   }
}

// this method will match the opening and closing parenthesis respectively
// if no. of opening parenthesis == no. of the closing parenthesis
// then it will return true otherwise false
bool isExpBalanced(string expn)
{
// initialize an stack
   stack<char> S;
  
   // iterate the complete expression
   for(int i =0;i<expn.length();i++)
   {
   // if opening parenthesis appears, push it to the stack
       if(expn[i] == '(' || expn[i] == '{' || expn[i] == '['){
       S.push(expn[i]);
       }
       // if closing parenthesis appears then check the stack to
       // find the appropriate pair
       // to find the pair, call a helper function isParenthesisPair()
       else if(expn[i] == ')' || expn[i] == '}' || expn[i] == ']')
       {
       // for a closing parenthesis
       // if stack is empty and there is no pair then return false
       // else pop the top of the stack
           if(S.empty() || !isParenthesisPair(S.top(),expn[i])){
               return false;
       }else{
       S.pop();
       }
       }
   }
   // at the end, if all parenthesis are matched and stack is empty
   // then return true else return false
   return S.empty() ? true:false;
}

// driver function
int main()
{
// provide test cases
   int testCases = 0;
   cout<<"Enter number of test cases: ";
   cin>>testCases;
  
   while(testCases-- > 0){
  
   // input expression
   string expn;
   cout<<"\nEnter an expression: ";
   cin>>expn;
  
   bool result = isExpBalanced(expn);
  
   if(result){
   cout<<"It is a balanced expression !!\n";
   }else{
   cout<<"It is not a balanced expression !!\n";
   }
   }
}

C++ program Screenshots

C++ program Output Screenshot