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.