假设我想通过替换字典中的占位符来扩展字符串。替换字符串也可以包含占位符:
$pattern = "#a# #b#";
$dict = array("a" => "foo", "b" => "bar #c#", "c" => "baz");
while($match_count = preg_match_all('/#([^#])+#/', $pattern, $matches)) {
for($i=0; $i<$match_count; $i++) {
$key = $matches[1][$i];
if(!isset($dict[$key])) { throw new Exception("'$key' not found!"); }
$pattern = str_replace($matches[0][$i], $dict[$key], $pattern);
}
}
echo $pattern;
只要没有圆形的替换模式，就可以正常工作，例如"c" => "#b#"。然后程序将被扔进一个无限循环，直到内存耗尽。
是否有一种简单的方法来检测这种模式?我正在寻找一个解决方案，其中替换之间的距离可以任意长，例如。a - c> b -> -> d - f ->
>理想情况下，解决方案也应该在循环中发生，而不是单独的分析。
单字符键
如果键是单个字符，这很容易:只需检查值端的字符串是否包含一个键字符。
foreach ($your_array as $key => $value) {
foreach(str_split($value) as $ch) {
if(array_key_exists ($ch,$your_array) {
#Problem, cycle is possible
}
}
}
#We're fine
现在即使有循环，这并不意味着它在每个字符串上都被触发(例如在空字符串中，没有模式被触发，因此没有循环)。在这种情况下，您可以将其合并到检查器中:如果第二次触发规则，则存在问题。很简单，因为如果是这种情况，前面的模式已经生成了这种情况，因此这种情况将会一次又一次地生成。
<<p> 字符串键/strong>如果键也是字符串，这可能是Post Correspondence Problem这是不可判定的…
感谢georg的评论和这篇文章，我想出了一个解决方案，将模式转换成图形，并使用拓扑排序来检查循环替换。
这是我的解决方案:
$dict = array("a" => "foo", "b" => "bar #c#", "c" => "baz #b#");
# Store incoming and outgoing "connections" for each key => pattern replacement
$nodes = array();
foreach($dict as $patternName => $pattern) {
if (!isset($nodes[$patternName])) {
$nodes[$patternName] = array("in" => array(), "out" => array());
}
$match_count = preg_match_all('/#([^#])+#/', $pattern, $matches);
for ($i=0; $i<$match_count; $i++) {
$key = $matches[1][$i];
if (!isset($dict[$key])) { throw new Exception("'$key' not found!"); }
if (!isset($nodes[$key])) {
$nodes[$key] = array("in" => array(), "out" => array());
}
$nodes[$key]["in"][] = $patternName;
$nodes[$patternName]["out"][] = $key;
}
}
# collect leaf nodes (no incoming connections)
$leafNodes = array();
foreach ($nodes as $key => $connections) {
if (empty($connections["in"])) {
$leafNodes[] = $key;
}
}
# Remove leaf nodes until none are left
while (!empty($leafNodes)) {
$nodeID = array_shift($leafNodes);
foreach ($nodes[$nodeID]["out"] as $outNode) {
$nodes[$outNode]['in'] = array_diff($nodes[$outNode]['in'], array($nodeID));
if (empty($nodes[$outNode]['in'])) {
$leafNodes[] = $outNode;
}
}
$nodes[$nodeID]['out'] = array();
}
# Check for non-leaf nodes. If any are left, there is a circular pattern
foreach ($nodes as $key => $node) {
if (!empty($node["in"]) || !empty($node["out"]) ) {
throw new Exception("Circular replacement pattern for '$key'!");
}
}
# Now we can safely do replacement
$pattern = "#a# #b#";
while ($match_count = preg_match_all('/#([^#])+#/', $pattern, $matches)) {
$key = $matches[1][$i];
$pattern = str_replace($matches[0][$i], $dict[$key], $pattern);
}
echo $pattern;