Parenthesis Checker

Problem Statement - link #

Given an expression string x. Examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in exp. For example, the function should return ‘true’ for exp = “[()]{}{[()()]()}” and ‘false’ for exp = “[(])”.

Your Task: This is a function problem. You only need to complete the function ispar() that takes a string as a parameter and returns a boolean value true if brackets are balanced else returns false. The printing is done automatically by the driver code.

Expected Time Complexity: O(N) Expected Auxiliary Space: O(N)

Examples #

Example 1:

Input:
{([])}
Output: 
true
Explanation: 
{ ( [ ] ) }. Same colored brackets can form 
balaced pairs, with 0 number of 
unbalanced bracket.

Example 2:

Input: 
()
Output: 
true
Explanation: 
(). Same bracket can form balanced pairs, 
and here only 1 type of bracket is 
present and in balanced way.

Example 3:

Input: 
([]
Output: 
false
Explanation: 
([]. Here square bracket is balanced but 
the small bracket is not balanced and 
Hence , the output will be unbalanced.

Constraints #

• 1 <= N <= 32000

Solutions #

class Solution{
    public:
    //Function to check if brackets are balanced or not.
    bool check(char c1, char c2){
        return ((c1=='{' && c2=='}') || (c1=='[' && c2==']') || (c1=='(' && c2==')'));
    }
    bool ispar(string x)
    {
        // Your code here
        stack<char> s;
        for(char c: x){
            if(c == '{' || c == '[' || c == '(') s.push(c);
            else {
                if(s.empty() || !check(s.top(), c)) return false;
                s.pop();
            }
        }
        return s.empty();
    }
};