栈的应用 后缀表达式求值 中缀表达的算术表达式的计算次序 中缀表达式: ∠=【 (1)先执行括号内的计算,后执行括号外 运算符在中间 的计算。在具有多层括号时,按层次反 需要括号改变优先级 复地脱括号,左右括号必须配对 率□ 十、 (2)在无括号或同层括号时,先乘(*) 4*x*(2*x+a)-c 除(/),后作加(+)、减(-)。 后缀表达式 (3)在同一个层次,若有多个乘除(* ■运算符在后面 /)或加减(+,-)的运算,那就按自左 完全不需要括号 至右顺序执行 2x*a+*c一 张帖写 大血张體 新有食究 中缀转后缀表达式值示例 中缀转后缀算法 当输入的是操作数时,直接输出到后缀 4*x*C2*x+a)一C 2x*a+*c (2)当输入的是开括号时,也把它压栈。 (3)当输入的是闭括号时,先 ■运算符可以作为中缀输入的自然分割 输出的后缀表达式,可以采用空格分割 cin按照变量指定的格式输入 CK bacK 真太张铭写 权新有,轨些究 北盒大管血歌张写 新究 后缀表达式求值 (4)当输入的是运算符时 ■循环:依次顺序读用户键入的符号序 算符的 列,组成并判别语法成分的类别 将栈顶元素弹出,放到后缀表达式序列中; 1.当遇到的是一个操作数,则压入栈顶; (b)把输入的运算符压校 2当通到的是一个运算符,就从栈中两次取 (5)最 出栈顶,按照运算符对这两个操作数进行计 算。然后将计算结果压入栈顶 如此继续,直到遇到符号=,这时栈顶 的值就是输入表达式的值。 back 真大带酱张储 新有,种究 北大管息歌张帖习 1010 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 55 back next 栈的应用 ——后缀表达式求值 „ 中缀表达式： „ 运算符在中间 „ 需要括号改变优先级 „ 4* x * (2 * x + a) – c „ 后缀表达式 „ 运算符在后面 „ 完全不需要括号 „ 4 x * 2 x * a + * c – - * * + * c 4 x a 2 x 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 56 back next 中缀表达的算术表达式的计算次序 „ (1)先执行括号内的计算，后执行括号外 的计算。在具有多层括号时，按层次反 复地脱括号，左右括号必须配对。 „ (2)在无括号或同层括号时，先乘(*) 、 除(／)，后作加(+)、减(-)。 „ (3)在同一个层次，若有多个乘除（*、 ／）或加减 (+，-)的运算，那就按自左 至右顺序执行。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 57 back next 中缀转后缀表达式值示例 „ 4 * x * (2 * x + a) – c „ 4 x * 2 x * a + * c – „ 运算符可以作为中缀输入的自然分割 „ 输出的后缀表达式，可以采用空格分割 „ cin按照变量指定的格式输入 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 58 back next 中缀转后缀算法 „ （1）当输入的是操作数时，直接输出到后缀 表达式序列。 „ （2）当输入的是开括号时，也把它压栈。 „ （3）当输入的是闭括号时，先判断栈是否为 空，若为空（括号不匹配），应该当错误异常 处理，清栈退出。若非空，则把栈中的元素依 次弹出，直到遇到第一个开括号为止，将弹出 的元素输出到后缀表达式的序列中（弹出的开 括号不放到序列中），若没有遇到开括号，说 明括号也不匹配，做异常处理，清栈退出。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 59 back next „ （4）当输入的是运算符时 „ （a) 循环，当（栈非空 and 栈顶不是开括 号 and 栈顶运算符的优先级不低于输入的运算符的 优先级）时，反复操作 将栈顶元素弹出，放到后缀表达式序列中； „ （b）把输入的运算符压栈。 „ （5）最后，当中缀表达式的符号序列全部读 入时，若栈内仍有元素，把它们全部依次弹 出，都放到后缀表达式序列尾部。若弹出的元 素遇到开括号时，则说明括号不匹配，做错误 异常处理，清栈退出。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 60 back next 后缀表达式求值 „ 循环：依次顺序读用户键入的符号序 列，组成并判别语法成分的类别 „ 1.当遇到的是一个操作数，则压入栈顶； „ 2.当遇到的是一个运算符, 就从栈中两次取 出栈顶，按照运算符对这两个操作数进行计 算。然后将计算结果压入栈顶。 „ 如此继续，直到遇到符号＝, 这时栈顶 的值就是输入表达式的值