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. Balanced Brackets
  2. Discussions

Balanced Brackets

  • lynx3535
     + 0 comments

    C++ O(n)

    the idea:

    • each time you encounter an opening bracket, push it to the stack. each time you encounter a closing bracket, check if the opening bracket at the top of the stack matches the closing bracket, if so, pop the stack.
    • to prevent segmentation fault in case of encountring a closing bracket with an empty stack, simply return NO. this would for example here: }(){

    The code:

    string isBalanced(string s) {
    stack<char> stk;
    char top;
    for(char c : s){
        if(c == '(' || c == '[' || c == '{')
            stk.push(c);
						
        if(c == ')' || c == ']' || c == '}'){
            if(stk.empty()) return "NO";
            top = stk.top();
						
            if(c == ')' && top == '(' || c == ']' && top == '[' || c == '}' && top == '{')
                stk.pop();
								
            else
             return "NO";
        }
             
    }
    return stk.empty() ? "YES" : "NO";
}