How do I use C++ to ensure that a program has a balanced set of curly braces; th

Question

How do I use C++ to ensure that a program has a balanced set of curly braces; that is, for every open curly brace, there is a corresponding close brace. In addition, you should not have a close curly brace without having a corresponding open curly brace first.

NOTE: Remember that things in comments should not be considered. The interface for the programming assignment should ask the user to enter a file to check for correctness, after the file is entered, it should display an appropriate message. Then ask the user if they would like to continue.

P.S : Use the image above as the content of the test txt file

Explanation / Answer

#include<iostream>
#include<stdlib.h>
#define bool int

using namespace std;

/* structure of a stack node */
struct sNode
{
   char data;
   struct sNode *next;
};

/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data);

/* Function to pop an item from stack*/
int pop(struct sNode** top_ref);

/* Returns 1 if character1 and character2 are matching left
   and right Parenthesis */
bool isMatchingPair(char character1, char character2)
{
   if (character1 == '(' && character2 == ')')
     return 1;
   else if (character1 == '{' && character2 == '}')
     return 1;
   else if (character1 == '[' && character2 == ']')
     return 1;
   else
     return 0;
}

/*Return 1 if expression has balanced Parenthesis */
bool areParenthesisBalanced(char exp[])
{
   int i = 0;

   /* Declare an empty character stack */
   struct sNode *stack = NULL;

   /* Traverse the given expression to check matching parenthesis */
   while (exp[i])
   {
      /*If the exp[i] is a starting parenthesis then push it*/
      if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
        push(&stack, exp[i]);

      /* If exp[i] is a ending parenthesis then pop from stack and
          check if the popped parenthesis is a matching pair*/
      if (exp[i] == '}' || exp[i] == ')' || exp[i] == ']')
      {
           
          /*If we see an ending parenthesis without a pair then return false*/
         if (stack == NULL)
           return 0;

         /* Pop the top element from stack, if it is not a pair
            parenthesis of character then there is a mismatch.
            This happens for expressions like {(}) */
         else if ( !isMatchingPair(pop(&stack), exp[i]) )
           return 0;
      }
      i++;
   }
  
   /* If there is something left in expression then there is a starting
      parenthesis without a closing parenthesis */
   if (stack == NULL)
     return 1; /*balanced*/
   else
     return 0; /*not balanced*/
}

/* UTILITY FUNCTIONS */
/*driver program to test above functions*/
int main()
{
char exp[500] = "{()}[]";
char c;
do{
      cout<<"Enter text:"<<endl;
      cin>>exp;
      if (areParenthesisBalanced(exp))
       cout<<" Balanced Text ";
      else
       cout<<" Not Balanced ";
      
   cout<<"Do you wan to continue: (y/Y)";
   cin>>c;
   }while(c == 'y' || c=='Y');
return 0;
}  

/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data)
{
/* allocate node */
struct sNode* new_node =
            (struct sNode*) malloc(sizeof(struct sNode));

if (new_node == NULL)
{
     cout<<"Stack overflow ";
     exit(0);
}         

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*top_ref);

/* move the head to point to the new node */
(*top_ref)    = new_node;
}

/* Function to pop an item from stack*/
int pop(struct sNode** top_ref)
{
char res;
struct sNode *top;

/*If stack is empty then error */
if (*top_ref == NULL)
{
     cout<<"Stack overflow ";
     exit(0);
}
else
{
     top = *top_ref;
     res = top->data;
     *top_ref = top->next;
     free(top);
     return res;
}
}

/*

Output:

Enter text:
{()}[]

Balanced Text
Do you wan to continue: (y/Y)y
Enter text:
dwedw{}{Fww}[deeded[[]]](wdw)

Balanced Text
Do you wan to continue: (y/Y)y
Enter text:
dwdwed{wdwd{{dwd}}}}dw

Not Balanced
Do you wan to continue: (y/Y)n

*/

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.