1

我已经说服自己他们做不到。

举个例子:

4 4 + 4 /

堆栈:4 堆栈:4 4 4 + 4 = 8 堆栈:8 堆栈:8 4 8 / 4 = 2 堆栈:2

有两种方法可以使用相同的运算符和操作数编写上述表达式,以使操作数都排在第一位:“4 4 4 + /”和“4 4 4 / +”,它们的计算结果都不为 2。

"4 4 4 + /" 堆栈:4 堆栈:4 4 堆栈:4 4 4 4 + 4 = 8 堆栈:4 8 4 / 8 = 0.5 堆栈:0.5

"4 4 4 / +" 堆栈:4 堆栈:4 4 堆栈:4 4 4 4 / 4 = 1 堆栈:4 1 4 + 1 = 5 堆栈:5

如果您有能力交换堆栈上的项目,那么是的,有可能,否则,没有。

想法?

4

4 回答 4

2

考虑代数表达式:

(a + b) * (c + d)

对 RPN 的明显翻译是:

a b + c d + *

即使有交换操作可用,我认为没有办法收集右边的所有运算符:

a b c d +
a b S

其中 S 是 c 和 d 的总和。此时,您不能使用单个交换操作来为 a + 操作同时获取 a 和 b。相反,您需要更复杂的堆栈操作(例如滚动)才能将 a 和 b 放在正确的位置。我也不知道滚动操作是否足以满足所有情况。

于 2008-09-02T09:08:08.793 回答
1

实际上,通过检查足以反驳标题中隐含假设的反例,您不仅给出了答案,而且还给出了确凿的证据。

于 2008-09-02T09:06:25.897 回答
1

我知道这是一个非常古老的线程,但我今天才发现它并想说我相信原始问题的答案是肯定的。我相信所有 RPN 表达式都可以表示为所有运算符出现在左侧,所有操作数出现在右侧,如果除了正常的算术运算之外,我们还可以在表示中包含三个额外的“导航”运算符。

任何算术表达式都可以表示为二叉树,在叶节点处具有变量和常量,在树的叉处具有二元算术运算,以及沿任何分支的一元运算,例如否定、倒数或平方根。我建议的三个附加操作代表构建左分支、构建右分支或到达二叉树中的叶节点。现在,如果我们根据它们各自叶子在树中的位置将所有操作数放在输入字符串的左侧,我们可以为输入字符串的其余部分提供操作,告诉如何在内存中重建适当的二叉树并插入在正确的点将操作数和数学运算放入其中。最后采用深度优先树遍历算法计算结果。

我不知道这是否有任何实际应用。作为编码和解码表达式的方式,它可能效率太低。但作为一项学术活动,我相信它是可行的。

于 2012-12-13T04:27:28.473 回答
0

展示一个不能告诉你答案的人就足够了。

如果不能重新排列堆栈内容,则表达式 (2+4)*(7+8) 不能重新排列。

2 4 + 7 8 + *

无论您如何重新排序,您最终都会得到一些需要在继续之前进行总结的内容。

至少我是这样相信的。

于 2008-09-02T09:05:53.183 回答