We want to give a logspace algorithm for deciding the set of strings
of properly nested parenthesis and brackets.
Consider the following two-stage logspace algorithm:
Stage 1: Using two counters, make a pass through the input from left
to right. Each time a ( is encountered, increase P by 1; each time a
) is encountered, decrease P by 1. Same for B and [ and ]. So P and
B are the counters for parenthesis and brackets, respectively. Notice
that |P| and |B| are bounded by log(|w|) where w in {(,),[,]}^* is the
input.
If at any time P or B <0, or by the end P and B are not 0, then the
parenthesis and brackets are not properly paired.
Note that stage 1 could also have been broken up into two sub-stages,
where we first count P and then count B; we don't have to count them
simultaneously.
Stage 2: In the second stage we want to check that the parenthesis and
brackets are closed in the right order. For example, ([)] has the
right count after stage 1, but it is not a properly nested string.
We maintain 4 pointers to the input (so each has length at most
log(|w|)). We have pointers Pl,Pr,Bl,Br, standing for left
parenthesis, right parenthesis, left bracket, and right bracket,
respectively.
We process the input from left to right, as follows: at each step,
either Pl or Bl points to ( or [. Then, Pr or Br searches for the
corresponding ) or ] starting at the left ( or [. The search can be
implemented with a single counter C which increases by 1 on left
parenthesis (bracket) and decreases by 1 on right parenthesis
(bracket). If stage 1 was successful, we know such a right
parenthesis (bracket) can be found. So now Pr or Br points to the
right ) or ].
Suppose that the next symbol to the right of ( is also (. Then the
process is repeated. Similarly, if the next symbol to the right of [
is [, the process is repeated. Closing parenthesis/brackets are
ignored.
However, if there is alternation---the next symbol to the right of (
is [---then we have to check that BrPr,
and so it is not a proper string.
Consider: ([][()])
At first Pl=1 and Pr=8.
Then Bl=2 and Br=3