Question

Write a function that takes a string parameter and determines whether the string contains matching grouping symbols. Grouping symbols are parenthesis ( ) , brackets [] and curly braces { }. For example, the string {a(b+ac)d[xy]g} and kab*cd contain matching grouping symbols. However, the strings ac)cd(e(k, xy{za(dx)k, and {a(b+ac}d) do not contain matching grouping symbols. (Note: open and closed grouping symbols have to match both in number and in the order they occur in the string). Your function must use a stack data structure to determine whether the string parameter satisfies the condition described above. You may define your own stack class or use the STL stack class. Write a driver program (i.e. a function main()) to test your function.

Deliverables:

1. a copy of your function and the test driver program source codes in a text file

2. screen shots of your test driver program runs showing it meets the problem's specifications. This is what I've done so far: I've copied the material from the book as well as from some sources on the internet. Could you edit my code and write it in C++. Some of my code is in Java.

#ifndef QUEUE_H
#define QUEUE_H
#include <iostream>
using namespace std;

// Stack template
template <class T>
class Queue
{
private:
   T *queueArray;
   int queueSize;
   int front;
   int rear;
   int numItems;
public:
   //Constructor
   Queue(int);

   //Copy constructor
   Queue(const Queue &);

   //Destructor
   ~Queue();

   //Queue operations
   void enqueue(T);
   void dequeue(T &);
   bool isEmpty() const;
   bool isFull() const;
   void clear();
};

//This constructor creates an empty queue of a specified size
template <class T>
Queue<T>::Queue(int s)
{
   queueArray = new T[s];
   queueSize = s;
   front = -1;
   rear = -1;
   numItems = 0;
}
//Copy constructor
template <class T>
Queue<T>::Queue(const Queue &obj)
{
   //Allocate the queue array.
   queueArray = new T[obj.queueSize];

   //Copy the other object's attributes.
   queueSize = obj.queueSize;
   front = obj.front;
   rear = obj.rear;
   numItems = obj.numItems;

   //Copy the other object's queue array.
   for (int count = 0; count < obj.queueSize; count++)
       queueArray[count] = obj.queueArray[count];
}

//Destructor
template <class T>
Queue<T>::~Queue()
{
   delete[] queueArray;
}
//Function enqueue inserts a value at the rear of the queue.

tmeplate <class T>
void Queue<T>::enqueue(T item)
{
   if (isFull())
       cout << "The queue is full.\n";
   else
   {
       //Calculate the new rear position
       rear = (rear + 1) % queueSize;
       //Insert new item
       queueArray[rear] = item;
       // Update item count
       numItems++;
   }
}

//Function dequeue removes the value at the front of the queue and copies t into num

template <class T>
void Queue<T>::dequeue(T &item)
{
   if (isEmpty())
       cout << "The queue is empy. \n";
   else
   {
       //Move front
       front = (front + 1) % queueSize;
       //Retrieve the front item
       item = queueArray[front];
       // Update item count
       numItems--;
   }
}

template <class T>
bool Queue<T>::isEmpty() const
{
   bool status;

   if (numItems)
       status = false;
   else
       status = true;

   return status;
}
template <class T>
bool Queue<T>::isFull() const
{
   bool status;

   if (numItems < queueSize)
       status = false;
   else
       status = true;

   return status;
}
template <class T>
void Queue<T>::clear()
{
   front + queueSize - 1;
   rear = queueSize - 1;
   numItems = 0;
}

//Driver program to test the above functions
public static void main(String[] args)

{

   String exp1 = "{a(b+ac)d[xy],}, kab * cd";

   if (areParenthesisBalanced(exp1.toCharArray()))

       System.out.println("Balanced ");

   else

       System.out.println("Not Balanced ");

   String exp2 = "ac)cd(e(k, xy{za(dx)k";

   if (areParenthesisBalanced(exp2.toCharArray()))
       System.out.println("Balanced ");
   else

       System.out.println("Not Balanced ");

}
}
#endif

Answer 1

Program1.cpp

---------------------------------------------------------------------------------------------------------

#include<iostream>
#include<stack>
#include<string>
using namespace std;
// Function to check whether two characters are opening
// and closing of same type.
bool ArePair(char opening,char closing)
{
   if(opening == '(' && closing == ')') return true;
   else if(opening == '{' && closing == '}') return true;
   else if(opening == '[' && closing == ']') return true;
   return false;
}

//Function to check having matching symbols
bool haveMatchingSymbol(string exp)
{
   stack<char> S; //Taking STL stack class as mentioned that we can take this too
   for(int i =0;i<exp.length();i++)
   {
       if(exp[i] == '(' || exp[i] == '{' || exp[i] == '[')
           S.push(exp[i]);
       else if(exp[i] == ')' || exp[i] == '}' || exp[i] == ']')
       {
           if(S.empty() || !ArePair(S.top(),exp[i]))
               return false;
           else
               S.pop();
       }
   }
   return S.empty() ? true:false;
}

//Driver function to check the conditions
int main()
{
   string expression;
   cout<<"Enter an expression: "; // input expression from STDIN/Console
   cin>>expression;
   if(haveMatchingSymbol(expression))
       cout<<"Balanced and having balancing condition\n";
   else
       cout<<"Not Balanced\n";
}

-----------------------------------------------------------------------------------------------------------------------------------------

Screenshots of test driver program:-

98 %. Activities XTerm Thu Jun 13, 01:23 /home/aakash/pr Enter an expression: a(biac) d[ xylg] Balanced and having balancing condition Procons returned Press ENTER Lo continun execution timo: 38.241 o (0x0) PS TEFN

Activities XTerm Thu Jun 13, 01:22 /home/aakash/pr Cnter an exprossion: kabxc Balanced and having balancing condition execution timo: 18.053 Procons returned Press ENTER Lo continun (0x0) PS TEFN

4 98 %- Activities XTerm Thu Jun 13, 01:29 /home/aakash/pr nter an expronsion: oc) cd(o(k.xy(za (dx)k. Not. Balancnd Procons returned Press ENTER to continue. execution time: 190.096 (0x0) PS TEFN

Activities XTerm Thu Jun 13, 01:30 /home/aakash/pr Lnter an expronsion: (o (blac) d) Not. Balancnd Process returned Press ENTER to continue. execut.ion timo: 32.940 (0x0) PS TEFN