2 shunfurh shunfurh 于 2017.08.27 15:30 提问

Gensokyo Forbidden Words

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.
Input

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

Output should contains lines of regex. There are no special judge for this problem!

Sample Input

PAD
[Pp]ad
[!i]Pad
?pad
baka[9]
baka[[]9[]]

  • babaa ... Sample Output

PAD
[Pp]ad
[^i]Pad
.pad
baka[9]
baka[[]9[]]
.* babaa
[.][.][.]
More Sample Input

[!]]
[]]
[][!]
More Sample Output

[^]]
[]]
[][!]

1个回答

devmiao
devmiao   Ds   Rxr 2017.09.10 12:50
已采纳
Csdn user default icon
上传中...
上传图片
插入图片