数据结构课件 第3章节 栈和队列.pptVIP

3.2.4 表达式求值问题 任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成。 其中 操作数：常数、标识符 运算符：算术运算符、关系运算符和逻辑运算符 基本界限符：左右括弧、表达式结束符等 以简单的二元运算符的算术表达式 二元表达式： 操作数1 （S1）操作符（OP）操作数2 （S2） 其中：操作数可以是简单变量，也可以是表达式； 而简单变量可以是标识符，也可以是无符号整数。 问题分析： 由于算术运算的规则是：先乘除后加减、先左后右和先括弧内后括弧外，不按其中运算符出现的先后次序。 那么怎么办？其中一个方法是先将它转换成另一种形式。 在计算机中，对这种二元表达式可以有三种不同的标识方法。 　　假设 Exp = S1 + OP + S2 则称 OP + S1 + S2 为表达式的前缀表示法（简称前缀式） 　称 S1 + OP + S2 为表达式的中缀表示法（简称中缀式） 　称 S1 + S2 + OP 为表达式的后缀表示法（简称后缀式） 例如： 　　若 ????????????????????????????　 则它的 　　前缀式为： ?????????????????????　　中缀式为： ?????????????????????　　后缀式为： ????????????????????? 综合比较它们之间的关系可得下列结论： 　1．三式中的 “操作数之间的相对次序相同”； 　2．三式中的 “运算符之间的的相对次序不同”； 　3．中缀式丢失了括弧信息，致使运算的次序不确定； 　4．前缀式的运算规则为：连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式； 　5．后缀式的运算规则为：　　·运算符在式中出现的顺序恰为表达式的运算顺序；　　·每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式； 　　以下就分如何按后缀式进行运算和如何将原表达式转换成后缀式两个问题进行讨论。 如何按后缀式进行运算？　　　　“先找运算符，后找操作数。” 如： 后缀式 参看动画flash3-3-5 运算过程为： 对后缀式从左向右“扫描”，遇见操作数则暂时保存，遇见运算符即可进行运算；此时参加运算的两个操作数应该是在它之前刚刚碰到的两个操作数，并且先出现的是第一操作数，后出现的是第二操作数。 由此可见，在运算过程中保存操作数的结构应该是个栈。 如何由原表达式转换成后缀式？　 先分析一下原表达式和后缀式两者中运算符出现的次序有什么不同。 ???? 例一　　原表达式： ?????????????????????　　　后缀式： ????????????????????? ???? 例二　　原表达式： ????????????????????　　　后缀式： ????????????????????? 先分析一下原表达式和后缀式两者中运算符出现的次序有什么不同。 ???? 例一　　原表达式： ?????????????????????　　　后缀式： ????????????????????? ???? 例二　　原表达式： ????????????????????　　　后缀式： ????????????????????? 给每个运算符赋以一个优先数的值，如下所列：　　　运算符 ?????????????????????　　　优先数　 ??????????????????? 优先数高的优先于优先数低的进行运算 　　显然，保存运算符的结构应该是个栈，从栈底到栈顶的运算符的优先数是从低到高的，因此它们运算的先后应是从栈顶到栈底的。 因此，从原表达式求得后缀式的规则为： 　　1) 设立运算符栈； 　　2) 设表达式的结束符为“#”，为栈底； 　　3) 若当前字符是操作数，则直接发送给后缀式； 　　4) 若当前字符为运算符且优先数大于栈顶运算符，则进栈，否则退出栈顶运算符发送给后缀式； 　　5) 若当前字符是结束符，则自栈顶至栈底依次将栈中所有运算符发送给后缀式； 　　6) “(”对它之前后的运算符起隔离作用，则若当前运算符为“(”时进栈； 　　7) )可视为自相应左括弧开始的表达式的结束符，则从栈顶起，依次退出栈顶运算符发送给后缀式直至栈顶字符为(止。 算法3.2　　void transform (char suffix[], char exp