如何评估前缀表示法中的表达式

Question

我试图评估一个表示前缀表示法中的表达式的列表.以下是此类列表的示例:

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

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

Answer 1

如果你使用postfix而不是前缀会更简单.请参阅反向波兰表示法(RPN).给定RPN中的表达式,使用一个堆栈很容易评估.

但是,既然你要求一种方法来评估前缀表达式而不使用递归和使用堆栈(对于一种可能更简单的方法,请参阅下面的编辑:),这是一种方法:

我们可以使用两个堆栈来完成此操作.

一个堆栈(称为Evaluation)保存运算符(如+,sin等)和操作数(如3,4等),另一个堆栈(称为Count)保存一个剩余可见操作数的元组+数字操作员期望的操作数.

无论何时看到操作员,都会将操作员推入评估堆栈并将相应的元组推送到Count堆栈.

无论何时你看到一个操作数(如3,5等),你都会检查Count堆栈的顶部元组并减少该元组中剩余的操作数.

如果剩下要看的操作数变为零,则从Count堆栈中弹出元组.然后从评估堆栈中弹出所需操作数的数量(由于元组的其他值,您知道这一点),弹出运算符并执行操作以获取新值(或操作数).

现在将新操作数推回到评估堆栈上.这个新的操作数push会让你再看看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

编辑:

一位朋友提出了一种没有多个堆栈的方法:

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

Answer 2

KISS,反向评估为后缀表达式.