是否可以表示所有 RPN 表达式，使得所有运算符都出现在左侧，所有操作数都出现在右侧？
我已经说服自己他们做不到。
举例：
4 4 + 4 /
堆叠：4 堆栈： 4 4 4 + 4 = 8 堆栈：8 堆栈：8 4 8 / 4 = 2 stack: 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 stack: 5
如果您有能力交换堆栈上的项目，那么是的，这是可能的，否则，不行。
想法？
I've convinced myself that they can't.
Take for example:
4 4 + 4 /
stack: 4
stack: 4 4
4 + 4 = 8
stack: 8
stack: 8 4
8 / 4 = 2
stack: 2
There are two ways that you could write the above expression with the
same operators and operands such that the operands all come first: "4
4 4 + /" and "4 4 4 / +", neither of which evaluate to 2.
"4 4 4 + /"
stack: 4
stack: 4 4
stack: 4 4 4
4 + 4 = 8
stack: 4 8
4 / 8 = 0.5
stack: 0.5
"4 4 4 / +"
stack: 4
stack: 4 4
stack: 4 4 4
4 / 4 = 1
stack: 4 1
4 + 1 = 5
stack: 5
If you have the ability to swap items on the stack then yes, it's possible, otherwise, no.
Thoughts?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
考虑代数表达式：
RPN 的明显翻译是：
即使有可用的交换操作，我认为也没有办法收集右侧的所有运算符：
其中 S 是 c 和 d 的总和。 此时，您无法使用单个交换操作来为 + 操作同时获取 a 和 b。 相反，您需要更复杂的堆栈操作（例如滚动）才能将 a 和 b 放在正确的位置。 我也不知道滚动操作是否足以满足所有情况。
Consider the algebraic expression:
The obvious translation to RPN would be:
Even with a swap operation available, I don't think there is a way to collect all the operators on the right:
where S is the sum of c and d. At this point, you couldn't use a single swap operation to get both a and b in place for a + operation. Instead, you would need a more sophisticated stack operation (such as roll) to get a and b in the right spot. I don't know whether a roll operation would be sufficient for all cases, either.
实际上，您不仅给出了答案，而且通过检查足以反驳标题中隐含的假设的反例，给出了结论性的证明。
Actually, you've not only given the answer but a conclusive proof as well, by examining a counter-example which is enough to disprove the assumption implied in the title.
我知道这是一个非常古老的线程，但我今天才发现它并想说我相信原始问题的答案是肯定的。 我相信所有 RPN 表达式都可以表示为所有运算符都出现在左侧，所有操作数都出现在右侧，如果除了正常的算术运算之外，我们还可以在表示中包含三个额外的“导航”运算符。
任何算术表达式都可以表示为二叉树，变量和常量位于叶节点，二元算术运算位于树的分叉处，一元运算例如沿任何分支的求反、倒数或平方根。 我建议的三个附加操作代表构建左分支、构建右分支或到达二叉树中的叶节点。 现在，如果我们根据树中各自叶子的位置将所有操作数放置在输入字符串的左侧，则可以为输入字符串的其余部分提供操作，告诉如何在内存中重建适当的二叉树并插入在正确的点将操作数和数学运算放入其中。 最后应用深度优先树遍历算法来计算结果。
我不知道这是否有任何实际应用。 作为编码和解码表达式的方式可能效率太低。 但作为一项学术练习，我相信它是可行的。
I know this is a very old thread, but I just found it today and wanted to say that I believe the answer to the original question is YES. I am confident all RPN expressions can be represented such that all operators appear on the left and all operands appear on the right, if in addition to the normal arithmetic operations, we are allowed to include three additional 'navigational' operators in the representation.
Any arithmetic expression can be represented as a binary tree, with variables and constants at the leaf nodes, binary arithmetic operations at the forks in the tree, and unary operations such as negation, reciprocal, or square root along any branches. The three additional operations I suggest represent building a left branch, building a right branch, or reaching a leaf node in a binary tree. Now if we place all the operands to the left of the input string according to the position of their respective leaves in the tree, we can supply the remainder of the input string with operations telling how to reconstruct the appropriate binary tree in memory and insert the operands and mathematical operations into it at the correct points. Finally a depth-first tree-traversal algorithm is applied to calculate the result.
I don't know if this has any practical application. It's probably too inefficient as way to encode and decode expressions. But as an academic exercise, I am sure it is workable.
只要展示一个不能告诉你这个问题的答案就足够了。
如果无法重新排列堆栈内容，则无法重新排列表达式 (2+4)*(7+8)。
2 4 + 7 8 + *
无论您如何重新排序，您最终都会得到一些需要在继续之前求和的东西。
至少我相信是这样。
It is enough to show one that can't in order to tell you the answer to this.
If you can't reorder the stack contents, then the expression (2+4)*(7+8) can't be rearranged.
2 4 + 7 8 + *
No matter how you reorder this, you'll end up with something that needs to be summed before you go on.
At least I believe so.