1

我在 PHP 中编写了一个解析器，它可以根据前面问题的反馈将方程的字符串表示形式转换为 RPN 。在测试它时，我发现了两个不同的方程，它们在 RPN 中解析为同一事物。因为当你解决它们时，它们最终在 RPN 中是相同的，所以你会得到相同的答案。

  1. 3 + 4 * 8 / (1 -5)
  2. 3 + 4 * 8 / 1 -5

两者都以 348*15-/+ 结尾，解决后给出的答案为 -5，这对第一个是正确的，但第二个的答案应该是 30。

那么我是否误解了如何转换为 RPN？我的解析器的代码可以在上一个问题的上述链接中找到。

4

1 回答 1

1

我在您的解析器中发现了错误。在你的最后一个else大块，你需要更换

$current = end($stack);
if($operators[$tokens[$i]] == $operators[$current]) {
  $rpn .= array_pop($stack);
  $stack[] = $tokens[$i];
} else {
  $stack[] = $tokens[$i];
}

和

while(!empty($stack) && end($stack) != '(' && $operators[$tokens[$i]] >= $operators[end($stack)]) {
  $rpn .= array_pop($stack);
}
$stack[] = $tokens[$i];

更改后，您的两个测试用例在这里工作正常。（我使用此参考来修复您的代码。在解决您问题中的问题后，我停止检查您的代码，因此内部可能存在更多错误——我没有校对所有内容！）

编辑：重要的是将“==”替换为“>=”。如果您总是只有两个优先级，那么if用循环替换 并不是绝对必要的。

于 2009-11-27T13:22:58.147 回答