MCN Professionals | Interview Question of the day
MCN Professionals is starting Industrial Training for MCA-2012 Batch. Have a look at our Industrial Training Program and Course Details.
-----------------------------------------------------------------------------------------------------------------------------------------
Today's Question:
Write a function which will accept a string of parenthesis ( '(' & ')' characters ) and return true if the parenthesis are matched and false otherwise (if the parenthesis are not matched). For example, for the below inpit Strings, the return values should be as follows:
Input String: ( UnMatched
Input String: () Matched
Input String: (() UnMatched
Input String: ()() Matched
Input String: (((()))) Matched
Input String: ()()(()) Matched
Input String: (((() UnMatched
Solution:
To solve this problem we will use Stack.
Algorithm:
For each element in the String do the following:
1. If str[i] is '(' then push is in the Stack
2. If str[i] is ')' then look at the stack.
If the stack is empty or the top element of the stack is NOT '(', unmatched parenthesis
return false
else
pop Stack
After all the elements are done, Check the Stack,
If Stack has element
return false
else
return true
Code:
int matchedParenthesis(char *str)
{
Stack s;
for(int i=0; i<strlen(str); i++){
if(str[i] == '(')
s.push(str[i]);
else if(str[i] == ')')
{
if(s.isEmpty() || s.pop() != '(')
return false;
}
}
if(! s.isEmpty())
return false;
else
return true;
}
---------------------------------------------------------------------------
Interview Questions Archive:
To see all the questions in the category click
here...