对一个后缀表达式进行求值需要用到堆栈,它用于存放操作数并在计算时将其弹出。假设我们将一个正确的后缀表达式存放在一个字符串中,计算时,只需从左到右依次扫描该字符串并遵循以下步骤进行:
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"放入堆栈 |
最终,栈中留下的元素即为计算的结果。
NOTHING
Nice to meet you~your page is so beautiful~thanks for your share~