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

表达式求值 中缀：A+B*(C-D)-E/F 优先级高的运算符先计算； 优先级相同的自左向右计算； 先括号内，后括号外； 后缀：ABCD-*+EF/ 运算符没有优先级，运算次序自左向右； 运算符的两个运算数是其之前的最后两个； 中缀和后缀的表达式 附设运算数栈； 依次读入表达式的每一“项”， 若是数，则将其压栈 若是符，则： 连续从栈中退出两个操作数b和a 计算a 当前符 b 并将计算结果压栈 当表达式处理结束时，栈顶（唯一元素）是计算结果。 后缀表达式的求值 def suffix_evaluator(exp): operators = +-*/ st = SStack() # 存已读入的运算数 for x in exp: if not x in operators: st.push(float(x)) else: b = st.pop() a = st.pop() c = calculate(a, x, b) # 子表达式“归约” st.push(c) return st.top() 后缀表达式求值算法 计算时机：读入新的运算符时，若其优先级比前面最后读入的运算符的优先级低时，则前一个运算符可与当前已读入的最后的两个运算数计算； 两处“最后读入的先处理”（LIFO），故附设两个栈： 运算数栈 运算符栈 中缀表达式的求值 优先级表：C版课本P53。 表示： # y是栈顶符， x是当前读入符 def precede(y, x): if y==‘+’ x==‘+’: # 栈顶的’+’优先级更高！ return 1 elif y==‘+’ x==‘-’: return 1 elif y==‘+’ x==‘*’: return -1 …… 优先级的处理方式1 before：入栈前的优先数 after：入栈后的优先数 优先级的处理方式2 操作符 # ( +- * / ^ ) before 0 8 2 4 6 1 after 0 1 3 5 7 不入栈 用两个字典对象 表示！ 附设运算数栈和运算符栈； 依次读入表达式的每一“项”， 若是数，则将其压入运算数栈； 若是符，考察最后一个符与当前符的优先级： ： 继续读入； ： 连续从栈中退出两个操作数b和a； 计算a当前符b； 并将计算结果压入运算数栈； 继续考察； ==： 此时是左右括号碰头，直接弹出左括号；继续读入 当遇到表达式结束符’#’并且运算符的栈顶也为‘#’时，运算数的栈顶（栈底）是计算结果。 【注】：为方便处理，在表达式末尾添加结束符“#” 中缀表达式求值算法 def inffix_evaluator(tokens): operators = “()+-*/“ st_opnd = SStack() # 存已读入的运算数 st_optr = SStack() # 存已读入的运算符 st_optr.push(‘#’) # 总有一个优先级最低的垫底 i = 0; x = tokens[i] while st_optr.top() !=‘#’ x!=‘#’: if x not in operators: str_opnd.push(x) i += 1; x = tokens[i] else: 运算符的处理 return st_opnd.top() 中缀表达式求值算法 y = st_optr.top() if after[y] before[x]: # 方式1：precede(y, x) == 1 st_optr.push(x) i += 1; x = tokens[i] elif after[y] before[x]: y = st_optr.pop() b = st_opnd.pop() a = st_opnd.pop() c = calculate(a, y, b) # 继续处理x，而不是读入新的x else: st_optr.pop() # 此时是左右括号碰头，弹出左括号 i += 1; x = tokens[i] 运算符的处理 后缀表达式操作数的排列次序同中缀表达式 故不需附设栈存运算数，遇数则直接输出； 运算符的输出时机同中缀表达式的计算时机； 附设栈保存以读入但未处理的运算符； 输出时机：当前符的优先级低于符栈栈