资源描述：
《C语言表达式求值.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、实验四算术表达式求值运算器一、实验目的帮助学生熟练掌握栈的基本操作，并通过用算符优先法对表达式求值的过程深刻领会用栈解决实际问题的基本方法。二、实验内容编写程序实现从键盘终端输入语法正确的算术表达式，计算出表达式的值。为了避免算符的二义性，可以假设表达式中只包含实型正常数运算符包括加、减、乘、除四种基本运算，可以包含圆括号。三、实验仪器微型计算机实验用编程语言：TurboC2.0，BorlandC3.0等以上版本四、实验原理1、算术四则运算法则：先乘除后加减从左至右先括号内后括号外2、方法：对运算符建立优先关系矩阵，按优先关系对表达式进行处理。算符：运算符和界符
2、。根据法则1：对于两个相邻运算符，乘除优先于加减。根据法则2：乘除优先级相同，加减优先级相同。相邻两个同级运算符左优先。根据法则3：“（”前面的运算符优先级低于“（”的优先级。“（”的优先级低于右边相邻算符。“）”左边的算符高于“）”的优先级。由于“（”和“）”必须成对出现，令它们的优先性相同。为了处理的方便，假设表达式以“＃”开始和结束，输入表达式的一般形式为：#表达式#如：#5.3+4.2*(7.6+4.5)#规定开始的“＃”的优先性低于所有其它算符，所有其它算符的优先性高于结束的“＃”。根据假设，表达式开始的“#”和结束的“#”必须成对出现，所以也令它们的
3、优先性相同。对于一个正确的表达式，“)”不可能与“（”相邻，“（”不可能与结束的“#”相邻，开始的“#”不可能与“）”相邻，它们之间没有优先性，程序应具有这种判断能力。根据上面的讨论，可用表1所示的算符优先关系矩阵来描述算符之间的优先关系，其中，用“>”表示表达式中前一个算符的优先性高于后一个算符的优先性，用“<”表示表达式中前一个算符的优先性低于后一个算符的优先性，用“=”表示表达式中前一个算符的优先性与后一个算符的优先性相同。若两个算符之间无优先性，用空白表示。表1：算符优先关系矩阵+-*/()#+>><<<>>->><<<>>*>>>><>>/>>>><<
4、>(<<<<<=)>>>>>>#<<<<<=3、算符表示为了使算符与优先关系矩阵的行列号对应，把表达式中可能有的算符放入一维数组中，可以用字符在一维数组中的下标作为字符的标识码。本计算中，算法表示如下：＋－*/()+0123456即用0表示算符“＋”，用1表示算符“－”，等。定义的字符数组为：chara[]={'+','-','*','/','(',')','#'};4、优先关系矩阵的表示大于关系用1表示小于关系用－1表示等于关系用0表示若两个算符间不存在关系，则用一个特定的数值表示，如用整数的上限值32767表示，可定义一个宏常量来表示：#defineNO32
5、767则其优先关系矩阵为：intPriorityTable[7][7]={{1,1,-1,-1,-1,1,1},{1,1,-1,-1,-1,1,1},{1,1,1,1,-1,1,1},{1,1,1,1,-1,1,1},{-1,-1,-1,-1,-1,0,NO},{1,1,1,1,NO,1,1},{-1,-1,-1,-1,-1,NO,0}};5、算术表达式求值算法的实现原理处理过程：设置两个栈：操作数栈OPND和运算符栈OPTR。1、首先置操作数栈为空栈，把“#”移进运算符栈（实际放入栈中的是字符“#”在字符数组中的下标，对其它算符也是一样）。2、从左至右扫描表达
6、式，凡遇到操作数一律进OPND栈；若遇到运算符，则把栈顶运算符与扫描运算符的优先数进行比较：若-1：扫描运算符进OPTR栈0：若“（”和“）”，栈顶符号出栈；若为#，运算结束。1：取OPND栈顶操作数与OPTR栈顶算符进行运算，参与运算的操作数和运算符出栈，运算结果进OPND栈NO:表示表达式有错。若表达式处理完，OPTR栈为#，OPND栈中只剩一项，表示表达式的运算结果，则分析成功。若达不到这种状态，表明表达式有错。五、实现1、数据存储结构假设一个表达式不可能很长，如不超过屏幕上一行的宽度（80个字符），在对表达式处理之前先把表达式放入一个一维字符数组中，用户
7、可以不输入表达式前后的“#”，由处理程序自动加入。由于表达式的长度有限，运算符栈和操作数栈的长度野优先，假定不超过20，所以都采用顺序存储结构比较合适。用C语言可定义如下：#defineEXPLENGT100#defineSTACKSIZE20charexpr[EXPLENGT];intOPTR[STACKSIZE];//运算符栈，元素为运算符对应的整数编码doubleOPND[STACKSIZE]；//操作数栈，元素为表达式中的运算数据2、运算符宏定义为了判断运算符的方便，增强程序的可读性，定义如下宏常量：#definePLUS0#defineMINUS1#d
8、efinePOWER2#
