2008-09-02 56 views
1

我相信自己不能。是否所有的RPN表达式都可以表示为所有的操作符出现在左侧,而所有的操作数出现在右侧?

采取例如:

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

如果你有能力在栈上交换物品,那么是的,这是可能的,否则,不。

想法?

回答

2

考虑代数表达式:

(a + b) * (c + d) 

明显的翻译RPN是:

a b + c d + * 

即使交换操作可用,我不认为有一种方式来收集所有右侧的运营商:

a b c d + 
a b S 

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

0

这是足以显示一个不能为了告诉你这个答案。

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

2 4 + 7 + 8 *

不管你怎么这个重新排序,你会的东西需要被概括你走之前结束。

至少我是这么认为的。

1

实际上,您不仅仅通过一个反例来证明标题中暗示的假设,而且还提供了一个确凿的证据。

1

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

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

我不知道这是否有任何实际应用。对表达式进行编码和解码可能效率太低。但作为学术演习,我相信这是可行的。

相关问题