Bracket Sequence Validation

You are given a string consisting solely of the characters [ and ]. Your task is to determine whether the bracket sequence is valid.

A valid sequence is defined by the following rules:

• An empty string is valid.
• If A is a valid sequence, then [A] is also valid.
• If A and B are valid sequences, then their concatenation AB is valid.

In mathematical terms, let balance denote the difference between the number of [ and ] encountered while processing the string from left to right. The sequence is valid if and only if the following two conditions hold:

\(\text{balance} \ge 0\) for every prefix of the sequence, and \(\text{balance} = 0\) at the end of the sequence.

Write a program that reads a bracket sequence from standard input and prints True if it is valid, and False otherwise.

inputFormat

The input consists of a single line containing a non-empty string of characters. The string contains only the characters [ and ].

outputFormat

Output a single line: True if the bracket sequence is valid, and False otherwise.

[]

True