Daily Coding Problem - 27

day-27.py

"""
This problem was asked by Facebook.

Given a string of round, curly, and square open and closing brackets, return whether the brackets are balanced (well-formed).

For example, given the string "([])[]({})", you should return true.

Given the string "([)]" or "((()", you should return false.
"""
# Solution:
# We traverse the string
# If we encounter opening brace, we push to stack
# If we encounter closing brace, we check top of stack
# If top of stack has matching opening brace, then good, else unbalanced
# If we reach end of string and stack is empty, then good, else unbalanced
# We use a deque to implement a stack
from collections import deque

def check_balanced(string):
    # List of opening braces
    opening_braces = ['(', '[', '{']
    # List of closing braces
    closing_braces = [')', ']', '}']
    # Dictionary for checking matching opening and closing braces
    matching_braces = {')':'(', '}':'{', ']':'['}
    stack = deque()
    for elem in string:
        # If we see an opening brace, push it to stack
        if elem in opening_braces:
            stack.append(elem)
        # If we see a closing brace, check top of stack
        if elem in closing_braces:
            # If nothing in stack, then opening brace missing
            if len(stack) == 0:
                return False
            # If opening brace in stack is doesn't match, then unbalanced
            elif matching_braces[elem] != stack.pop():
                    return False
    # Reached end of string
    # If still elements in stack
    if len(stack) > 0:
        return False
    else:
        return True

string1 = "([])[]({})"
string2 = "([)]"
string3 = "((()"
print(check_balanced(string1))
print(check_balanced(string2))
print(check_balanced(string3))