BLOG
Enjoy when you can, and endure when you must.
APR 27, 2014/数据结构
后缀表达式求值

对一个后缀表达式进行求值需要用到堆栈,它用于存放操作数并在计算时将其弹出。假设我们将一个正确的后缀表达式存放在一个字符串中,计算时,只需从左到右依次扫描该字符串并遵循以下步骤进行:

1. 如果当前元素是一个操作数,则将其值推入堆栈;

2. 如果当前元素是一个运算符:

a)将栈顶的头两个元素弹出;

b)将这两个元素与当前运算符做数学运算(注意弹出的第一个元素为右操作数,而第二个元素为左操作数);

c)将结果推入堆栈。

A B C + * D /

这里我们以这个后缀表达式为例演示求值过程。假设A、B、C、D的值分别如下:

A = 8  B = 2  C = 3  D = 4

下表展示了整个计算过程:

当前步骤 栈内元素示意 描述
ABC+*D/ 8 "8"入栈
ABC+*D/ 8  2 "2"入栈
ABC+*D/ 8  2  3 "3"入栈
ABC+*D/ 8 弹出栈内头两个操作数:y = 3和x = 2
  8 计算:z = x + y,即z = 2 + 3
  8 5 将计算结果"5"放入堆栈
ABC+*D/   弹出栈内头两个操作数:y = 5和x = 8
    计算:z = x * y,即z = 8 * 5
  40 将计算结果"40"放入堆栈
ABC+*D/‍‍‍‍‍‍‍ 40  4 "4"入栈
ABC+*D/   弹出栈内头两个操作数:y = 4和x = 40
    计算:z = x / y,即z = 40 * 4
  10 将计算结果"10"放入堆栈

最终,栈中留下的元素即为计算的结果。

COMMENTS
LEAVE COMMNT