之战的应用(ct 4、栈的应用范例表达式 2)算术表达式求值(算符优先法) 表达式求值操作规则。从左向右扫描表达式串,每次去一个单 词 o如果单词是操作数,一律入操作数栈 e如果单词是运算符(称为外运算符),则比较该外运算符与运 算符栈栈顶运算符的优先级。 如果外运算符优先级高或相同,则将该运算符入栈; 否则将栈顶运算符出栈并出栈操作数计算结果入操作数栈。 注意:运算符栈一开始有个运算符(,它的优先级最低。 6表达式终结符一一分号的优先级最低,比栈内任何实际运算 符都低 当栈顶运算符与外运算符是不同运算符时,按照预先定义的 优先级处理,如果是相同的运算符,右结合性的运算符,外运 算符优先级高 ⑤为了能对圆括号作统一处理,特别规定左括号在栈内优先级 最低,在栈外优先级最高
栈之栈的应用(cont’d) 4、栈的应用范例(表达式) (2) 算术表达式求值(算符优先法) 表达式求值操作规则：从左向右扫描表达式串，每次去一个单 词， 如果单词是操作数，一律入操作数栈 如果单词是运算符(称为外运算符)，则比较该外运算符与运 算符栈栈顶运算符的优先级。 • 如果外运算符优先级高或相同，则将该运算符入栈； •否则将栈顶运算符出栈并出栈操作数计算结果入操作数栈。 注意：运算符栈一开始有个运算符(，它的优先级最低。 表达式终结符－－分号的优先级最低，比栈内任何实际运算 符都低。 当栈顶运算符与外运算符是不同运算符时，按照预先定义的 优先级处理，如果是相同的运算符，右结合性的运算符，外运 算符优先级高。 为了能对圆括号作统一处理，特别规定左括号在栈内优先级 最低，在栈外优先级最高
传之战的应用(c 4、找的应用范例表达式 (2)算术表达式求值(算符优先法) 为了方便栈内外运算符优先级比较,可以事先规 定运算符的栈内外的优先级数。可以根据下面的表格, 编写函数获取运算符的优先级数: 优先级函数 运算符x 栈内 栈外 isp(x) ielp(x) 单目运算符3 4 2 2 0 4
栈之栈的应用(cont’d) 4、栈的应用范例(表达式) (2) 算术表达式求值(算符优先法) 为了方便栈内外运算符优先级比较，可以事先规 定运算符的栈内外的优先级数。可以根据下面的表格， 编写函数获取运算符的优先级数： 优先级函数 运算符 x 栈内 isp(x) 栈外 ielp(x) ^ 单目运算符 3 4 * / 2 2 + - 1 1 ( 0 4
传之战的应用(c 4,我的应用范例舞的 float evaluate(charexplD /*实现开辟操作数栈S1和运算符栈s 中:cp是输入表达式串*将程序补充 while(1) 完整 从exp中取出一个单词x switch(x) case x是操作数:push(&s1,x); break; case x是y 反复出栈处理,直到遇到(为止. break case x是';反复出栈处理,直到栈只剩下(为止; return操作数栈顶值; case x是其它运算符: while(ielp(x)<=isp(s2. elem s2top-){出栈处理} push(&s2, x); break; //switch 3//while
float evaluate(char exp[]) { /*实现开辟操作数栈s1和运算符栈s2，并将(入到s2 中；exp是输入表达式串*/ while(1) {从exp中取出一个单词x switch(x) { case x是操作数:push(&s1,x);break; case x是')': 反复出栈处理,直到遇到(为止.break; case x是';':反复出栈处理，直到栈只剩下(为止； return 操作数栈顶值; case x是其它运算符: while(ielp(x)<=isp(s2.elem[s2.top--])){出栈处理} push(&s2,x);break; }//switch }//while } 栈之栈的应用(cont’d) 4、栈的应用范例(算符) (3) 算符优先法求值算法 将程序补充 完整！
传之战的应用(c 4,我的应用范例舞的 练习: 1、设有一个栈,元素进栈的次序A,B,C,D,E。 试问能否得到出栈序列: (1)C,E,A,B,D;(2)C,B,A,D,E (3)D,C,A,B,E;(4)A,C,B,E,D; (5)A,B,C,D,E;(6)E,A,B,C,D。 (1)否(2) SSSXSXS(3)否 (4)XSXXSSXXSS(5)XSXSXSXSXS(6)1 2、按照运算符优先数法,画出对下列算术表达式求值 时运算符栈和操作数栈的变化过程: A+B^C*E一D/F*G;
练习： 1、设有一个栈，元素进栈的次序:A，B，C，D，E。 试问能否得到出栈序列： （1）C，E，A，B，D；（2）C，B，A，D，E； （3）D，C，A，B，E；（4）A，C，B，E，D； （5）A，B，C，D，E；（6）E，A，B，C，D。 2、按照运算符优先数法，画出对下列算术表达式求值 时运算符栈和操作数栈的变化过程： A + B^C*E – D/F*G; 栈之栈的应用(cont’d) 4、栈的应用范例(算符) (3) 算符优先法求值算法
战的应(c 4、的应用范例递归算法 (4)实现速问题的 递归算法: int Ackerman(int n, int x, int y) fif(n==return x+1; lse if(y==0) Rif(n==lreturn x; else if(n==2)return 0 else if(n==3)return 1; lse return 2; 3 else return Ackerman(n-1, Ackerman(n, x, y-1), x);
栈之栈的应用(cont’d) 4、栈的应用范例(非递归算法) (4) 实现递归问题的非递归算法 − − = = = = = = = + = = ( 1, ( , , 1), ) 0, 0 2 4, 0 1 3, 0 0 2, 0 1, 0 1 0 ( , , ) A n A n x y x n y n y n y n y x n y x n A n x y 递归算法： int Ackerman(int n,int x,int y) { if(n==0) return x+1; else if(y==0) {if(n==1) return x; else if(n==2) return 0; else if(n==3) return 1; else return 2; } else return Ackerman(n-1,Ackerman(n,x,y-1),x); }