Question

Write a pseudocode method to determine if a set of parentheses and brackets is balanced. For example, such a method should return true for the string, "[()]{}{[()()]()}" and false for the string "[(])". Discuss how the algorithm will perform and how much space in memory it will take if somebody passes a massive string as input.

Answer 1

pseudocode method:

Boolean isBalance(S)

1. Set I=0

2. Repeat Step 3 While S[I] not equal to NULL do

3. IF S[I]= '(' then Push(S[I])

ELSE IF S[I]= '{' then Push(S[I])

ELSE IF S[I]= '[' then Push(S[I])

ELSE IF S[I]= ')' AND Peek() = '(' then Pop()

ELSE IF S[I]= '}' AND Peek() = '{' then Pop()

ELSE IF S[I]= ']' AND Peek() = '[' then Pop()

[End of IF]

[End of Loop]

4. IF Isempty() = True Return True

5. Else Return False

6. End

In this algorithm we are using a Stack data structure. At the beginning the stack is empty. Now read the given string from left to right until the end of the string. When a read symbol is open bracket (e.g. ( or { or [ ) then push it on to the stack. Otherwise, when a read symbol is close bracket (e.g. ) or } or ] ) and top of stack contains corresponding pair bracket then pop from the stack. Finally, check the stack is empty or not, if it is empty then brackets are balanced otherwise not balanced.

In this algorithm, extra memory for the stack data structure is needed, that is maximum of length of the given string. So, the space complexity is O(n) and time complexity also O(n).

Program in c++:

#include<iostream>
#include<stdlib.h>

using namespace std;

const int MAX = 100;

typedef struct stack
{
   char st[MAX];
   int top;
}stack;

stack stk;

void push(char x);
char pop();
char peek();

bool isbalance(char s[])
{
   for(int i=0; s[i]!='\0'; i++)
   {
       switch(s[i])
       {
           case '(':
           case '{':
           case '[':
               push(s[i]);
               break;
           case ')':
               if(peek()=='(') pop();
               break;
           case '}':
               if(peek()=='{') pop();
               break;
           case ']':
               if(peek()=='[') pop();
               break;
       }
   }
   if(stk.top==-1) return true;
  
   return false;
}

int main()
{
   int n,i,x;
   stk.top = -1;
   char s[MAX];

   cout<<"Enter string: :";
   cin>>s;
  
   bool f = isbalance(s);
  
   if(f==true)
       cout<<"Balanced"<<endl;
   else
       cout<<"Not Balanced"<<endl;
      
   return 0;
  
}

void push(char x)
{
if(stk.top==MAX-1){
   printf("Stack overflow\n");
return;
}
stk.st[++stk.top] = x;
}

char pop()
{
if(stk.top==-1){
   printf("Stack underflow\n");
return 0;
}
return stk.st[stk.top--];
}

char peek()
{
   return stk.st[stk.top];
}

Output:

Enter string: :[()]{}{[()()]()}
Balanced

Enter string: :[(])
Not Balanced