Skip to main content

Balancing brackets

we are going to make the logic for isbalanced function correct.This article is part of my efforts where i have made many mistakes while thinking about problem solution which iam just recording over here.Finally i will also have the correct anwser in the same language.As it is self explanatory no Explantion.

Test Case 1

Python

Failure

class Solution:
    def isequal(self,f,s):
        ok=[['(',')'],
        ['[',']'],
        ['{','}'],
        ]
        for i in ok:
            s=s.replace(i[1],i[0])
        if f==s:
            return True
        else : 
           
            return False
            
    def isBalanced(self, s):
        # code here
        s=s.strip()
        s.replace(" ","")
        n=len(s)
        #should be even
        if n%2!=0:
            return False
        m=n//2
        f=s[:m]
        t=s[m:]
        t=t[::-1]
        return self.isequal(f,t)
            

My above program got failed at this test case "{[()()]}" in gfg.



Correct Approach

The algorithm uses a stack πŸ“š to ensure that each opening bracket ((, {, [) has a corresponding and correctly ordered closing bracket (), }, ]). If all brackets are properly matched, the stack will be empty by the end of the string, indicating a valid sequence. ✅

πŸ”„Approach

1️⃣ Iterate through the string:

Push each opening bracket ((, {, [) onto a stack. πŸ“₯

For each closing bracket (), }, ]):

Check if it matches the top of the stack (i.e., the most recent unmatched opening bracket). πŸ”

If the stack is empty or the bracket doesn’t match, the string is invalid, and we return false. ❌

2️⃣ Final check:

After iterating through the entire string, if the stack is empty, it means every opening bracket has a corresponding closing bracket, and the sequence is valid. πŸŽ‰

c++ code

class Solution {
public:
    bool ispar(string s) {
        if (s.length() <= 1) return false;

        stack<char> stack;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '[' || s[i] == '{' || s[i] == '(') {
                stack.push(s[i]);
            }
            else if (stack.empty()) {
                return false;
            }
            else {
                if (s[i] == ')' && stack.top() != '(') return false;
                if (s[i] == '}' && stack.top() != '{') return false;
                if (s[i] == ']' && stack.top() != '[') return false;
                stack.pop();
            }
        }
        return stack.empty();
    }
};

Python

Result successfull

this more clearly explain the logic of balancing stack

class Solution:

            
    def isBalanced(self, s):
        # code here
        stack=[]
        
        s=s.strip()
        s=s.replace(" ","")
        n=len(s)
        #should be even
        if n%2!=0:
            return False
        open="({["
        # stack = deque()
        for i in s:
            if i in open:
                stack.append(i)
            else:
            
            
                if not stack:
                    return False
                if i==']' and stack[-1]=='[':
                    stack.pop()
                elif i==')' and stack[-1]=='(':
                    stack.pop()
                elif i=='}' and stack[-1]=='{':
                    stack.pop()
                else:
                    return False
        return len(stack)==0      

Another Short version

class Solution:
    def isBalanced(self, s):
        stack = []
        s = s.strip().replace(" ", "")  # Fix inplace mutation

        brackets = {'(': ')', '{': '}', '[': ']'}
        opening = brackets.keys()
        closing = brackets.values()

        for char in s:
            if char in opening:
                stack.append(char)
            elif char in closing:
                if not stack or brackets[stack[-1]] != char:
                    return False
                stack.pop()

        return len(stack) == 0

Finally


Comments