We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Stacks
  4. Balanced Brackets
  5. Discussions

Balanced Brackets

Sort by

recency

|

1634 Discussions

|

  • bonnemai
     + 0 comments
    def isBalanced(s):
    _map={')': '(', ']':'[', '}':'{'}
    q=[] 
    for character in s:
        if character in '([{': 
            q.append(character)
        elif character in ')]}': 
            if not q: 
                return 'NO'
            last=q.pop()
            if last!=_map[character]: 
                return 'NO'
    return 'YES' if not q else 'NO'

  • xavi_aclm
     + 0 comments

    use a lifo queue and scan left to right

  • gauravvgaikwad07
     + 0 comments

    What's the issue?

    include

    using namespace std; void printstack(stack s){ while(!s.empty()){ cout< st; bool t=true; for (auto ch:s){ if ((ch=='(')||(ch=='[') || (ch=='{')){ st.push(ch); //printstack(st); }else{ if ((ch==')') && (st.top()=='(')){ st.pop(); }else if((ch==']') &&(st.top()=='[')){ st.pop(); }else if((ch=='}') && (st.top()=='{')){ st.pop(); }else{ return "NO"; } } }

    if (st.empty()){
    return "YES";
}else{
    return "NO";
}

    } int main(){ int t; cin>>t; while(t--){ string s; cin>>s; cout<

  • f97gp1
     + 0 comments

    I try a recursive solution just for fun (won't pass the test cases)

        # rest of the code ...
    # the methods are naive methods and self explained.
    # `stack` variable could be considered as a global variable.
    def isBalanced(self, s: str, stack: deque) -> bool:
        c: str = s[0]
        
        if self.isOpenBracket(c):
            stack.append(c)
        else:
            stack_top: str = stack.pop()
            if not self.areBothBracketsBalanced(stack_top, c):
                print('\tnot-match: ', stack_top, c)

                return False
            
            if len(s) == 1 and len(stack) == 0:
                print('\tfinal-case OK')
                
                return True
        
        # New solution.
        new_sol: str = s[1:]
        
        if len(new_sol) > 0:
            return self.isBalanced(new_sol, stack)

  • rajivaiyer
     + 0 comments

    Fairly simple Stack based problem. Nothing too complex.

    Here's my Java 8 solution, passing all test cases, for Max Score of 25:

    class Result {
    
    private static final String B_ROUND  = "()";
    private static final String B_SQUARE = "[]";
    private static final String B_CURLY  = "{}";
    
    private static String getBracketType(Character bracketCh) {
        return getBracketType("" + bracketCh);
    }
    
    private static String getBracketType(String bracketStr) {
        switch(bracketStr) {
            case "(":
            case ")":
                return B_ROUND;
            case "[":
            case "]":
                return B_SQUARE;
            case "{":
            case "}":
                return B_CURLY;
            default:
                return "";
        }
    }
    
    private static Character getExpectedOpenBracketCh(String curBracketType) {
        switch (curBracketType) {
            case B_ROUND:
                return '(';
            case B_SQUARE:
                return '[';
            case B_CURLY:
                return '{';
            default:
                return 'd';
        }
    }
    
    /*
     * Complete the 'isBalanced' function below.
     *
     * The function is expected to return a STRING.
     * The function accepts STRING s as parameter.
     */

    public static String isBalanced(String s) {
        // Write your code here
        Stack<Character> bracketsStack = new Stack<>();

        System.err.println(""); System.err.println("");
        System.err.println("s=" + s);

        for (int sIdx = 0 ; sIdx < s.length() ; sIdx++) {

            Character sCh = s.charAt(sIdx);
            String curBracketType = getBracketType(sCh);
            
            // System.err.println("sIdx=" + sIdx + " | sCh=" + sCh + " | " +
            //                    "curBracketType=" + curBracketType);

            switch(sCh) {
                case '(':
                case '[':
                case '{':
                    bracketsStack.push(sCh);
                    break;

                case ')':
                case ']':
                case '}':
                
                    if (bracketsStack.isEmpty()) {
                        return "NO";
                    }

                    Character peekStackTopBracket =
                                  bracketsStack.peek();

                    Character expectedOpenBracket = 
                                  getExpectedOpenBracketCh(curBracketType);
                                  
                    // System.err.println("peekStackTopBracket=" + 
                    //                    peekStackTopBracket + " | " +
                    //                    "expectedOpenBracket=" + 
                    //                    expectedOpenBracket);

                    if (peekStackTopBracket != expectedOpenBracket) {
                        return "NO";
                    }

                    bracketsStack.pop();
                    break;
            }
        }
        
        if (!bracketsStack.isEmpty()) {
            return "NO";
        }

        return "YES";
    }

}