Parentheses matching using stacks

Parentheses matching problem

Given a string of characters ‘(‘ and ‘)’, we need to find if they form a valid parentheses, that is to say, find out if there are matching pairs or not. This known as parentheses matching problem.
Below are some examples

1. ()() : valid
2. (() : Invalid, not matching parenthesis
3. ((())) : Valid

This problem is also know as Onion peeling problem or balanced parentheses
Simple solution to this would be to maintain a counter. Initialize counter to zero. When ‘(‘ is encountered, increment counter and when ‘)’ is encountered, decrement counter. If at the end of processing entire string, if counter is zero, then string has balanced parenthesis.

Above algorithm will fail for ‘())(‘. In this case, counter will be zero but still string does not have balanced parenthesis. To tackle this case, after decrementing counter, check if counter is less than zero. If yes, then return false at that time, no need to traverse entire string.

Problem becomes interesting, when we have multiple kind of brackets in string i.e ‘[‘, ‘{‘ ,’}’, ‘]’ are also present in string. Then either we keep count of each type of bracket. This approach is not scalable.

Parenthesis matching with multiple kind of brackets is a typical problem where stacks are used. When character  ‘)’ or any closing bracket is encountered, all we are interested in is whether there is a matching ‘(‘ or opening bracket for it or not. If not, then parentheses string is not correct.

For asserting that the current closing parenthesis is in sync with what we have already seen, we just need to check if current parenthesis completes a pair with opening parenthesis we last seen.

Next closing parenthesis should complete pair with the one prior to last and so on.

Algorithm to check parentheses matching

1. Whenever we see a opening parenthesis, we put it on stack.
2. For closing parenthesis, check what is at the top of the stack, if it corresponding opening parenthesis, remove it from the top of the stack.
3. If parenthesis at the top of the stack is not corresponding opening parenthesis, return false, as there is no point check the string further. 
4. After processing entire string, check if stack is empty or not. 
   4.a If the stack is empty, return true. 
   4.b If stack is not empty, parenthesis do not match.

Parentheses matching implementation

#include<stdio.h>
#include<stdlib.h>
 
#define STACK_SIZE 10
 
typedef struct stack{
        int top;
        int items[STACK_SIZE];
}stack;
 
void push(stack *ms, int element){
   if(ms->top < STACK_SIZE-1){
   	   ms->top =  ms->top + 1;
       ms->items[ms->top] = element;
   }
   else {
       printf("Stack is full\n");
   }
}
 
void pop (stack *ms){
   if(ms->top >= 0){
       ms->top =  ms->top - 1;
   } 
   else{
       printf("Stack is empty\n");
   }
}
 
int peek(stack ms){
  if(ms.top<0){
      printf("Stack empty\n");
      return 0;
   }
   return ms.items[ms.top];
}
int isEmpty(stack ms){
   if(ms.top <0) return 1;
   else return 0;
}
 
int parenthesesMatching(char *s){
 
   stack ms;
   char temp;
   ms.top = -1;
 
   /* Wrong input */
   if(!s) return 0;
 
   /*Empty string */
   if(*s == '\0') return 1;
 
   while(*s != '\0'){
   //If char is opening parentheses, push it 
      if (*s == '(') 
         push(&ms, *s);
      else if(*s == ')'){
      /* If char is closing parenthesis, check if the top most 
      parenthesis on the stack is opening one or not */
          temp  = peek(ms);
          if(temp == '(')
             pop(&ms);
          else
             return 0;
       }
       s++;
   }
  /* If we have something is stack remaining */
   if(isEmpty(ms))
      return 1;
   else
      return 0;
}
 
/* Driver program */
int main(){
 char *str = "((()))";
 printf("%d\n", parenthesesMatching(str));
 
 return 0;
}

Complexity of parenthesis matching algorithm is O(N) time to scan N length string and O(N) extra space for stack.

Test cases

1. ((()))
True

2. ()))
False

3. )(((
False

4. (
False

5 Empty string
True

6. NULL pointer
False

Please share if there is something wrong or missing. If you are interested in contributing to algorithms and me, please contact us.