3.2.5表达式求值前缀表达式、中缀表达式、后缀表达式一一波兰式、逆波兰式算法3.4void evaluateExpressionO使用两个栈：OPTR，运算符栈；OPND操作数栈步骤:1）首先置OPND空，OPTR栈底为#"：2）依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符，则和OPTR的栈顶运算符比较优先权后做相应操作，直至整个表达式求值完毕（OPTR的栈顶和当前读入元素均为'#’）。11中国科学技术大学ypb@ustc.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.1算符间的优先关系62+#/()*61+A>>V<><>AA>>>7x>/人>>>V(D>>><<<<#E12中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 12 中国科学技术大学 • θ1表示栈内， θ2表示当前运算符 • 运算符优先级相等时取 “>” • “(“=“)” “#”=“#“，特殊处理，后者比较不会出现
例计算2+4-3*6#<66*996699*6+334#2##66操作数操作数运算符操作数运算符运算符66＊99>“#"66-99 >栈顶和c均为“#”“#""循环结束18#6#-12操作数运算符操作数运算符13中国科学技术大学ypb@ustc.edu.cn
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)若当前运算符是")”，可视为自相应的“("开始的表达式的结束，从栈顶起依次退出栈顶运算符发送给后缀表达式，直至栈顶相应运算符为“("”，再将“("也出栈14中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 14 中国科学技术大学 1)设立运算符栈 2)设表达式的结束符为“#”预设栈底为“#” 3)若当前字符是操作数，直接发送后缀表达式 4)若当前字符是运算符，且优先级大于栈顶运算符， 则入栈，否则退出栈顶运算符发送给后缀表达式。 5)若当前字符是结束符“#”，则自栈顶至栈底依次将 栈中所有运算符发送给后缀表达式。 6)若当前运算符是“(”，进栈，对其之前底运算符起隔 离作用。 7)若当前运算符是“)”，可视为自相应的“(”开始的表 达式的结束，从栈顶起依次退出栈顶运算符发送给 后缀表达式，直至栈顶相应运算符为“(”，再将“(” 也出栈 原表达式转化为后缀表达式规则*
后缀表达式求值步骤1、读入表达式一个字符2、若是操作数，压入栈，转43、若是运算符，从栈中弹出2个数，将运算结果再压入栈4、若表达式输入完毕，栈顶即表达式值；若表达式未输入完，转1后缀表达式：435*+例计算4+3*5-toptoptop1-5toptop3315top71944415中国科学技术大学ypb@ustc.edu.cn
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