display | more...

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:

  1. If a string X contains no parentheses, then it is properly matched.
  2. If X is a properly matched string, then so is (X).
  3. If X and Y are properly matched strings, then so is XY.
  4. 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.

Log in or register to write something here or to contact authors.