表达式求值.ppt.pptVIP

表达式求值 一个表达式由操作数(亦称运算对象)、操作符 (亦称运算符) 和分界符(亦称界限符)组成。 算术表达式有三种表示： 中缀(infix)表示 操作数 操作符 操作数，如 A+B； 前缀(prefix)表示 操作符 操作数 操作数，如 +AB； 后缀(postfix)表示 操作数 操作数 操作符，如 AB+； 表达式的中缀表示 a + b * ( c - d ) - e ^ f / g 表达式中相邻两个操作符的计算次序为： 优先级高的先计算; 优先级相同的自左向右计算; 当使用括号时从最内层括号开始计算。 C语言中操作符的优先级 优先级 操作符 1 单目-、！ 2 *、/、% 3 +、- 4 、=、、= 5 ==、!= 6 7 || 一般表达式的操作符有4种类型: 算术操作符 如双目操作符（+、-、*、/ 和%）以及单目操作符（-）; 关系操作符 包括、=、==、!=、=、。这些操作符主要用于比较; 逻辑操作符 如与()、或(||)、非(!); 括号‘(’和‘)’ 它们的作用是改变运算顺序; 应用后缀表示计算表达式的值 从左向右顺序地扫描表达式，并用一个栈暂存扫描到的操作数或计算结果; 在后缀表达式的计算顺序中已隐含了加括号的优先次序，括号在后缀表达式中不出现; 计算例 a b c d - * + e f ^ g / - 通过后缀表示计算表达式值的过程 顺序扫描表达式的每一项，根据它的类型做如下相应操作： 若该项是操作数，则将其压栈； 若该项是操作符op，则连续从栈中退出两个操作数Y和X，形成运算指令XopY，并将计算结果重新压栈。 当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。 利用栈将中缀表示转换为后缀表示 使用栈可将表达式的中缀表示转换成它的前缀表示和后缀表示。 为了实现这种转换，需要考虑各操作符的优先级。 各个算术操作符的优先级 isp叫做栈内(in stack priority)优先数。 icp叫做栈外(in coming priority)优先数。 操作符优先数相等的情况只出现在括号配对或栈底的“;”号与输入流最后的“;”号配对时。 中缀表达式转换为后缀表达式的算法 操作符栈初始化，将结束符‘;’进栈。然后读入中缀表达式字符流的首字符ch； 重复执行以下步骤，直到ch = ‘;’，同时栈顶的操作符也是‘;’，停止循环； 若ch是操作数直接输出，读入下一个字符ch。 若ch是操作符，判断ch的优先级icp和位于栈顶的操作符op的优先级isp： 若 icp (ch) isp (op)，令ch进栈，读入下一个字符ch； 若 icp (ch) isp (op)，退栈并输出； 若 icp (ch) == isp (op)，退栈但不输出，若退出的是“(”号读入下一个字符ch； 算法结束，输出序列即为所需的后缀表达式。 中缀算术表达式求值 使用两个栈，操作符栈OPTR (operator)，操作数栈OPND(operand)， 对中缀表达式求值的一般规则： (1) 建立并初始化OPTR栈和OPND栈，在OPTR栈中压入一个“#” (2) 从头扫描中缀表达式，取一字符送入ch (3) 当ch != “#” 时, 执行以下工作, 否则结束算法，此时在OPND栈的栈顶得到运算结果。 ① 若ch是操作数，进OPND栈，从中缀表达式取下一字符送入ch； ② 若ch是操作符，比较栈外icp(ch)的优先级和栈内isp(OPTR)的优先级： ? 若icp(ch) isp(OPTR)，则ch进OPTR栈，从中缀表达式取下一字符送入ch； ? 若icp(ch) isp(OPTR)，则从OPND栈退出a2和a1，从OPTR栈退出θ, 形成运算指令 (a1)θ(a2)，结果进OPND栈； ? 若icp(ch) == isp(OPTR) 且ch == “)”，则从OPTR栈退出栈顶的“(”，对消括号，然后从中缀表达式取下一字符送入ch； * rst1 rst2 rst3 rst4 rst5 rst6 rst1 rst2 rst3 rst4 rst5 rst6 *