Output of a C language Program
June 12, 2012
Compute polynomial, Cn.x^n + Cn-1.x^(n-1) + … … + C2.x^2 + C1.x + C0
June 12, 2012

Check if parenthesis are matched or not

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

Your email address will not be published. Required fields are marked *