This post pertains to an interview question by Microsoft. The problem is to check if the order of parenthesis in a given string is correct, or "balanced". For example, the following string is balanced:
[{()}]()[{}]
While the following string is not balanced:
[{()}]([{}]
The algorithm is pretty simple, we use a stack data structure for this purpose. We push all the opening braces onto the stack, and on encountering a closing brace, we pop a brace from the stack and check if it matches the closing one. In addition, we check if the string length is odd, in which case it is automatically unbalanced.
The code:
#include <stdio.h>
#include <stdlib.h>
typedef struct stack stack;
struct stack {
char brace ;
stack * next ;
} *top = NULL ;
void push ( char val )
{
stack * ptr = (stack *) malloc(sizeof(stack)) ;
ptr -> brace = val ;
ptr -> next = top ;
top = ptr ;
}
char pop ()
{
stack * ptr ;
char ch ;
ptr = top ;
ch = top -> brace ;
top = top -> next ;
free (ptr) ;
return ch ;
}
char close(char ch)
{
if(ch==']')
return '[' ;
if(ch=='}')
return '{' ;
if(ch==')')
return '(' ;
return ' ' ;
}
int check_order (char * str)
{
int i , len = 0 ;
for(i=0;str[i]!='\0';i++)
len++ ;
if(len&1) // if string length is odd
return 0 ;
for(i=0;i<len;i++)
{
if(str[i]=='[' || str[i]=='{' || str[i]=='(')
push(str[i]);
else {
if(pop() != close(str[i]))
return 0 ;
}
}
return 1 ;
}
int main()
{
char str[100] ;
printf("Enter the string expression: ");
scanf("%s",str);
printf("The expression you entered is: %s .\n",str);
if( check_order(str) )
printf("Right Order");
else printf("Wrong Order");
return 0;
}
The above code can be modified to accept all strings that include parenthesis, such as
[{(2+3)}](4*5)[{}]
by adding one more if condition to ignore characters other than any of the braces.
