3.2栈的应用举例-表达式求值 3.2栈的应用举例-表达式求值 OpndType EvaluatePostExpr(OKII氧设表达文是合法的 ·输入：后领表达式申（逆波兰式） InitStack(OPND);c=getchar(); 输出：表达式值 while (cl#) if (!IsOP(c))Push(OPND,c); 。例：ab+c*dea-* else( 。退到进算时桌时，由于算将在后，故前存该进算对康 Pop(OPND,b);Pop(OPND,a); 逼到算符时，立即计算 Push(OPND,doop(a,c,b)); 。前存的运算时章个数不园定，营要引入款据站构保存 。上侧中：在进行第一个运算前，嚼督存和，b c=getchar(); 。数据结构的操作特点：后选先出~蝇作数技 。不需要比校算将的优先银塘合性 result GetTop(OPND);DestroyStack(OPND); 退到算符时，直接从操作数找中弹出所需的操作数进行计 return result; 算：计算后再将计算帅录入栽 19/50 回 2D/50 图 3.2栈的应用举例-表达式转换 栈的概念运用 。表达式的不同表示之间的相互转换 ■问题1：习题桌3.6P23 。逆波兰式)波兰式 。轴入序列：123…H ,如：ab+c*dea-*.-*+abc*d-ea ■轴出序列P1P2户3…P ·共同点 ,证明，不存在i<j<k使得P,<P<P 。运算对津的次序一票 ·证（反证法）：假设存在<<k,使，<P,< ,不需要指号区分优光最和纳合性 ?<k”n最先出找，P最后出找 ·某算符在所有算特中的女序决定丁它的计算欲序 由鞭设如即，是三个敢中最大的 ,转换的思想 :入提序列是按值道增的 a。黄材保线为病保年健 :若某个值大的先出找。花中还有比它小的值，这些值将按值道常 。逆波兰式)中鞭表达式 的次序依次输出 即即先出，P和部比，小，录后着出，P的值应该是最小的 ,如：ab+c*dea-*.→(a+b)*c-d*(e-a) 图 这与服设相矛看。 21/50 22/50 图 3.3栈与递归的实现 3.3栈与递归的实现 ,递归的定义 递归 递推 ·递归(recursion):直接或间接地调用自身， 。递归的规则 int fact1(int n) int fact2(int n) 开始 。递归终止条件 if(n<0)return-1; 如：nl=(n-11*n if(n<0)return-1; else if(n==0)return 1; fact=1;i=1; 01=1 return n*fact1(n-1); ile(i<=n) ·递推：从已知的初始条件出 r 发，恶次递推出最后要求的值，结 fact *=;++ 如：01=1,1=0I*1=1 2 2!=11*2=2 23/50 可图 24/50 图 44 19/50 3.2 栈的应用举例-表达式求值 OpndType EvaluatePostExpr(){ //假设表达式是合法的 InitStack(OPND); c=getchar(); while (c!=‘#’) { if ( !IsOP(c) ) Push(OPND, c) ; else{ Pop(OPND, b); Pop(OPND, a); Push(OPND, doOp(a,c,b)); } c=getchar(); } result = GetTop(OPND); DestroyStack(OPND); return result; } 20/50 3.2 栈的应用举例-表达式求值 „ 输入：后缀表达式串(逆波兰式) 输出：表达式值 „ 例： ab+c*dea-*- „ 遇到运算对象时，由于算符在后，故暂存该运算对象 „ 遇到算符时，立即计算 „ 暂存的运算对象个数不固定，需要引入数据结构保存 „ 上例中：在进行第一个运算前，需暂存a,b „ 数据结构的操作特点：后进先出-Æ操作数栈 „ 不需要比较算符的优先级和结合性 „ 遇到算符时，直接从操作数栈中弹出所需的操作数进行计 算；计算后再将计算结果入栈 21/50 3.2 栈的应用举例-表达式转换 „ 表达式的不同表示之间的相互转换 „ 逆波兰式Æ波兰式 „ 如： ab+c*dea-*- Æ -*+abc*d-ea „ 共同点 „ 运算对象的次序一致 „ 不需要括号区分优先级和结合性 „ 某算符在所有算符中的次序决定了它的计算次序 „ 转换的思想 „ 参照逆波兰式的计算过程，将计算转换为待计算的算符和运 算对象的串的拼接 „ 逆波兰式Æ中缀表达式 „ 如： ab+c*dea-*- Æ (a+b)*c-d*(e-a) 22/50 栈的概念运用 „ 问题1：习题集3.6 P23 „ 输入序列：1 2 3 … n „ 输出序列：p1 p2 p3 … pn „ 证明：不存在i<j<k, 使得pj < pk < pi „ 证(反证法)：假设存在i<j<k, 使pj < pk < pi ∵ i<j<k ∴ pi 最先出栈，pk最后出栈 由假设知pi 是三个数中最大的 ∵入栈序列是按值递增的 ∴若某个值大的先出栈，栈中还有比它小的值，这些值将按值递减 的次序依次输出 即pi 先输出，pj 和pk都比pi 小，pk最后输出，pk的值应该是最小的 这与假设相矛盾。 23/50 3.3 栈与递归的实现 „ 递归的定义 „ 递归(recursion)：直接或间接地调用自身. „ 递归的规则 „ 递归终止条件 如: n! = (n-1)! *n 0! = 1 „ 递推：从已知的初始条件出 发，逐次递推出最后要求的值。 如：0!=1, 1!= 0!*1 = 1 2! = 1! *2 = 2 …… 24/50 3.3 栈与递归的实现 递归 int fact1(int n) { if (n<0) return -1; else if (n==0) return 1; return n*fact1(n-1); } 递推 int fact2(int n) { if (n<0) return -1; fact=1; i=1; while (i<=n) { fact *= i; i++; } }