03 第3章 栈和队列.pptVIP

　　2、中缀表达式变成等价的后缀表达式 　　将中缀表达式变成等价的后缀表达式，表达式中操作数次序不变，运算符次序发生变化，同时去掉了圆括号。转换规则是：设立一个栈，存放运算符，首先栈为空，编译程序从左到右扫描中缀表达式，若遇到操作数，直接输出，并输出一个空格作为两个操作数的分隔符；若遇到运算符，则必须与栈顶比较，运算符级别比栈顶级别高则进栈，否则退出栈顶元素并输出，然后输出一个空格作分隔符；若遇到左括号，进栈；若遇到右括号，则一直退栈输出，直到退到左括号止。当栈变成空时，输出的结果即为后缀表达式。 　　将中缀表达式(1+2)*((8-2)/(7-4))变成等价的后缀表达式。 　　现在用栈来实现该运算，栈的变化及输出结果如下 步骤 栈中元素 输出结果 说明 1 ( ? （进栈 2 ( 1 输出1 3 ( + 1 +进栈 4 ( + 1 2 输出2 5 ? 1 2 + +退栈输出，退栈到（止 6 * 1 2 + *进栈 7 * ( 1 2 + （进栈 8 * ( ( 1 2 + （进栈 9 * ( ( 1 2 + 8 输出8 10 * ( ( - 1 2 + 8 - 进栈 11 * ( ( - 1 2 + 8 2 输出2 12 * ( 1 2 + 8 2 - -退栈输出，退栈到（止 13 * ( / 1 2 + 8 2 - / 进栈 14 * ( / ( 1 2 + 8 2 - （ 进栈 15 * ( / ( 1 2 + 8 2 - 7 输出7 16 * ( / ( - 1 2 + 8 2 - 7 - 进栈 17 * ( / ( - 1 2 + 8 2 - 7 4 输出4 18 * ( / 1 2 + 8 2 - 7 4 - -退栈输出，退栈到（止 19 * 1 2 + 8 2 - 7 4 - / /退栈输出，退栈到（止 20 ? 1 2 + 8 2 - 7 4 - / * *退栈并输出 步骤 栈中元素 输出结果 说明 　　3、后缀表达式的求值 (此处不做要求) 　　将中缀表达式转换成等价的后缀表达式后，求值时，不需要再考虑运算符的优先级，只需从左到右扫描一遍后缀表达式即可。具体求值步骤为：设置一个栈，开始时，栈为空，然后从左到右扫描后缀表达式，若遇操作数，则进栈；若遇运算符，则从栈中退出两个元素，先退出的放到运算符的右边，后退出的放到运算符左边，运算后的结果再进栈，直到后缀表达式扫描完毕。此时，栈中仅有一个元素，即为运算的结果。 　　例：求后缀表达式：1 2 + 8 2 - 7 4 - / *的值，栈的变化情如下： 步骤 栈中元素 说明 1 1 1进栈 2 1 2 2进栈 3 ? 遇+号退栈2和1 4 3 1+2=3的结果3进栈 5 3 8 8进栈 6 3 8 2 2进栈 7 3 遇-号退栈2和8 8 3 6 8-2=6的结果6进栈 9 3 6 7 7进栈 10 3 6 7 4 4进栈 步骤 栈中元素 说明 11 3 6 遇-号退栈4和7 12 3 6 3 7-4=3的结果3进栈 13 3 遇/号退栈3和6 14 3 2 6/3=2的结果2进栈 15 ? 遇*号退栈2和3 16 6 3*2=6进栈 17 6 扫描完毕，运算结束 　　从上可知，最后求得的后缀表达式之值为6，与用中缀表达式求得的结果一致，但后缀式求值要简单得多。 　　4、函数的嵌套调用 　　在函数嵌套调用中，一个函数的执行没有结束，又开始另一个函数的执行，因此必须用栈来保存函数中中断的地址，以便调用返回时能从断点继续往下执行。 　　例 设有一个主程序，它调用函数a，函数a又调用函数b，函数b又调用函数c，（见下页），其中r，s，t分别表示中断地址，我们可以用一个栈来描述调用情况（见下页）。 一般情况的示意图 　　主程序调用函数a，留下一个断点地址r进栈，然后主函数处于挂起状态，进入函数a中执行，函数a中再调用函数b，留下一个断点地址s进栈，然后函数a处于挂起状态，进入函数b中执行，函数b中调用函数c，留下一个断点地址t进栈，然后函数b处于挂起状态，进入函数c中执行，函数c执行完后，要返回断