PythonMediumStack & Queue20 min

Validate balanced brackets

Only (), [] and {} appear. Every closing bracket must match the latest unmatched opening bracket; the empty string is valid. Interviewers use this problem to assess use a stack to model last-in-first-out matching.

Input

One line containing brackets.

Output

Print true or false in lowercase.

Constraints

0 <= length <= 100000.

Example

Input

{[()]}

Output

true

Example 2 input

()[]{}

Output

true

Adjacent balanced groups are valid.

Public test cases (2)

Input
```
{[()]}
```
Expected output
```
true
```
Input
```
([)]
```
Expected output
```
false
```

Hints (2)

Identify the state needed to avoid repeated work.
Use a stack to model last-in-first-out matching.

Target complexity: time O(n) · space O(n)

Your solution

import sys


def solve_balanced_brackets(s):
    # your code
    return False


if __name__ == "__main__":
    data = sys.stdin.read()
    s = data.split("\n", 1)[0]
    result = solve_balanced_brackets(s)
    print("true" if result else "false")

Standard input

Checking runner availability…

Reference solution

Check whether a number is prime · Easy
Check whether a string is a palindrome · Easy
Check whether two strings are anagrams · Easy
Compute the factorial of a number · Easy
Count vowels and consonants · Easy
Find the first occurrence with binary search · Easy
Find the missing number from zero through n · Easy
Find the second largest distinct value · Easy
Generate the Fibonacci series · Easy
Remove duplicate values while preserving order · Easy

All Python programs

Validate balanced brackets

Input

Output

Constraints

Example

Public test cases (2)

Your solution

Reference solution

More Python programs