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