栈的应用.ppt

——用栈求算术表达式的值一些概念算术表达式:由操作数、算术运算符和括号组成的有意义的式子。二目运算符:对于运算符,参加运算的操作数必须有两个。中缀表达式:在算术表达式中,二目运算符位于参与运算的两个操作数中间。如:a+b*c-d/e*f(a+b)*c-d/(e*f)a+b*(c-d/(e*f))——用栈求算术表达式的值中缀表达式规定:(1)括号内的运算先执行。(2)运算符优先级由高(先执行)到低(后执行)为:^//乘方*/+-(3)相同优先级的运算符,——用栈求算术表达式的值后缀表达式:把运算符放在参与运算的操作数后面的算术表达式。如:abc*+de/f*-请比较a+b*c-d/e*fab+c*def*/-请比较(a+b)*c-d/(e*f)abcdef*/-*+请比较a+b*(c-d/(e*f))一旦遇运算符,即将紧靠它前面的两个操作数拿出来进行运算,结果作为操作数置于原来位置。优点:后缀表达式中操作数的顺序与中缀表达式中操作数的顺序相同,但它更为简单,不使用括号,不考虑运算符的优先级别,操作单纯。——(1)把中缀表达式转换成等价的后缀表达式(2)根据后缀表达式来求值这两步都需要应用栈来解决问题(1)把中缀表达式转换成等价的后缀表达式建一个存放操作符的栈,栈底元素存放字符“$”。扫描中缀表达式,若遇到操作数就将它直接输出到后缀表达式中;若遇到操作符,则将其压到栈中,等待时机输出。若要两个表达式等价,则后缀表达式要体现中缀表达式的运算优先次序。因此,要在操作符进栈和出栈的时机,比较运算符的优先级,并加以处理。(1)把中缀表达式转换成等价的后缀表达式定义运算符(含识别符)的优先级:字符栈中优先级进栈前的优先级^34*/22+-11(0——$-1——(1)把中缀表达式转换成等价的后缀表达式具体做法: 逐个字符扫描中缀表达式,按下列情况分别处理:(1)若为变量(操作数),则立即输出。(2)若为“(”,则将其压入栈中。(3)若为运算符,则将其优先级(进栈前)与栈顶字符的优先级进行比较。如果当前的运算符的优先级小于或等于栈顶字符的优先级,则栈顶字符出栈并输出。此过程持续到当前的运算符的优先级大于栈顶字符的优先级为止。然后将当前运算符进栈。(4)若为“)”,则从栈中依次退出运算符并输出,直到将“(”退出为止。“(”不输出。(5)若为“\0”,则从栈中依次退出所有运算符并输出,直到将“$”退出为止。“$”不输出。(1)把中缀表达式转换成等价的后缀表达式算法程序(-23)inticp(c)//返回进栈前运算符c的优先级intisp(c)//返回栈中字符c的优先级intmid_to_pos(mid_e,pos_e)//中缀表达式转换为后缀表达式课堂上讲解