收藏本站腾讯微博新浪微博

经典论坛

 找回密码
 注册

QQ登录

只需一步,快速开始

蓝色理想 最新研发动态 网站开通淘帖功能 - 蓝色理想插件 论坛内容导读一页看论坛 - 给官方提建议

论坛活动及任务 地图和邮件任务 请多用悬赏提问 热夏来袭,选一款蓝色理想的个性T恤吧!

手机上论坛,使用APP获得更好体验 急需前端攻城狮,获得内部推荐机会 论坛开通淘帖功能,收藏终于可以分类了!

搜索
查看: 2776|回复: 20

一个非常有趣的正则问题,大家来研究一下

[复制链接]
发表于 2009-12-19 01:28:07 | 显示全部楼层 |阅读模式
最近的项目中有一个比较特殊的要求,是要根据正则替换字符串中某个匹配编组的内容,非常有趣,举例说明一下:
例如正则表达式为:
  1. (mod-(\d+-)?)?(act(ion)?)-(?:add(s)?|edit)-(\d+)-(\d+)-(\d+)
复制代码

字符串为:
  1. action-add-5-5-5
复制代码

(这里的正则表达式和字符串都是不定的,而且正则的规则是没有限制的,可以包含嵌套编组和非捕获编组,但是一定是可以成功匹配的。)
要求是将捕获到的 $7 的引用内容替换成 8,然后再替换到原来的字符串中相应的位置去,得到新的字符串(这里的组号和值也是不定的),那么对于上面的正则和字符串来说替换后的结果应该是:
  1. action-add-5-8-5
复制代码

俺和我佛山人讨论了一下,佛子给出了一个js的解决方案,俺呢就写了一个vbs的,我们两个的切入点都差不多,但是思路和解决方法差别很大。

大家可以先发挥一下,js和vbs都可以,看看还有没有好的想法,不想写代码写写思路也成。

童鞋们玩的时候,方法的原型就采用下面的好了:
  1. replacePart(txt,rule,part,replacement)
复制代码

调用时也用请用上面的例子来测试,当然,你有更刁钻的正则更好。

==== 更新 =============================

下面就帖出俺的vbs的解决方案,请大家指正:

 提示:您可以先修改部分代码再运行



为了方便童鞋们测试,俺把格式帖好:
JS:

 提示:您可以先修改部分代码再运行


VBS:

 提示:您可以先修改部分代码再运行


[[i] 本帖最后由 coldstone 于 2009-12-20 02:55 编辑 ]
发表于 2009-12-19 07:56:35 | 显示全部楼层
这个描述看不明白,“正则不确定”   是指什么意思?
回复 支持 反对

使用道具 举报

发表于 2009-12-19 09:30:58 | 显示全部楼层
lz的想法是扩展一下js的 replace 方法,使用反向引用(backreference)实现部分替换,
可以将部分替换理解成部分保留
回复 支持 反对

使用道具 举报

 楼主| 发表于 2009-12-19 10:31:19 | 显示全部楼层
原帖由 [i]baishui 于 2009-12-19 07:56 发表
这个描述看不明白,“正则不确定”   是指什么意思?

就是用户可以自己输入的。你可以理解为就是要写一个函数,那四个参数是可以任意输入的,只要满足文本和正则匹配就行。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2009-12-19 12:25:32 | 显示全部楼层
举几个例子吧:
  1. =======================
  2. txt : test/34-29
  3. rule : (\w+)/(\d+)-(\d+)
  4. part : $2
  5. replacement : 89
  6. result: test/89-29
  7. =======================
  8. txt : www.blueidea.com
  9. rule : ^(?:ftp|bbs|www)\.([a-z0-9][a-z0-9-]*)\.([a-z]{2,4})$
  10. part : $1
  11. replacement : google
  12. result: www.google.com
  13. =======================
  14. txt : news/2009-12/19/
  15. rule : ^([a-z]{3,5})/(\d{4})-([0]?\d|(11|12))/([0-2]?\d|(30|31))[/]?$
  16. part : $5
  17. replacement : 25
  18. result: news/2009-12/25/
复制代码


就是要实现这样的替换。

有一点需要注意,就是字符串中有重复的值,只能替换指定的内容,这也是这个替换的唯一难点:
  1. txt : test/34-34
  2. rule : (\w+)/(\d+)-(\d+)
  3. part : $2
  4. replacement : 89
  5. result: test/89-34
复制代码

[[i] 本帖最后由 coldstone 于 2009-12-19 22:21 编辑 ]
回复 支持 反对

使用道具 举报

发表于 2009-12-19 19:11:02 | 显示全部楼层
要求是将捕获到的 $7 的引用内容替换成 8
这个在js,.net等用replacement参数传function就可以了啊.
js里
arguments[0] 是lastMatch
最后俩是index和input 即"下标"n-1和n-2

其它是arguments[1] 到 arguments[n - 3] ($1-$n)

如demo
  1. javascript:void '0abcd'.replace(/0(a)b(c)/,function () {alert(Array.prototype.slice.call(arguments, 0).join('\n------\n'))});
复制代码


.net里道理也一样.会给MatchEvaluator传一个Match的实例
回复 支持 反对

使用道具 举报

 楼主| 发表于 2009-12-19 20:30:55 | 显示全部楼层

回复 6# muxrwc 的帖子

取出来和做替换都是很简单的事,需要做的是如何在替换相应的部分后再还原成原来的字符串。
回复 支持 反对

使用道具 举报

发表于 2009-12-19 20:55:51 | 显示全部楼层

回复 7# coldstone [楼主] 的帖子

还原是说什么意思?

txt : test/34-34
rule : (\w+)/(\d+)-(\d+)
part : $2
replacement : 89
result: test/89-34

不是替换指定group么.
回复 支持 反对

使用道具 举报

发表于 2009-12-19 21:05:12 | 显示全部楼层
= =,喔...
抱歉...了解了...
这个.net里比较好搞...js里要算下...我去改下...

[[i] 本帖最后由 muxrwc 于 2009-12-19 21:07 编辑 ]
回复 支持 反对

使用道具 举报

发表于 2009-12-19 22:08:31 | 显示全部楼层
= =,先来个简单的山寨的方案...
这个没有解决分组在分支和预查里的情况...

  1. <script type="text/javascript">
  2. var replacePart = function (txt, rule, part, replacement) {
  3.         var index = part.match(/\d+/)[0];
  4.        
  5.         var getExpression = function () {
  6.                 var expression = [], floor = 0, i = 0;
  7.                
  8.                 rule.source.replace(/(?:[^\(\\)]|\\.|(\(\?[:!=]))+|(\()|(\))/g, function (l, ngs, s, e) {
  9.                         if (i < index) {
  10.                                 if (s) {
  11.                                         ++ floor, ++ i;
  12.                                 } else if (ngs) {
  13.                                         ++ floor;
  14.                                 } else if (e) {
  15.                                         -- floor;
  16.                                 }
  17.                                 expression.push(l);
  18.                         }
  19.                 });

  20.                 expression.pop();
  21.                 if (floor - 1) expression.push(new Array(floor).join(')'));
  22.                 return expression.join('');
  23.         };

  24.         return String(txt).replace(rule, function (l) {
  25.                 var regex = new RegExp(getExpression(), rule.toString().match(/[^\/]*$/)[0]);
  26.                 var len = txt.match(regex)[0].length;
  27.                 return l.slice(0, len) + replacement + l.slice(len + arguments[index].length);
  28.         });
  29. };

  30. alert('result:' + replacePart('action/addzz-5/5/zzzz-5', /(mod-(\d+-)?)?(act(ion)?)\/(?:add(on|an)?(ss|zz)?|edit)-(\d+)\/(\d+)\/(\w+)-(\d+)/ig, '$6', 'xx'));
  31. </script>
复制代码

[[i] 本帖最后由 muxrwc 于 2009-12-20 00:00 编辑 ]
回复 支持 反对

使用道具 举报

发表于 2009-12-19 22:19:19 | 显示全部楼层
楼上的,你这个正则改掉的话,就失效了,不通用哦。

[[i] 本帖最后由 nicoljiang 于 2009-12-19 22:28 编辑 ]
回复 支持 反对

使用道具 举报

发表于 2009-12-19 22:42:37 | 显示全部楼层

回复 11# nicoljiang 的帖子

改了下^^
回复 支持 反对

使用道具 举报

 楼主| 发表于 2009-12-19 23:08:21 | 显示全部楼层

回复 10# muxrwc 的帖子

非常不错的想法!
呵呵,我这里有个极端的正则例子,我自己的代码开始也替换错了,老兄可以再完善一下:
txt  = "action/addzz-5/5/zzzz-5";
rule = /(mod-(\d+-)?)?(act(ion)?)/(?:add(on|an)?(ss|zz)?|edit)-(\d+)/(\d+)/(\w+)-(\d+)/ig;
part = "$6";
replacement = "XX";

这个例子的极端之处在于,$6 是处于一个非捕获匹配中,但是它本身又是可以被捕获的,而且有相应的匹配。

[[i] 本帖最后由 coldstone 于 2009-12-19 23:45 编辑 ]
回复 支持 反对

使用道具 举报

发表于 2009-12-19 23:13:49 | 显示全部楼层
12楼那个还是不行,
比如把连结符号换一下:
txt = "action-add+5+5+5"
rule = /(mod-(\d+-)?)?(act(ion)?)-(?:add(s)?|edit)+(\d+)\+(\d+)\+(\d+)/
回复 支持 反对

使用道具 举报

发表于 2009-12-19 23:16:07 | 显示全部楼层
楼主发在13楼的那个也不行啊,不用那么极端,换个连结符号就不行了~
回复 支持 反对

使用道具 举报

 楼主| 发表于 2009-12-19 23:39:31 | 显示全部楼层
原帖由 [i]nicoljiang 于 2009-12-19 23:16 发表
楼主发在13楼的那个也不行啊,不用那么极端,换个连结符号就不行了~

对,连结符号是不应该影响结果的。那是正则的一部分,只能根据正则表达式中的语法来。我把13楼修改一下,来个终极版的正则,如果这个正则通过了,应该问题就不大了。
回复 支持 反对

使用道具 举报

发表于 2009-12-20 00:02:09 | 显示全部楼层
没想到这个帖子又浮上来了,我的js或vbs很一般,但是在php中用过正则。
这个问题可以不可以这样考虑:像程序语言一样准确定位 函数的第3个参数(即反向引用的序号)所引用的内容(也就是要被替换的内容)。
把正则看成字符串,将函数的第3个参数(即反向引用的序号)引用(捕获)的位置从正则里定位出来,这个方法应该是任何实现正则表达式的语言通常都实现了的,因为它肯定会用反向引用的序号正确的定位正则表达式的具体位置,如果谁能像程序语言自身一样正确实现这种定位,应该就可以实现以局部地替换正则表达式任一反向引用的序号所引用的位置的内容。

如果不看底层代码,通常我会想到使用正则来计算反向引用的序号所引用(捕获)的内容(就是算出正确的括号),但在一些很复杂的正则式里,很难考虑周全,比如子查询嵌套非常多、纯字符串里也包含括号、非捕获模式 甚至这些情况交织在一起等等,我发现自己很难用正则捕获那个要命的括号

程序语言的底层代码里应该有完善的算法,光说不练,我是不太了解他们对一个表达式是如何顺利对号入座的捕获的
回复 支持 反对

使用道具 举报

发表于 2009-12-20 00:05:39 | 显示全部楼层

回复 16# coldstone [楼主] 的帖子

改了下10楼的代码...
忘记了(?.的括号也要补充全...呵呵...

其实这个方案,我觉得不理想= =,因为如果有分组存在于复杂的分支,那么截取必然会导致匹配结果不正确.这个应该算是比较极端了.
,不过想不出好的解决办法了,因为要是重新自己写个正则解释函数代价有点过大了.
或者
用匹配结果来匹配表达式...这个成本也挺大的...类似于dfa了,不过nfa,dfa的概念还不是很理解,只是知道有它存在XD.
回复 支持 反对

使用道具 举报

发表于 2009-12-20 00:06:19 | 显示全部楼层
如果是.net的话就简单了,每个group都有自己的index,还真是和谐的设计呢...呵呵...
回复 支持 反对

使用道具 举报

 楼主| 发表于 2009-12-20 00:36:07 | 显示全部楼层

回复

@askok:
要解决这个问题,都需要从分析正则表达式入手,我的解决办法就和你这里提出的思路一样,通过分析正则表达式来确定匹配字符串的位置,然后再进行相应的替换并还原字符串。

@muxrwc:
你的思路和佛子一样,通过分析正则表达式的语法,不得不佩服你们的算法的强悍。虽然结果可能并不完美严谨,但过程的确很优雅,而且足矣应付普通的应用了,像我例子中的极端情况在实际应用中其实是基本不会出现的。另外我的解决方案其实也通过计算出每个group的index来进行替换的。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2009-12-20 02:50:55 | 显示全部楼层
明天要出去,上不了网,先把我的解决方法帖出来吧,请指正。VBS的:
  1. <script language="vbscript">
  2. Dim txt,rule,part,replacement
  3. txt  = "action/add中文zz-5/5/zz-5"
  4. rule = "(mod-(\d+-)?)?(act(ion)?)/(?:add([\u4e00-\u9fa5]{1,2})?(ss|zz)?|edit)-(\d+)(/|-)(\d+)/(\w+)-(\d+)"
  5. part = "$6"
  6. replacement = "XX"
  7.    
  8. document.write "txt : " & txt
  9. document.write "<br />rule : " & rule
  10. document.write "<br />part : " & part
  11. document.write "<br />replacement : " & replacement
  12. document.write "<br />result: " & replacePart(txt,rule,part,replacement)
  13.    
  14. Function replacePart(ByVal txt, ByVal rule, ByVal part, ByVal replacement)
  15.         Dim Reg,Match,i,j,ma,pos,uleft,ul
  16.         Set Reg = New Regexp
  17.         Reg.Global = True
  18.         Reg.IgnoreCase = True
  19.         Reg.Pattern = rule
  20.         If Not Reg.Test(txt) Then replacePart = "unMatch" : Exit Function
  21.         i = Int(Mid(part,2))-1
  22.         Set Match = Reg.Execute(txt)(0)
  23.         Set Reg = Nothing
  24.         For j = 0 To Match.SubMatches.Count-1
  25.                 ma = Match.SubMatches(j)
  26.                 pos = Instr(txt,ma)
  27.                 If pos > 0 Then
  28.                         ul = Left(txt,pos-1)
  29.                         txt = Mid(txt,Len(ul)+1)
  30.                         If i = j Then
  31.                                 replacePart = uleft & ul & Replace(txt,ma,replacement,pos-len(ul),1,0)
  32.                                 Exit For
  33.                         End If
  34.                         uleft = uleft & ul & ma
  35.                         txt = Mid(txt, Len(ma)+1)
  36.                 End If
  37.         Next
  38.         Set Match = Nothing
  39. End Function
  40. </script>
复制代码

可运行代码主帖已更新。

[[i] 本帖最后由 coldstone 于 2009-12-20 03:25 编辑 ]
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

QQ|小黑屋|Archiver|手机版|blueidea.com ( 湘ICP备12001430号 )  

GMT+8, 2020-10-23 10:38 , Processed in 0.124683 second(s), 9 queries , Gzip On, Memcache On.

Powered by Discuz! X3.2 Licensed

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表