0

我会尽量使描述尽可能简单。

我被要求为只有0的正则表达式提供一个解决方案，1 说不0\*匹配任何内容或任何只有0的字符串。

我有三个运营.商\*，，|

  • .结合两个正则表达式r1和r1，r1匹配s1和r2匹配s2, s = s1 + s2

  • |就像或者，结合 r1, r2，要么 r1 匹配 s1，要么 r2 匹配 s2(r1|r2) matches s = s1 + s2

  • \*只是明星案例，没有或更多的逻辑。

所有的运算符和 0 和 1 都存储在二叉树中。

完整参考：http ://www.cdf.toronto.edu/~heap/148/F13/Assignments/A2/a2.pdf

我试图找到一个递归解决方案。

以（任何以1((1.(0|1)\*).0)开头并以0结尾的字符串）匹配为例：100101010

.右边是正则表达式树的根，对于它的左孩子和1.(0|1)\*右孩子 0，递归求解match('1.(0|1)\*', 10010101)，对于它的右孩子0，递归求解match('0', 0)。

对于正确的孩子，它将返回 true，

左边部分继续递归步骤。

就像是

def match(rx, s):
    if rx == s:
         // base case when s is 0 or 1
         return True
    else:
         return False
    x = 'some number'
    s1 = s[:x]
    s2 = s[x:]
    if rx.operator == '.':
       return match(rx.left, s1) and match(rx.right, s2)
    elif rx.operator == '|':
       return match(rx.left, s1) or match(rx.right, s2)
    else:
       return solveStar(rx, s)

两部分我现在卡住了，首先我应该如何划分字符串以匹配子正则表达式，其次我对解决星 * 案例感到困惑

4

0 回答 0