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

表达式求值中缀：A+B*(C-D)-E/F优先级高的运算符先计算；优先级相同的自左向右计算；先括号内，后括号外；后缀：ABCD-*+EF/运算符没有优先级，运算次序自左向右；运算符的两个运算数是其之前的最后两个；中缀和后缀的表达式附设运算数栈；依次读入表达式的每一“项”，若是数，则将其压栈若是符，则：•连续从栈中退出两个操作数b和a•计算a当前符b•并将计算结果压栈当表达式处理结束时，栈顶（唯一元素）是计算结果。后缀表达式的求值defsuffix_evaluator(exp):operators=+-*/st=SStack()#存已读入的运算数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是栈顶符，x是当前读入符defprecede(y,x):ify==‘+’&&x==‘+’:#栈顶的’+’优先级更高！return1elify==‘+’&&x==‘-’:return1elify==‘+’&&x==‘*’:return-1……优先级的处理方式1before：入栈前的优先数after：入栈后的优先数优先级的处理方式2操作符#(+-*/^)before082461after01357不入栈用两个字典对象表示！附设运算数栈和运算符栈；依次读入表达式的每一“项”，若是数，则将其压入运算数栈；若是符，考察最后一个符与当前符的优先级：：继续读入；：连续从栈中退出两个操作数b和a；计算a当前符b；并将计算结果压入运算数栈；继续考察；==：此时是左右括号碰头，直接弹出左括号；继续读入当遇到表达式结束符’#’并且运算符的栈顶也为‘#’时，运算数的栈顶（栈底）是计算结果。【注】：为方便处理，在表达式末尾添加结束符“#”中缀表达式求值算法definffix_evaluator(tokens):operators=“()+-*/“st_opnd=SStack()#存已读入的运算数st_optr=SStack()#存已读入的运算符st_optr.push(‘#’)#总有一个优先级最低的垫底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]:#方式1：precede(y,x)==1st_optr.push(x)i+=1;x=tokens[i]elifafter[y]before[x]:y=st_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_suffix(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]before[x]:#方式1：precede(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()#去左括号i+=1;x=tokens[i]运算符的处理