Let's parse some regex. Not quite the regex you are used to, but the formal regular expressions taught in courses on automata theory. Wikipedia knows what I'm talking about.
We have four operations. In order of priority, from highest to lowest:
- Parenthesis.
(a)- The contents of the parenthesis is a regular expression itself. This allows for nested parenthesis.
- Kleene star.
a*- The star denotes that the previous token may be matched zero or more number of times.
- Concatenation. Logical AND.
ab- This does what you think it does. It matches
afollowed byb.
- This does what you think it does. It matches
- Union, or alteration. Logical OR.
a|b- This matches
aorbbut notab.
- This matches
These characters have special meaning: *|()ε All other characters (except white-space) are in the language. There are no escape sequences.
ε denotes the empty string. If your language of choice does not support that character, tell us how we can change what character you used to denote the empty string.
The task:
Your program is supposed to read one line of well-formatted regex from stdin, followed by one line of text to be matched against that regex. If the regex accepts the string, output "yay" to stdout. Otherwise, output "nay" to stdout.
Yay-cases:
abc
abc
_
ab(c|d)*ef*
abcdcdcdddcce
_
ab(c|d)*ef*
abeff
_
[abc]*
[abc]
_
<(?P<tag>[A-Z][A-Z0-9]*)\b[^>]*>
<(?P<tag>[A-Z][A-Z0-9])\b[^>]>
_
a*
ε
_
a*b*c*
aaεbbεεbcε
_
a\(b\)c
a\b\c
_
a|b
b
Nay-cases:
abc
ab
_
ABC
abc
_
abc
abcd
_
[abc]*
abc
_
a+
aaaa
This is code golf, so lowest byte count wins.
