regex - Scala 中的简化正则表达式匹配

Question

我正在尝试编写一个简单的正则表达式匹配Scala作为练习。为简单起见，我假设要匹配的字符串是 ASCII 并且正则表达式由 ASCII 字符和两个元字符组成：.并且*只有。（显然，我不使用任何正则表达式库）。

这是我简单而缓慢（指数）的解决方案。

def doMatch(r: String, s: String): Boolean = {
  if (r.isEmpty) s.isEmpty
  否则 if (r.length > 1 && r(1) == '*') 星(r(0), r.tail.tail, s)
  else if (!s.isEmpty && (r(0) == '.' || r(0) == s(0))) doMatch(r.tail, s.tail)
  否则为假
}

def star(c: Char, r: String, s: String): Boolean = {
  if (doMatch(r, s)) 真
  else if (!s.isEmpty && (c == '.' || c == s(0))) star(c, r, s.tail)
  否则为假
}

现在我想改进它。您能否在大约 10-15 行“纯”Scala 代码中提出一个简单的多项式解决方案？