队列的递归计算

Question

队列中有一些元素(例如/ - 4 2 + 4 5)。

这需要计算为(4-2)/(4+5)。有人能向我解释一下递归算法吗？

Answer 1

您尝试理解一个波兰符号，它是逻辑、算术和代数的一种符号形式。

添加数字4和5的表达式是用前缀/波兰符号编写的+ 4 5，而不是4 + 5。

减去数字4和2的表达式是用前缀/波兰符号表示的，它是写的- 4 2，而不是4 - 2。

然后，可以组合操作。op3 (op1 m1 n1) (op2 m2 n2)，可以解释为(m1 op1 n1) op3 (m2 op2 n2)，其中op1、op2、op3可以是+、-、*、/。

括号是可选的，前面的波兰符号可以写成op3 op1 m1 n1 op2 m2 n2。

理解它的最简单的方法是使用一棵树。树还将帮助您更好地理解用于计算此类符号的递归算法。在这样的树上，任何操作都将被视为一个节点，数字是叶子。

要评估表达式，需要：

• 解析表达式:它包括识别运算符和数字，并构建关联树。
• 访问创建的树以评估所有操作并生成最终结果。