5 Easy, difficult, and impossible tasks
Some things are difficult or impossible with regular expressions, and many are elegant and highly expressive. The puzzles in this chapter ask you to think about which situation each puzzle describes.
Puzzle 18 Identifying equal counts
Summary
In this puzzle we would like to balance starting and ending symbols.
At times we encounter a message or a stream that uses balanced “increment” and “decrement” symbols. For example, one way to check that a message has terminated might be to match up the increments and decrements. The same concept would apply to many kinds of messages and symbols—perhaps you would like to set the table with the same number of forks and knives, for example.
As a simplification of the general problem, write a regular expression that matches strings that consist of any number of A characters, followed by the same number of B characters.
For example AAABBB and AAAAAAABBBBBBB should match, while AAAABBBBBB should fail to match.
Author thoughts Lateral thinking might help you find the answer
You cannot match patterns based on having an equal number of different symbols using regular expressions. Or at least you cannot do so in the general case. It is, of course, perfectly possible to require exactly seven A’s and exactly seven B’s. But if the count is arbitrarily large, the kind of “machine” that can match the message requires additional power.