Write a function that accepts a string of parenthesis ( ‘(‘ and ‘)‘ characters ) and return true if parenthesis are matched and false otherwise (if the parenthesis are not matched).
For example, for the below input 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 stack is empty or the top element of 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;
}