|
|
|
知识路径： > 计算机科学基础 > 常用数据结构 > 队列、栈 > 栈 >
|
|
考试要求：掌握
相关知识点：5个
|
|
|
|
|
栈具有广泛的应用，例如，求表达式的值及递归到非递归等。
|
|
|
|
|
|
在源程序编译中，若要把一个含有表达式的赋值语句翻译成正确求值的机器语言，首先应正确地解释表达式。例如，对赋值语句X=4+8×2-3；，其正确的计算结果应该是17，但若在编译程序中简单地按自左向右扫描的原则进行计算，则为：X=12×2-3=24-3=21。这个结果显然是错误的。因此，为了使编译程序能够正确地求值，必须事先规定求值的顺序和规则。通常采用运算符优先法。
|
|
|
|
|
|
将一个递归算法转换为功能等价的非递归算法有很多方法，可以使用栈保存中间结果。其一般形式如下：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
其中，st[top][0]用于存放n值，st[top][1]用于存放n！值，在初始时，设置st[top][1]为0，表不n！尚未求出。
|
|
|
|
|
|
|
|
| |
|
|
|
