algorithm - 以下哪个后缀表示法正确表示中缀和 1+2+3+4？

Question

我正在测试一个中缀到后缀到中缀的转换器，并发现了某种不确定性。例如，一个简单的中缀和

1 + 2 + 3 + 4

可以转换为后缀一

1 2 + 3 + 4 +

假设不累积具有相同优先级的运算符。如果他们是那么我得到

1 2 3 4 + + +

另一方面，以下所有后缀表达式都可以转换为初始和

1 2 + 3 + 4 +
1 2 + 3 4 + +
1 2 3 4 + + +

所有这些后缀表达式都正确吗？

如果你要做这样的转换器，你会选择哪种形式？我需要选择一个进行测试。

score 7 · Accepted Answer

您需要定义一个额外的约束。

从数学上讲，您的后缀表达式都是相同的。但是在计算机上，整数加法并不是真正可交换的，因为溢出。

将 1 2 3 4 替换为 abcd 并考虑溢出的可能性。大多数编程语言都定义a + b + c + d必须从左到右进行评估，以便这a b + c + d +是唯一正确的翻译。

仅当您定义评估顺序为“未指定”时，所有后缀版本都是等效的。（较旧的）C 编译器就是这种情况。

score 5 · Accepted Answer

是的，都正确。它们对应于以下括号中的中缀表达式：

((1 + 2) + 3) + 4
(1 + 2) + (3 + 4)
1 + (2 + (3 + 4))

score 2 · Accepted Answer

+令人困惑 - 它是可交换的，所以事实上，每个结果似乎都是正确的。

考虑用+其他运算符替换：1 a 2 b 3 c 4.
对于左结合运算符，这里的正确结果是

1 2 a 3 b 4 c

所以，在你的情况下，我希望1 2 + 3 + 4 +

3 回答 3