You might have heard of Regular Expressions, but this question is about Irregular Expressions, a concept we just invented. An irregular expression is a pattern string that can be used to match target strings. Here's an example pattern that can be used to "accept" or "reject" target strings:
adbsk[kkjsvf]bbb
There are two rules for matching a target string to a pattern like the one above:
- Any lowercase letter that is not inside square brackets in the pattern must match to the same letter in the target string, in the correct position.
- If a set of lowercase letters appears in square brackets in the pattern, the target string must contain, at that point in the string, exactly half of these letters (rounded up) in any order.
There are lots of target strings that match the above pattern ( to be precise). Here are a few of them. The parts that match the bracketed portion are highlighted:
adbskkkjbbb, adbskjkkbbb, adbskskfbbb, adbskfjkbbb
Of course, there are infinitely many targets that do not match. Here are a few of them:
adbskkkjsbbb, adbskjkbbb, adbsjsvbbb, adbsksfjbb, fhfghj tomato pesto
An irregular expression can be any length, can use any plain lowercase letter, and can contain zero or more non-nested square bracket sections.
The input will contain lines. Each line will consist of an irregular expression pattern string followed by target strings to match, all separated by spaces. Your program must output either true
or false
for each target string depending on whether it matches the pattern. The words true
and false
must be lowercase and separated by a single space. You should produce a separate line of text for each line in the input. The maximum length for each pattern and each target string is characters.
Note that the test data below has only lines, but the real data file will have .
Sample Input
adbsk[kkjsvf]bbb adbskkkjbbb adbskkkjsbbb adbskskfbbb adbsjsvbbb fhfghj
fkqm[qzqyledbqq]c fkqmdqqqlc fkqmqlbyq fkqmqedqc fkqmblqqzc fkqmlqbdzc
dj[mocn]dd djnmdd djocdd djmodd djmodd djcndd
wsvahfskbs[uucysmlfrcnhu]mjgphbd this problem is ridiculous dude
a[aauzujbtipmca]bsk aiamzuausk acuaaujabsk aaaauucbsk aazpubtubsk aiaujcambsk
Sample Output
true false true false false
true false false true true
true true true true true
false false false false false
false true false true true
Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org
Comments