**An Algorithm for Checking Nested Parentheses**
This algorithm is useful in programming and computation theory to determine if a string has properly nested parentheses. A string is a finite sequence of characters, two of which can be the left parenthesis '(' and right parenthesis ')'. The set of *properly matched strings* is defined as follows:

- If a string X contains no parentheses, then it is properly matched.
- If X is a properly matched string, then so is (X).
- If X and Y are properly matched strings, then so is XY.
- Only strings that can be formed by rules 1-3 are properly matched strings.

Example 1: (5 * (1 + 2))(4)

Properly matched.

Start with 1 + 2 by rule 1;

(1 + 2) by rule 2;

5 * (1 + 2) by rules 1,3;

(5 * (1 + 2)) by rule 2;

(5 * (1 + 2))(4) by rules 1,3.

Example 2:

Properly matched. A string can be empty. (see rule 1)

Example 3: if(!(!(0.999 == 1))

**Not** properly matched.

There is an extra left parenthesis. (see rules 2,4)

Example 4: how to be a better monkey )tm(

**Not** properly matched.

Parentheses are out of order. (see rules 2,4)

**Related topics:** nested parentheses, Theory of Computation, context-free grammar, LISP.