3.25表达式求值 前缀表达式、中缀表达式、后缀表达式 波兰式、逆波兰式 算法3.4 void evaluate Expression( 使用两个栈OPIR运算符栈;OPND操作数栈 步骤: 1)首先置OPND空,OPTR栈底为#2 2)依次读入表达式中每个字符,若是操作数则进 OPND栈,若是运算符,则和OPTR的栈顶运算符 比较优先权后做相应操作,直至整个表达式求值 完毕(OPTR的栈顶和当前读入元素均为#2)。 pboustc. edu. cn 中国科学技术大学
ypb@ustc.edu.cn 11 中国科学技术大学 3.2.5表达式求值 – 前缀表达式、中缀表达式、后缀表达式 – 波兰式、逆波兰式 – 算法3.4 void evaluateExpression() 使用两个栈:OPTR,运算符栈；OPND操作数栈 步骤： 1）首先置OPND空，OPTR栈底为’#’; 2）依次读入表达式中每个字符，若是操作数则进 OPND栈，若是运算符，则和OPTR的栈顶运算符 比较优先权后做相应操作，直至整个表达式求值 完毕（OPTR的栈顶和当前读入元素均为’#’）
01表示栈内,02表示当前运算符 ·运算符优先级相等时取“ “(-)3“#”-“#,特殊处理,后者比较不会出现 表3.1算符间的优先关系 2 # pboustc. edu. cn 12 中国科学技术大学
ypb@ustc.edu.cn 12 中国科学技术大学 • θ1表示栈内， θ2表示当前运算符 • 运算符优先级相等时取 “>” • “(“=“)” “#”=“#“，特殊处理，后者比较不会出现
例计算2+4-3*6# 699“9 99∠“6÷99 < # 操作数运算符 操作数运算符操作数运算符 “”>“# 699~“6453 # -12 操作数运算符 操作数运算符 pboustc. edu. cn 13 中国科学技术大学
ypb@ustc.edu.cn 13 中国科学技术大学 例 计算 2+4-3*6# 操作数 运算符 6 # 18 操作数 运算符 -12 “+” > “ –” “–” < “*” 操作数 运算符 2 4 + # 操作数 运算符 6 - # 操作数 运算符 6 3 - 6 * # - “*” > “#” “–” > “#” #
③原表达式转化为后缓表达式规则* 1)设立运算符栈 Po幻灯片放 2)设表达式的结束符为“#预设栈底为“#” 3)若当前字符是操作数,直接发送后缀表达式 4)若当前字符是运算符,且优先级大于栈顶运算符 则入栈,否则退出栈顶运算符发送给后缀表达式。 5若当前字符是结束符“#,则自栈顶至栈底依次将 栈中所有运算符发送给后缀表达式。 6)若当前运算符是“(”,进栈,对其之前底运算符起隔 离作用。 7)若当前运算符是“)”,可视为自相应的“(开始的表 达式的结束,从栈顶起依次退出栈顶运算符发送给 后缀表达式,直至栈顶相应运算符为“(,再将“ 也出栈 pboustc. edu. cn 14 中国科学技术大学
ypb@ustc.edu.cn 14 中国科学技术大学 1)设立运算符栈 2)设表达式的结束符为“#”预设栈底为“#” 3)若当前字符是操作数，直接发送后缀表达式 4)若当前字符是运算符，且优先级大于栈顶运算符， 则入栈，否则退出栈顶运算符发送给后缀表达式。 5)若当前字符是结束符“#”，则自栈顶至栈底依次将 栈中所有运算符发送给后缀表达式。 6)若当前运算符是“(”，进栈，对其之前底运算符起隔 离作用。 7)若当前运算符是“)”，可视为自相应的“(”开始的表 达式的结束，从栈顶起依次退出栈顶运算符发送给 后缀表达式，直至栈顶相应运算符为“(”，再将“(” 也出栈 原表达式转化为后缀表达式规则*