大学 栈应用ppt课件

1、1.3.5 栈的运用一. 用栈求算术表达式的值二. 用栈处理迷宫问题1.3.5 栈的运用用栈求算术表达式的值一些概念 算术表达式：由操作数、算术运算符和括号组成的有意义的式子。 二目运算符：对于运算符，参与运算的操作数必需有两个。 中缀表达式：在算术表达式中，二目运算符位于参与运算的两个操作数中间。如： a+b*c-d/e*f (a+b)*c-d/(e*f) a+b*(c-d/(e*f)1.3.5 栈的运用用栈求算术表达式的值中缀表达式规定：中缀表达式规定：1括号内的运算先执行。括号内的运算先执行。2运算符优先级由高先执行到低后运算符优先级由高先执行到低后执行为：执行为： /乘方乘方 * /

2、+ -3一样优先级的运算符，普通从左到右依一样优先级的运算符，普通从左到右依次执行次执行1.3.5 栈的运用用栈求算术表达式的值 后缀表达式：把运算符放在参与运算的操作数后面的算术表达式。如： abc*+de/f*- 请比较 a+b*c-d/e*f ab+c*def*/- 请比较 (a+b)*c-d/(e*f) abcdef*/-*+ 请比较 a+b*(c-d/(e*f) 一旦遇运算符，即将紧靠它前面的两个操作数拿出来进展运算，结果作为操作数置于原来位置。 优点：后缀表达式中操作数的顺序与中缀表达式中操作数的顺序一样，但它更为简单，不运用括号，不思索运算符的优先级别，操作单纯。1.3.5 栈的

3、运用用栈求算术表达式的值2. 处理步骤1把中缀表达式转换成等价的后缀表达式2根据后缀表达式来求值这两步都需求运用栈来处理问题 1把中缀表达式转换成等价的后缀表达式 建一个存放操作符的栈，栈底元素存放字符“$。 扫描中缀表达式，假设遇到操作数就将它直接输出到后缀表达式中；假设遇到操作符，那么将其压到栈中，等待时机输出。 假设要两个表达式等价，那么后缀表达式要表达中缀表达式的运算优先次序。因此，要在操作符进栈和出栈的时机，比较运算符的优先级，并加以处置。1把中缀表达式转换成等价的后缀表达式定义运算符含识别符的优先级：字符栈中优先级进栈前的优先级34* /22+ - 11(0$-11把中缀表达式转换

4、成等价的后缀表达式详细做法：逐个字符扫描中缀表达式，按以下情况分别处置： 1假设为变量(操作数)，那么立刻输出。 2假设为“，那么将其压入栈中。 3假设为运算符，那么将其优先级进栈前与栈顶字符的优先级进展比较。假设当前的运算符的优先级小于或等于栈顶字符的优先级，那么栈顶字符出栈并输出。此过程继续到当前的运算符的优先级大于栈顶字符的优先级为止。然后将当前运算符进栈。 4假设为“，那么从栈中依次退出运算符并输出，直到将“退出为止。“不输出。 5假设为“0，那么从栈中依次退出一切运算符并输出，直到将“$退出为止。“$ 不输出。1把中缀表达式转换成等价的后缀表达式算法程序int icp(c) / 前往进栈前运算符c的优先级int isp(c) / 前往栈中字符c的优先级int mid_to_pos(mid_e, pos_e) / 中缀表达式转换为后缀表达式课堂上讲解2根据后缀表达式来求值 建一个栈用来存放后缀表达式中的操作数。 扫描后缀表达式，假设遇到操作数，那么将其压进栈；假设遇到运算符，那么从栈顶延续取出两个操作数进展运算，然后将结果压进栈中。如此继续，直到最后一个运算符执行终了，这时送入栈中的值就是结果。2根据后缀表达式来求值 为了程序简单，后缀表达式的操作数用一个小写英文字母表示。字母所表示的数值存放在数组v26中，即由数组元素v