数据结构课件C 版第三章.ppt

mayan 第三章 栈和队列 --循环队列的函数实现 //构造函数 template class T SeqQueueT::SeqQueue(int sz) : front(0), rear(0), maxSize(sz) { elements = new T[maxSize]; assert ( elements != NULL ); } * mayan 第三章 栈和队列 --栈的应用之表达式求值 通过后缀表示计算表达式值的过程： 顺序扫描表达式的每一项，如果该项是操作数，则将其入栈； 如果该项是操作符op，则连续从栈中退出两个操作数X和Y，形成运算指令XopY，并将计算结果重新压入栈中。 当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。 * mayan 第三章 栈和队列 --栈的应用之表达式求值 A B C D －×+ E F /－ 步 扫描项 项类型 动作 栈中内容 1 置空栈 空 2 A 操作数 进栈 A 3 B 操作数 进栈 AB 4 C 操作数 进栈 ABC 5 D 操作数 进栈 ABCD 6 － 操作符 D、C退栈，计算C－D，结果R1进栈 ABR1 7 × 操作符 R1、B退栈，计算B×R1，结果R2进栈 A R2 * mayan 第三章 栈和队列 --栈的应用之表达式求值 8 + 操作符 R2、A退栈，计算A +R2，结果R3进栈 R3 9 E 操作数 进栈 R3 EF 10 F 操作数 进栈 R3 EF 11 / 操作符 F 、 E 退栈，计算E/F，结果R4进栈 R3 R4 12 － 操作符 R3、R4退栈，计算R3－R4，结果R5进栈 R5 步 扫描项 项类型 动作 栈中内容 A B C D －×+ E F /－ * mayan 第三章 栈和队列 --栈的应用之表达式求值 中缀表示→转后缀表示 先对中缀表达式按运算优先次序加上括号； 再把操作符后移到右括号的后面并以就近移动为原则； 最后将所有括号消去。 例：中缀表示(A+B)*D-E/(F+A*D)+C，转换为后缀表示 ( ( ( ( A + B ) * D ) – ( E / ( F + ( A * D ) ) ) ) + C ) 后缀表示 A B + D * E F A D * + / - C + * mayan 第三章 栈和队列 --栈的应用之表达式求值 中缀表示→转前缀表示 先对中缀表达式按运算优先次序通统加上括号 再把操作符前移到左括号前并以就近移动为原则 最后将所有括号消去。 例：中缀表示 (A+B)*D-E/(F+A*D)+C，转换为前缀表示 ( ( ( ( A + B ) * D ) – ( E / ( F + ( A * D ) ) ) ) + C ) 前缀表示 + - * + A B D / E + F * A D C * mayan 第三章 栈和队列 --栈的应用之表达式求值 利用栈将中缀表示转换为后缀表示 使用栈可将表达式的中缀表示转换成它的前缀表示和后缀表示。 操作符优先级 为了实现这种转换，需要考虑各操作符的优先级。 优先级 操作符 1 单目－，！ 2 ×，／，% 3 ＋，－ 4 ，=，，= 5 ==，！= 6 7 || * mayan 第三章 栈和队列 --栈的应用之表达式求值 各个算术操作符的优先级 isp叫做栈内(in stack priority)优先数 icp叫做栈外(in coming priority)优先数。 操作符优先数相等的情况只出现在括号配对或栈底的“#”号与输入流最后的“#”号配对时。 操作符ch # ( ×,／,% ＋,－ ) isp 0 1 5 3 6 icp 0 6 4 2 1 * mayan 第三章 栈和队列 --栈的应用之表达式求值 中缀表达式转换为后缀表达式的算法 操作符栈初始化，将结束符‘#’进栈。然后读入中缀表达式字符流的首字符ch。 重复执行以下步骤，直到ch = ‘#’，同时栈顶的操作符也是‘#’，停止循环。 若ch是操作数直接输出，读入下一个字符ch。 若ch是操作符，判断ch的优先级icp和位于栈顶的操作符op的优先级isp： * mayan 第三章 栈和队列 --栈的应用之表达式求值 若 icp(ch) isp(op)，令ch进栈，读入下一个字符ch。 若 icp(ch) isp(op)，退栈并输出。 若 icp(ch) == isp(op)，退栈但不输出，若退出的是“(”号读入下一个字符ch。 算法结束，输出序列即为所需的后缀表达式。 * mayan 第三章 栈和队列 --栈的应用之表达式求值 例