字符串匹配问题
最近遇到一道关于字符匹配的问题,想了好久还是写出来了。但是可能还是存在部分缺陷,代码中暂时没考虑和测试深层嵌套的问题。
问题描述
def matchIn(tp,str):
mstrs = tp.split('|')
mi = 0
for ss in mstrs:
si,i,sl = 0,0,len(ss)
while si<sl:
if ss[si]!='[' and ss[si]!='<' and ss[si]==str[i]:
i += 1
si += 1
elif ss[si]=='[':
ts = ss[si:]
ms = ss[si+1:si+ts.find(']')]
msl = len(ms)
if ms == str[i:i+ msl]:
i = i+ msl
si = si + msl + 2
elif ss[si]=='<':
ms = ss[si + 1:ss.find('>')]
msl = len(ms)
if ms == str[i:i+ msl]:
i = i+ msl
si = si + msl + 2
else:
break
else:
break
if si==sl:
mi=i
break
return mi
def ali_match(tp, str):
# 第一行,上述格式的语义模板表达式
# 第二行,用户的自然语言指令(即:用户query)
# 输出:
# 当前query是否匹配当前语义模板表达式。匹配,则输出1,否则输出0.
# 输入范例:
# <[播]放|来>[一|几]<首|曲|个>@{singer}的<歌[曲]|[流行]音乐>
# 来几首@{singer}的流行歌曲
if tp == '' and str == '':
return 1
elif tp == '':
return 0
elif tp[0] == '<':
mstr = tp.split('>')[0]
mlen = len(mstr)-1
st = matchIn(mstr[1:], str)
return st>0 and ali_match(tp[mlen+2:], str[st:])
elif tp[0] == '[':
mstr = tp.split(']')[0]
mlen = len(mstr)-1
st = matchIn(mstr[1:], str)
return (st > 0 and ali_match(tp[mlen + 2:], str[st:])) or ali_match(tp[mlen + 2:], str)
else:
mi = min([tp.find('<'),tp.find('['),len(tp)])
st = matchIn(tp[:mi], str)
return st>0 and ali_match(tp[mi:], str[st:])
if __name__ == '__main__':
tp = '<[播]放|来>[一|几]<首|曲|个>@{singer}的<[流行]歌[曲]|音乐>'
str = '来几首@{singer}的流行歌曲'
print(int(ali_match(tp, str)))