Algorithm to Check Matching and Nesting of Grouping Symbols
Input: Sequence T = T1...Tn of n tokens; set G of pairs of grouping symbols.
Output: TRUE if all grouping symbols in T are correctly matched and nested; FALSE otherwise.
S ← new stack // S stores unmatched opening ("left") symbols; last-read on top.
for each i in 1..n
x ← Ti
if x is an opening symbol from G
push x on S
else if x is a closing symbol from G
if S is empty
// too many closing symbols
y = pop S
if x and y don't match
// mis-matched left and right symbols
// Note: if x is not a grouping symbol, we just ignore it.
if S is not empty
// too many opening symbols
// If execution reaches this point, we claim:
// - every token has been read,
// - all grouping symbols have been paired up,
// - no pair of symbols is incorrectly nested.
- Simulate the algorithm on a sample C++ program.
- Similate the algorithm on the same sample, modified to have various errors
in grouping symbol matching or nesting.