Challenge: Balanced Brackets

Lab Python Beginner 10 points

Read a line of text. Print balanced if every ( [ { is closed by the matching bracket in the right order (ignore all other characters), otherwise not balanced.

Input

One line of text.

Output

balanced or not balanced.

Example

Input

{[()()]}

Output

balanced

Sample input available Sample output available

Editor

Python

Hints

Push opening brackets.

A closing bracket must match what you pop.

At the end the stack must be empty.

Solution explanation

The most recent unclosed bracket is always on top, which is exactly the one that must close next.

Show solution

s = input()
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
ok = True
for ch in s:
    if ch in "([{":
        stack.append(ch)
    elif ch in pairs:
        if not stack or stack.pop() != pairs[ch]:
            ok = False
            break
print("balanced" if ok and not stack else "not balanced")

Output

Answer