数据结构与算法(Python语言描述)课件表达式的求值.ppt

《数据结构与算法(Python语言描述)课件表达式的求值.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、表达式求值中缀：A+B*(C-D)-E/F优先级高的运算符先计算；优先级相同的自左向右计算；先括号内，后括号外；后缀：ABCD-*+EF/运算符没有优先级，运算次序自左向右；运算符的两个运算数是其之前的最后两个；中缀和后缀的表达式附设运算数栈；依次读入表达式的每一“项”，若是数，则将其压栈若是符，则：连续从栈中退出两个操作数b和a计算a<当前符>b并将计算结果压栈当表达式处理结束时，栈顶（唯一元素）是计算结果。后缀表达式的求值defsuffix_evaluator(exp):operators="+-*/"st=SStack(

2、)#存已读入的运算数forxinexp:ifnotxinoperators:st.push(float(x))else:b=st.pop()a=st.pop()c=calculate(a,x,b)#子表达式“归约”st.push(c)returnst.top()后缀表达式求值算法计算时机：读入新的运算符时，若其优先级比前面最后读入的运算符的优先级低时，则前一个运算符可与当前已读入的最后的两个运算数计算；两处“最后读入的先处理”（LIFO），故附设两个栈：运算数栈运算符栈中缀表达式的求值优先级表：C版课本P53。表示：#y是栈顶

3、符，x是当前读入符defprecede(y,x):ify==‘+’&&x==‘+’:#栈顶的’+’优先级更高！return1elify==‘+’&&x==‘-’:return1elify==‘+’&&x==‘*’:return-1……优先级的处理方式1before：入栈前的优先数after：入栈后的优先数优先级的处理方式2操作符#(+-*/^)before082461after01357不入栈用两个字典对象表示！附设运算数栈和运算符栈；依次读入表达式的每一“项”，若是数，则将其压入运算数栈；若是符，考察最后一个符与当前符的优先

4、级：<：继续读入；>：连续从栈中退出两个操作数b和a；计算a<当前符>b；并将计算结果压入运算数栈；继续考察；==：此时是左右括号碰头，直接弹出左括号；继续读入当遇到表达式结束符’#’并且运算符的栈顶也为‘#’时，运算数的栈顶（栈底）是计算结果。【注】：为方便处理，在表达式末尾添加结束符“#”中缀表达式求值算法definffix_evaluator(tokens):operators=“()+-*/“st_opnd=SStack()#存已读入的运算数st_optr=SStack()#存已读入的运算符st_optr.push(‘

5、#’)#总有一个优先级最低的垫底i=0;x=tokens[i]whilest_optr.top()!=‘#’&&x!=‘#’:ifxnotinoperators:str_opnd.push(x)i+=1;x=tokens[i]else:运算符的处理returnst_opnd.top()中缀表达式求值算法y=st_optr.top()ifafter[y]before[x]:y=st

6、_optr.pop()b=st_opnd.pop()a=st_opnd.pop()c=calculate(a,y,b)#继续处理x，而不是读入新的xelse:st_optr.pop()#此时是左右括号碰头，弹出左括号i+=1;x=tokens[i]运算符的处理后缀表达式操作数的排列次序同中缀表达式故不需附设栈存运算数，遇数则直接输出；运算符的输出时机同中缀表达式的计算时机；附设栈保存以读入但未处理的运算符；输出时机：当前符的优先级低于符栈栈顶运算符时，栈顶运算符可输出。中缀表达式转换为后缀表达式definffix_to_suf

7、fix(tokens):operators=“()+-*/“st_optr=SStack()#存已读入的运算符exp=[]st_optr.push(‘#’)#总有一个优先级最低的垫底i=0;x=tokens[i]whilest_optr.top()!=‘#’&&x!=‘#’:ifxnotinoperators:exp.append(x)i+=1;x=tokens[i]else:运算符的处理returnexp中缀表达式转换为后缀表达式算法伪码y=st_optr.top()ifafter[y]

8、cede(y,x)==1st_optr.push(x)i+=1;x=tokens[i]elifafter[y]>before[x]:y=st_optr.pop()#计算的时机即输出时机exp.append(y)#继续处理x，而不是读入新的xelse:st_optr.pop()