表达式求值问题3.ppt

《表达式求值问题3.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、限于二元运算符的表达式定义:表达式::=(操作数)+(运算符)+(操作数)操作数::=简单变量

2、表达式简单变量::=标识符

3、无符号整数Exp=S1+OP+S2前缀表示法OP+S1+S2中缀表示法S1+OP+S2后缀表示法S1+S2+OP例4：表达式求值例如:Exp=ab+(cd/e)f前缀式:+abc/def中缀式:ab+cd/ef后缀式:abcde/f+表达式标识方法b-ca/*def*+后缀表达式求值先找运算符，再找操作数例如：abcde/f+abd/ec-d/e(c-d/e)

4、f从原表达式求得后缀式方法设立暂存运算符的栈;设表达式的结束符为“#”,予设运算符栈的栈底为“#”若当前字符是操作数，则直接发送给后缀式;(后缀与前缀式操作数的顺序是相同的)若当前运算符的优先数高于栈顶运算符，则进栈;否则，退出栈顶运算符发送给后缀式;“(”对它之前后的运算符起隔离作用，“)”为自左括弧开始的表达式的结束符。表达式求值的算法采用“算符优先法”，在表达式中,优先级的顺序是:（1）括号的优先级最高,对括号内的各种运算符有:先乘除、再加碱，同级运算从左至右。（2）先括号内，后括号外，多层括号，由内向外。任

5、何表达式都是由操作数、运算符和界符组成。操作数可以是常量、变量、常数运算符有算术运算符、关系运算符、逻辑运算符界符包括左右括号算式结束符。运算符和界符统称为“算符”。在算符集中，在每一个运算步，相邻的算符c1和c2之间的关系是如下三种情况（c1出现在c2之前）：c1c2,c1的优先级大于c27*(5-3)算符间优先级＋－＊/()＃＋－＊／（）＃>><<<>>>><<<>>>>>><<<>>>><>><<<<<=>>>>>><<<<<=c2c1为实现算

6、符优先算法，在这里用了两个工作栈。一个存放算符OPTR，另一个存放数据OPND。算法思想是：（1）首先置数据栈为空栈，表达式起始符“＃”为算符栈的栈底元素（2）自左向右扫描表达式，读到操作数进OPND栈，读到运算符，则和OPTR栈顶元素比较（栈顶元素为c1，读到的算符为c2);若c1c2,则将c1出栈，并在操作数栈取出两个元素a和b按c1做运算，运算结果进OPND.重复

7、直到表达式求值完毕。例如：表达式3*(7-2),求值过程如下表：步骤OPTR栈OPND栈输入字符主要操作1＃3*(7-2)#PUSH(OPND,’3’)2＃3*(7-2)#PUSH(OPTR,’*’)3＃＊3(7-2)#PUSH(OPTR,’(’)4＃＊（37-2)#PUSH(OPND,’7’)5＃＊（37-2)#PUSH(OPTR,’-’)6＃＊（-372)#PUSH(OPND,’2’)7＃＊（372)#operate(‘7’,’-’,’2’)8＃＊（35)#POP(OPTR)消去括号9＃＊15#operate(

8、‘3’,’*’,’5’)10＃15#PUSH(OPTR,’*’)为使两个算符比较方便,给算符设置优先级,如下表,其中c1为栈内元素,c2为栈外元素算符栈内优先级栈外优先级*/43+-21(05)50#-1-1算符比较算法charPrecede(charc1,charc2){intc_temp1,c_temp2;switch(c1){case‘*’:case‘/’:c_temp1=4;break;case‘+’:case‘-’:c_temp1=2;break;case‘(’:c_temp1=0;break;case‘

9、)’:c_temp1=5;break;case‘#’:c_temp1=-1;}switch(c2){case‘*’:case‘/’:c_temp2=3break;case‘+’:case‘-’:c_temp2=1;break;case‘(’:c_temp2=5;break;case‘)’:c_temp2=0;break;case‘#’:c_temp2=-1;}if(c_temp1c_temp

10、2)return(‘>‘);}switch(c1){case‘*’:case‘/’:c_temp1=4;break;case‘+’:case‘-’:c_temp1=2;break;case‘(’:c_temp1=0;break;case‘)’:c_temp1=5;break;case‘#’:c_temp1=-1;}intexpress(){Initstack