Jun 122012
 

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

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)