如何检测文本替换是否导致无限循环?

问题描述 投票:0回答:2

我开发了一个从其他程序中提取文本的程序。其中一个功能是用户可以指定“替换脚本”来处理文本。示例替换脚本:

|ORIG|a|BECOMES|bb|END|
|ORIG|b|BECOMES|cc|END|

替换过程搜索任何ORIG文本并将其替换为相应的BECOMES文本。因此,如果提取文本aaaa,它将首先替换为bbbbbbbb,然后替换为cccccccccccccccc

当存在这样的替换脚本时会出现问题:

|ORIG|a|BECOMES|bb|END|
|ORIG|b|BECOMES|aa|END|

并且在提取的文本中有一个a。那a变成bb变成aaaa变成bbbbbbbb等无限。

因此,我需要两种算法:1。读取替换脚本并检测它是否可能创建无限循环(因此我可以警告用户)。 2.执行替换脚本时检测无限循环(因此我可以中止操作并通知用户)。

我不知道从哪里开始。我已经考虑过这个问题超过两个星期而已经无处可去。

algorithm language-agnostic
2个回答
0
投票

如果第一个脚本的ORIG是第二个脚本的BECOMES的一部分,您可以尝试使用表示替换脚本的节点和将一个脚本连接到另一个脚本的边来构建图形。

然后你可以在这个图中搜索循环,告诉你你可以无限期地应用这个循环中的规则。


0
投票

如果任何ORIG等于或任何BECOMES的子串,那么你可能会遇到问题。

© www.soinside.com 2019 - 2024. All rights reserved.