非通勤运算符的中缀到后缀

Question

我对后缀与中缀中的 - / 运算符有疑问。

来自作业

The input string 5 4 + 3 10 * + is equivalent to the infix expression (5 + 4) + (3 * 10) The answer is 39.

我照着做。然后我对这个说法感到困惑。

We also have to worry about the non-commuting operators – and / . We will evaluate the postfix string 4 5 – as 4 – 5 and, likewise, will evaluate 4 5 / as 4 / 5 .

然而，当我这样做时......我得到了中缀和后缀的不同结果。

修改第一个示例以包含减法。

中缀

(5 - 4) + (3 * 10) = 31

后缀

5 4 - 3 10 * +

29....对吧？

所以我很困惑。中缀和后缀的结果应该是一样的吧？这是实际作业中的错字还是我做错了什么？

Answer 1

后缀的计算结果也为 31。

让我们一步步过一遍：我们的表达式是

5 4 - 3 10 * +

所以堆栈的进展如下：

5
5 4
1      # after evaluating -, i.e. popping 5 and 4 and pushing 5 - 4
1 3
1 3 10
1 30   # after evaluating *, i.e. popping 3 and 10 and pushing 3 * 10
31     # after evaluating +, i.e. popping 1 and 30 and pushing 1 + 30

Answer 2

在-和/的语句中，是4 5 -。那是-1，即4-5。

在较长的表达式中：5 4 - 3 10 * +

是 5 - 4，因为 5 在前。因此，它是 (5-4) + (3*10) = 31。

如果是 4 5 - 3 10 * + 那么计算结果将是 29（即 (4-5) + (3*10)）。这与前缀或后缀表示法无关，而是我们评估参数的顺序，因为 - 和 / 是不可交换的。赋值指定它们将按 "intuitive" 顺序进行评估，即 x y - 表示 x - y。

Answer 3

我认为您可能感到困惑，因为示例是 4-5 而您的示例是中缀表示法的 5-4。

求后缀5 4 - 3 10 * +:
5 4 - = 5 - 4 = 1
3 10 * = 3 * 10 = 30
1 30 + = 1 + 30 = 31

你作业中的第二个陈述只是澄清了如果你有类似 4 5 - 的东西，它将是 4 - 5 而不是 5 - 4。

Answer 4

当你评估后缀时，你使用一个堆栈：你压入操作数，当你到达一个运算符时，你弹出所需的操作数并压入评估结果。

对于像 + 这样的交换运算符，操作数的顺序并不重要。例如：

5 4 +

可以评价为

PUSH 5
PUSH 4
PUSH (POP + POP)

第一个 POP 将产生 4，第二个 POP 将产生 5。所以你真的评估了 4+5。

但在非交换运算符的情况下，这将不起作用。您必须评估 5 / 4，而不是 4 / 5。因此您需要使用临时变量：

 PUSH 5
 PUSH 4
 let d = POP; // divisor = 4
 let q = POP; // quotient = 5
 PUSH q/d;    // push the dividend

或者引入一个 SWAP 操作，交换栈顶的两项：

PUSH 5
PUSH 4
SWAP
PUSH (POP / POP)

否则编译后缀以便以相反的顺序推送:

PUSH 4
PUSH 5
PUSH (POP/POP)

非通勤运算符的中缀到后缀

infix to postfix with non-commuting operators

operators

infix-notation

postfix