Lesson 1

A parenthesis sequence is a sequence of opening and closing parentheses. Informally, such a sequence is called valid if each opening parenthesis can be matched with a closing one. Examples of valid parenthesis sequences:

• \(\texttt{()}\)
• \(\texttt{(())}\)
• \(\texttt{()()}\)
• \(\texttt{(()(()))()}\)

Examples of invalid parenthesis sequences:

• \(\texttt{(}\)
• \(\texttt{)(}\)
• \(\texttt{(()())(()}\)
• \(\texttt{(()(()())))(()}\)

Formally, a valid parenthesis sequence can be defined as follows. The balance of a parenthesis sequence is the difference between the number of opening and closing parentheses. Then, a sequence is called valid if its balance is zero and the balance of any of its prefixes is non-negative.