Parenthesis Checker

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 = [(]).

Note: The driver code prints “balanced” if function return true, otherwise it prints “not balanced”.

Examples :

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

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

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

Expected Time Complexity: O(|x|)
Expected Auixilliary Space: O(|x|)

Constraints:
1 ≤ |x| ≤ 10⁵

Approach 01:

class Solution{
    public:
    //Function to check if brackets are balanced or not.
    bool ispar(string bracketsString){
        int n = bracketsString.size();
        if(n%2 != 0){
            return false;
        }
        stack<char> st;
        
        for(auto &ch: bracketsString){
            if(ch == '('){
                st.push(')');    
            }
            else if(ch == '['){
                st.push(']');    
            }
            else if(ch == '{'){
                st.push('}');    
            }
            else{
                if(st.empty()){
                    return false;
                }
                else{
                    char top = st.top();
                    st.pop();
                    if(ch != top){
                        return false;
                    }
                }
            }
        }
        return st.empty();
    }
};

class Solution:

    # Function to check if brackets are balanced or not.
    def ispar(self, bracketsString):
        stack = []
        
        # If the length of the string is odd, it can't be balanced
        if len(bracketsString) % 2 != 0:
            return False

        for char in bracketsString:
            if char == '(':
                stack.append(')')
            elif char == '{':
                stack.append('}')
            elif char == '[':
                stack.append(']')
            else:
                if len(stack) == 0:
                    return False
                else:
                    top = stack.pop()
                    if top != char:
                        return False

        # If stack is not empty, the brackets are not balanced
        return len(stack) == 0

Time Complexity

• Iterating through the string:

  The function iterates through each character in the input string bracketsString exactly once. This operation takes \(O(n)\), where \(n\) is the length of the input string.

• Stack Operations:

  Each character is either pushed or popped from the stack at most once. Pushing and popping elements from the stack are both \(O(1)\) operations. As the stack operations occur for each character, the time complexity remains \(O(n)\).

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where \(n\) is the length of the input string.

Space Complexity

• Space for Stack:

  In the worst case, the stack stores half of the characters from the input string (i.e., when all opening brackets are encountered first). Therefore, the space complexity for the stack is \(O(n/2)\), which simplifies to \(O(n)\).

• Overall Space Complexity:

  The overall space complexity is \(O(n)\), where \(n\) is the length of the input string, as the stack can store up to half of the characters in the worst case.