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 |
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; }