Valid Parentheses Checker

You are given a string s consisting only of the characters (' and ')'. Your task is to determine whether the string is a valid parentheses sequence. A valid sequence is one where every opening parenthesis (' has a corresponding closing parenthesis ') and the pairs of parentheses are properly nested.

The problem can be formulated as follows:

Given an input string s, check if the sequence is valid, i.e. if it satisfies the following rules:

• Every '(' must have a corresponding ')'.
• The pairs of parentheses must be properly ordered (i.e. no unmatched or misordered pairs).

In mathematical terms, for a string s to be valid, it must hold that:

\[ \text{valid}(s) = \begin{cases} \text{True} & \text{if } s = \epsilon \text{ (empty string)},\\ \text{True} & \text{if } s = (s') \text{ and } \text{valid}(s') ,\\ \text{True} & \text{if } s = s_1 s_2, \text{ where } \text{valid}(s_1) \text{ and } \text{valid}(s_2),\\ \text{False} & \text{otherwise.} \end{cases} \]

Write a program that reads the input from standard input and outputs either True or False to standard output.

inputFormat

The input consists of a single line containing the string s which is made up of characters (' and ')'. The length of s can be zero or more.

outputFormat

Output True if the input string s is a valid sequence of parentheses, otherwise output False.

()

True