expression-trees - 如何以前缀表示法计算表达式

Question

我正在尝试评估一个以前缀表示法表示表达式的列表。以下是此类列表的示例:

[+, [sin, 3], [- 10 5]]

评估列表值(value)的最佳方法是什么

Answer 1

如果您使用后缀而不是前缀会更简单。见 Reverse Polish Notation (RPN) .给定 RPN 中的表达式，只需使用一个堆栈就可以很容易地对其进行评估。

但是由于您要求一种无需递归和使用堆栈来评估前缀表达式的方法(对于可能更简单的方法，请参阅下面的编辑:下面)，这是一种方法:

我们可以使用两个堆栈来做到这一点。

一个堆栈(称为求值)保存运算符(如 +、sin 等)和操作数(如 3,4 等)，另一个堆栈(称为 Count)保存剩余操作数的数量 + 数量的元组操作符期望的操作数。

每当您看到运算符时，都将运算符插入计算堆栈并将相应的元组插入计数堆栈。

任何时候看到一个操作数(如 3,5 等)，您都会检查 Count 堆栈的顶部元组并减少该元组中剩余的操作数数量。

如果剩下要查看的操作数变为零，则从 Count 堆栈中弹出元组。然后从计算堆栈中弹出所需的操作数数量(您知道这是因为元组的另一个值)，弹出运算符并执行操作以获得新值(或操作数)。

现在将新操作数推回到计算堆栈上。这个新的操作数压入使您再次查看 Count 堆栈的顶部，并且您会做我们刚刚做的相同的事情(减少看到的操作数，与零进行比较等)。

如果操作数计数未变为零，则继续输入中的下一个标记。

例如，假设您必须评估 + 3 + 4/20 4

堆栈看起来像(左侧是堆栈的顶部)

Count                  Evaluation                   Input
                                                   + 3 + 4 / 20 4

(2,2)                   +                            3 + 4 / 20 4

(2,1)                   3 +                            + 4 / 20 4

(2,2) (2,1)             + 3 +                            4 / 20 4

(2,1) (2,1)             4 + 3 +                            / 20 4

(2,2) (2,1) (2,1)       / 4 + 3 +                            20 4

(2,1) (2,1) (2,1)       20 / 4 + 3 +                            4

(2,0) (2,1) (2,1)       4 8 / 4 + 3 +                   

Since it has become zero, you pop off two operands, the operator / 
and evaluate and push back 5. You pop off (2,0) from the Count stack.

(2,1) (2,1)                5 4 + 3 +

Pushing back you decrement the current Count stack top.

(2,0) (2,1)               5 4 + 3 + 

Since it has become zero, you pop off 5,4 and + and evaluate and push back 9. 
Also pop off (2,0) from the count stack.

(2,0)                          9 3 + 

                               12

编辑:

一位 friend 提出了一种无需多个堆栈即可执行此操作的方法:

从最后开始，转到第一个操作符。右边的标记将是操作数。评估和重做。看起来比用两个堆栈来做要简单得多。我们可以使用双向链表来表示我们在处理过程中更改的输入。评估时，您删除节点，然后插入结果。或者你也许可以只使用一个堆栈。