Regex Golf 的解答

Belleve Invis · 2013-12-22

今天看到有人在传这个网站,正好自己号称了解编译原理于是尝试解答,答案如下:

  1. Plain Strings:「foo」。很简单不是么
  2. Anchors:「ick$」。
  3. Ranges:「^[a-f]*$」。
  4. Backrefs:「(...).*\1」。这一题的要求不是正则集合。
  5. Abba:「^((?!(.)(.)\3\2).)*$」。这一题的要求也不是正则集合。
  6. A man, a plan:这题目不是正则语言,也不能用带反向引用的正则表达式表示之。一个 Chear 解:「^(.)[^p].*\1$
  7. Prime:「^(?!^x?$|^(xx+?)\1+$)」。表达式「^x?$|^(xx+?)\1+$」总是匹配合数个 x,利用否定预查就可以了。
  8. Four:「(.)(.\1){3}」。
  9. Order:「^a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z*$」。
  10. Triples:「^([0369]|[258][0369]*[147]|[147]([0369]|[147][0369]*[258])*[258]|[258][0369]*[258]([0369]|[147][0369]*[258])*[258]|[147]([0369]|[147][0369]*[258])*[147][0369]*[147]|[258][0369]*[258]([0369]|[147][0369]*[258])*[147][0369]*[147])*$」。和前面几个问题不同,这个题目要求的集合是正则的,你可以用 36 个节点的 DFA 表示之。
  11. Glob:「^(\*?)(\w*)(\*?)(\w*)(\*?)(\w*) matches ((.(?!\1))+|\1)\2((.(?!\3))+|\3)\4((.(?!\5))+|\5)\6$」。利用否定预查。
  12. Balance:「^(<(<(<(<(<(<<>>)*>)*>)*>)*>)*>)*$」。同样非正则,只能处理有限深度。
  13. Powers:「^(((((((((x|xx)\9?)\8?)\7?)\6?)\5?)\4?)\3?)\2?)\1?$」。