Gensokyo Forbidden Words
Time Limit: 2 Seconds
Memory Limit: 65536 KB
In Gensokyo (幻想郷), there are many forbidden words such as "PAD", "baka⑨", and "sukima babaa". Hieda no Akyu (稗田阿求), the ninth Child of Miare with ability to not forget anything she sees and record Gensokyo's history, is who maintains the system of Gensokyo Forbidden Words. Currently, the system uses glob to match the forbidden words. The rules of glob are as follows:
- the asterisk character ("*") substitutes for any zero or more characters;
- the question mark ("?") substitutes for any one character;
- characters enclosed in square brackets ("[" and "]") substitute for all the characters in their ranges:
- the string enclosed by the brackets cannot be empty (thus, "[!]" matches the three characters '[', ']' and '!');
- two characters separated by '-' denote a range (thus, "-]" matches just the two characters ']' and '-', and "[--0]" matches the three characters '-', '.', '/' and '0');
- an expression "[!...]" substitute for all the characters not in their ranges, the string enclosed by the brackets cannot be empty;
- an expression "[^...]" is invalid.
Recently, Akyu is planning to upgrade the system to use more powerful regex (regular expression). The rules of regex are as follows:
- the asterisk character ("*") indicates there are zero or more of the preceding element. for example, ab*c matches "ac", "abc", "abbc", "abbbc", and so on;
- the question mark ("?") indicates there is zero or one of the preceding element. for example, colou?r matches both "color" and "colour";
- the dot character (".") matches any single character;
- a bracket expression ("[...]") matches a single character that is contained within the brackets:
- the string enclosed by the brackets cannot be empty;
- two characters separated by '-' denote a range;
- an expression "[^...]" matches a single character that is not contained within the brackets;
- the "-" character is treated as a literal character if it is the last or the first character within the brackets. the "]" character can be included in a bracket expression if it is the first character.
The input contains lines of valid glob, and is extremely large! It's guarantee that all brackets are well balanced, so "[" and "]" are invalid, but "[" and "]" are valid. Process to the end of file.
Output should contains lines of regex. There are no special judge for this problem!
More Sample Input
More Sample Output
Author: WU, Zejun
Source: ACM × Touhou
Contest: ZOJ Monthly, August 2010