Algorithm to Check Matching of Parentheses
Input: Sequence T = T1...Tn of n tokens.
Output: TRUE if the parentheses in T are correctly matched; FALSE otherwise.
S ← new stack // S stores unmatched opening parentheses.
for each i in 1..n
x ← Ti
if x is '('
push x on S
else if x is ')'
if S is empty
// too many ')'s
// Note: if x is not a '(' or ')', we just ignore it.
if S is not empty
// too many '('s
// If execution reachees this point, we claim:
// - every token has been read,
// - all parentheses have been matched correctly.
Notice that we don't really need the stack. The only thing is stores is
'('s, so it is sufficient to keep track of how many of have been read but
not yet matched. We can do this just with a counter.
Re-write the given pseudo-code to use a counter (and integer variable) instead
of the stack. Intuitively, push becomes +1, pop becomes -1, etc.