C语言表达式求值

实验四算术表达式求值运算器一、实验目的帮助学生熟练掌握栈的基本操作，并通过用算符优先法对表达式求值的过程深刻领会用栈解决实际问题的基本方法。

二、实验内容编写程序实现从键盘终端输入语法正确的算术表达式，计算出表达式的值。

为了避免算符的二义性，可以假设表达式中只包含实型正常数运算符包括加、减、乘、除四种基本运算，可以包含圆括号。

三、实验仪器微型计算机实验用编程语言：Turbo C 2.0，Borland C 3.0等以上版本四、实验原理1、算术四则运算法则：先乘除后加减从左至右先括号内后括号外2、方法：对运算符建立优先关系矩阵，按优先关系对表达式进行处理。

算符：运算符和界符。

根据法则1：对于两个相邻运算符，乘除优先于加减。

根据法则2：乘除优先级相同，加减优先级相同。

相邻两个同级运算符左优先。

根据法则3：“（”前面的运算符优先级低于“（”的优先级。

“（”的优先级低于右边相邻算符。

“）”左边的算符高于“）”的优先级。

由于“（”和“）”必须成对出现，令它们的优先性相同。

为了处理的方便，假设表达式以“＃”开始和结束，输入表达式的一般形式为：#表达式#如：#5.3+4.2*(7.6+4.5)#规定开始的“＃”的优先性低于所有其它算符，所有其它算符的优先性高于结束的“＃”。

根据假设，表达式开始的“#”和结束的“#”必须成对出现，所以也令它们的优先性相同。

对于一个正确的表达式，“)”不可能与“（”相邻，“（”不可能与结束的“#”相邻，开始的“#”不可能与“）”相邻，它们之间没有优先性，程序应具有这种判断能力。

根据上面的讨论，可用表1所示的算符优先关系矩阵来描述算符之间的优先关系，其中，用“>”表示表达式中前一个算符的优先性高于后一个算符的优先性，用“<”表示表达式中前一个算符的优先性低于后一个算符的优先性，用“=”表示表达式中前一个算符的优先性与后一个算符的优先性相同。

若两个算符之间无优先性，用空白表示。

表1：算符优先关系矩阵3、算符表示为了使算符与优先关系矩阵的行列号对应，把表达式中可能有的算符放入一维数组中，可以用字符在一维数组中的下标作为字符的标识码。

本计算中，算法表示如下：即用0表示算符“＋”，用1表示算符“－”，等。

定义的字符数组为：char a[]={'+','-','*','/','(',')','#'}; 4、优先关系矩阵的表示大于关系用1表示 小于关系用－1表示 等于关系用0表示若两个算符间不存在关系，则用一个特定的数值表示，如用整数的上限值32767表示，可定义一个宏常量来表示：#define NO 32767 则其优先关系矩阵为：int PriorityTable[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、从左至右扫描表达式，凡遇到操作数一律进OPND栈；若遇到运算符，则把栈顶运算符与扫描运算符的优先数进行比较：若-1：扫描运算符进OPTR栈0：若“（”和“）”，栈顶符号出栈；若为#，运算结束。

1：取OPND栈顶操作数与OPTR栈顶算符进行运算，参与运算的操作数和运算符出栈，运算结果进OPND栈NO:表示表达式有错。

若表达式处理完，OPTR栈为#，OPND栈中只剩一项，表示表达式的运算结果，则分析成功。

若达不到这种状态，表明表达式有错。

五、实现1、数据存储结构假设一个表达式不可能很长，如不超过屏幕上一行的宽度（80个字符），在对表达式处理之前先把表达式放入一个一维字符数组中，用户可以不输入表达式前后的“#”，由处理程序自动加入。

由于表达式的长度有限，运算符栈和操作数栈的长度野优先，假定不超过20，所以都采用顺序存储结构比较合适。

用C语言可定义如下：#define EXPLENGT 100#define STACKSIZE 20char expr[EXPLENGT];int OPTR[STACKSIZE]; //运算符栈，元素为运算符对应的整数编码double OPND[STACKSIZE]； //操作数栈，元素为表达式中的运算数据2、运算符宏定义为了判断运算符的方便，增强程序的可读性，定义如下宏常量：#define PLUS 0 //运算符+#define MINUS 1 //运算符-#define POWER 2 //运算符*#define DIVIDE 3 //运算符/#define LEFTP 4 //运算符(#define RIGHP 5 //运算符）#define STARTEND 6 //运算符##define DIGIT 7 //数字字符#define POINT 8 //小数点3、基本功能(1)输入算术表达式(2)计算表达式的值4、辅助功能（1）菜单选择（2）获取字符类型编码5、程序结构该程序由5个函数组成，其中主函数1个，基本功能函数2个，辅助功能函数2个。

函数间的调用关系图1所示。

图1 程序结构图6、函数说明（1）主函数main功能：根据菜单选择确定要操作的内容：表达式输入表达式计算计算结果输出退出系统（2）菜单选择函数：menu功能：构造功能菜单，并选择下一步要操作的功能。

格式：int menu(void)参数：无参数。

返回值：1～4中的一个序号。

可供选择的功能如下：1--input expression 表示输入表达式2--calculation expression 表示计算表达式3--print result 表示输出计算结果4--Quit 表示退出系统，结束程序的运行（3）表达式输入函数：InputExpression功能：输入表达式，并在表达式前后加上符号“＃”格式：void InputExpression(char str[])参数：char str[]—存放输入的表达式返回值：无（4）表达式计算函数：excute功能:完成表达式的计算格式：int excute(char *str,double *Result)参数：char *str—要计算的表达式字符串double *Result—计算结果值返回值：1—计算成功0—计算失败（5）确定当前字符类型函数：GetCharType功能：确定当前要处理的字符的类型格式：int GetCharType(char ch)参数：char ch—当前要处理的字符返回值：若为算符，返回字符的编码（一维数组下标）若为数字，返回符号常熟DIGIT（数字）若为小数点，返回符号常熟POINT（小数点）若不是定义的表达式的字符，返回－1。

六、算法描述1、表达式计算算法描述设栈顶指针：int topTr—运算符栈顶指针topNd—操作数栈顶指针表达式字符指针：int pp—指向表达式中当前要处理的字符开始时，把表达式开始符“#”（编码）放入栈中。

设当前要处理的字符类型为CharType。

以当前要处理的字符为参照来确定下一步要作的处理：●若当前字符为非法字符：则结束处理，返回出错标志（0）；●若当前字符是数字：表示遇到表达式中的操作数，则识别出该操作数；●若当前字符是小数点：表示遇到以小数点开头的操作数，则识别出该操作数；●若当前字符是＋、－、*、/运算符：则用栈顶运算符与当前运算符比较优先性：若对应的数组元素为－1，则当前运算符（运算符编码）进栈，调整pp指向下一个字符。

若对应的数组元素为1，则取运算符栈顶运算符和操作数栈顶操作数进行运算，参与运算的运算符和操作数出栈，运算结果进操作数栈。

实现为： OPND[topNd-2]=OPND[topNd-2] op OPBD[topNd-1];topNd--;topTr--;●若当前字符是左括号(: 则左括号进栈，pp指向下一个字符●若当前字符是右括号）：⊙若栈顶是左括号，则左括号出栈，pp指向下一个字符⊙若栈顶是运算符，则取运算符栈顶运算符和操作数栈顶操作数进行运算，参与运算的运算符和操作数出栈，运算结果进操作数栈。

实现为： OPND[topNd-2]=OPND[topNd-2] op OPBD[topNd-1];topNd--;topTr--;重复该操作，直到栈顶出现左括号“（”。

⊙若栈顶是＃，则左括号和右括号不配对，结束处理，返回出错标志（0）●若当前字符为＃：依次从运算符栈取出运算符和从操作数栈取出操作数进行计算，直到运算符栈的栈顶为＃为止。

若运算符栈顶为＃，当前字符也为＃，则表达式计算结束，返回计算结果值和计算成功标志（1）。

2、字符型数字常数转换为数值型常数的方法因为程序处理的表达式是以字符串形式出现的，表达式中每个数值型常数也是有一个一个的数字字符组成。

处理程序必须把字符串形式的常数转换为数值形式的常数。

（1）整数的转换方法我们知道，一个数值型常数3256可以表示为：3256=((3*10+2)*10+5)*10+6相应的，一个字符串型的数字常数“3256”转换为数值型常数可以表示为：(((‘3’-48)*10+(‘2’-48))*10+(‘5’-48))*10+(‘6’-48)每个字符的ASCII码指减去48就是该字符对应数字值。

实现方法：依次读入数字字符，用前面读入子字符串对应的数值型值乘以10，再加上当前字符的数字值，就是当前读入子字符串对应的数值型值。

用C语言描述如下：number=0;while(str[pp]>='0' && str[pp]<='9'){ number=number*10+(str[pp]-48);pp++;}（2）小数的转换方法一个小数常数0.2345可以表示为：0.2345=2/10+3/100+4/1000+5/10000相应的，一个字符串表示的小数“0.2345”转换为数值型小数可以表示为：“0.2345”=(‘2’-48)/10+(‘3’-48)/100+(‘4’-48)/1000+(‘5’-48)/10000假设当前字符指针指向小数点字符，转换方法描述为：number=0;temp=10.0;pp++;while(str[pp]>='0' && str[pp]<='9'){ number=number+(str[pp]-48)/temp;temp=temp*10;pp++;}（3）既有整数又有小数部分的实数的转换算法综合前面两部分算法，既有整数又有小数部分的实数的转换算法描述如下：number=0;while(str[pp]>='0' && str[pp]<='9') //处理实数的整数部分{ number=number*10+(str[pp]-48);pp++;}if(str[pp]=='.') //遇到小数点{ temp=10.0;pp++;while(str[pp]>='0' && str[pp]<='9') //处理实数的小数部分{ number=number+(str[pp]-48)/temp;temp=temp*10;pp++;}}七、思考题1、若表达式中的数据带有正负号的实数字符串该怎样进行转换？2、对于指数形式的实数字符串该怎样进行转换？八、部分函数代码#include<stdio.h>#include <string.h>#include <conio.h>#define PLUS 0#define MINUS 1#define POWER 2#define DIVIDE 3#define LEFTP 4#define RIGHP 5#define STARTEND 6#define DIGIT 7#define POINT 8#define NUM 7#define NO 32767#define STACKSIZE 20//运算符char a[]={'+','-','*','/','(',')','#'};//优先关系矩阵，规定：=为0,>为1,<为-1,空为NOint PriorityTable[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}};int menu(void) ;/*{int n;printf("\n\n");printf(" MENU \n");printf("********************************************\n"); printf("operations\n");printf(" 1.输入表达式\n");printf(" 2.计算表达式\n");printf(" 3.输出计算结果\n");printf(" 4.退出\n");printf("********************************************\n"); printf("choice(1,2,3,4):");scanf("%d",&n);return n;}*//***************************//* 输入表达式函数 *//***************************/void InputExpression(char str[]){ int len;printf("Input expression string:\n");scanf("%s",str);len=strlen(str);str[len]='#';str[len+1]='\0';}/*************************************************//* 确定当前字符类型 *//*************************************************//* 若为运算符，则返回运算符在运算符数组中的序号 *//* 若为数字字符，则返回DIGIT *//* 若为小数点字符,则返回POINT *//* 否则为非法字符,返回-1 *//*************************************************/int GetCharType(char ch){ int i;for(i=0;i<NUM;i++) if(ch==a[i]) return(i);if(ch>='0' && ch<='9') return(DIGIT);if(ch=='.') return(POINT);return(-1);}/*************************************************//* 表达式计算 *//*************************************************//* 输入参数：char *str,表达式字符串 *//* 输出参数：double *Result,表达式计算结果 *//* 函数返回值：1 计算正确 *//* 0 表达式有错 *//*************************************************/int EXCUTE(char *str,double *Result){int pp,strlength,topTr,topNd,CharType,OPTR[STACKSIZE]; int b,c;char *p; double number,temp,OPND[STACKSIZE];OPTR[0]=STARTEND;topTr=1;topNd=0;pp=0;while((str[pp])){ CharType=GetCharType(str[pp]); //确定字符类型switch(CharType){ case -1: //不是表达式中的字符，表达式有错return(0);case DIGIT: //数字字符，实数的开始字符number=0;while(str[pp]>='0' && str[pp]<='9') //处理实数的整数部分{ number=number*10+(str[pp]-48);pp++;}if(str[pp]=='.') //遇到小数点{ temp=10.0;pp++;while(str[pp]>='0' && str[pp]<='9') //处理实数的小数部分 { number=number+(str[pp]-48)/temp;temp=temp*10;pp++;}}OPND[topNd]=number;topNd++;break;case POINT: //小数点，以小数点开头的实数number=0;temp=10.0;pp++;while(str[pp]>='0' && str[pp]<='9'){ number=number+(str[pp]-48)/temp;temp=temp*10;pp++;}OPND[topNd]=number;topNd++;break;case PLUS: //+case MINUS: //-case POWER: //*case DIVIDE: ///while(PriorityTable[OPTR[topTr-1]][CharType]==1){if(OPTR[topTr-1]==PLUS)number=OPND[topNd-2]+OPND[topNd-1];else if(OPTR[topTr-1]==MINUS)number=OPND[topNd-2]-OPND[topNd-1];else if(OPTR[topTr-1]==POWER)number=OPND[topNd-2]*OPND[topNd-1];else if(OPTR[topTr-1]==DIVIDE)number=OPND[topNd-2]/OPND[topNd-1];topNd--;topNd--;topTr--;OPND[topNd]=number;topNd++;return number;}OPTR[topTr]=CharType;topTr++;pp++;break;case LEFTP: //(OPTR[topTr]=LEFTP;topTr++;pp++;break;case RIGHP: //)while(OPTR[topTr-1]!=LEFTP){if(OPTR[topTr-1]==PLUS){number=OPND[topNd-1]+OPND[topNd-2];topNd--;topNd--;topTr--;OPND[topNd]=number;topNd++;return number;}else if(OPTR[topTr-1]==MINUS){number=OPND[topNd-2]-OPND[topNd-1];topNd--;topNd--;topTr--;OPND[topNd]=number;topNd++;return number;}else if(OPTR[topTr-1]==POWER){number=OPND[topNd-2]*OPND[topNd-1];topNd--;topNd--;topTr--;OPND[topNd]=number;topNd++;return number;}else if(OPTR[topTr-1]==DIVIDE){number=OPND[topNd-2]/OPND[topNd-1];topNd--;topNd--;topTr--;OPND[topNd]=number;topNd++;return number;}}topTr--;pp++;break;case STARTEND: //遇到表达式结束符while(OPTR[topTr-1]!=STARTEND){if(OPTR[topTr-1]==PLUS){number=OPND[topNd-1]+OPND[topNd-2];topNd--;topNd--;topTr--;OPND[topNd]=number;topNd++;return number;}else if(OPTR[topTr-1]==MINUS){number=OPND[topNd-2]-OPND[topNd-1];topNd--;topNd--;topTr--;OPND[topNd]=number;topNd++;return number;}else if(OPTR[topTr-1]==POWER){number=OPND[topNd-2]*OPND[topNd-1];topNd--;topNd--;topTr--;OPND[topNd]=number;topNd++;return number;}else if(OPTR[topTr-1]==DIVIDE){number=OPND[topNd-2]/OPND[topNd-1];topNd--;topNd--;topTr--;OPND[topNd]=number;topNd++;return number;}}pp++;break;if(topNd==1){ *Result=OPND[0];return(1);}else return(0);}}return(1);}void main(){ int num,flag;double result;char str[256];str[0]=0;while(1){ num=menu();switch(num){case 1: //输入表达式InputExpression(str);flag=0;printf("%s\n",str);getchar();break;case 2: //计算表达式if(str[0]==0){ printf("Expresson is Empty!");getchar();break;}if(!EXCUTE(str,&result)){ printf("The expression has error!\n");getchar();}else{ printf("calulation has finished!\n"); getchar();flag=1;}break;case 3: //打印计算结果if(flag){ printf("#%s=%lf\n",str,result);getchar();}break;case 4: //退出系统break;}if(num==4) break;}}int menu(void){ int num;//clrscr();printf("%20c1--input expression\n",' ');printf("%20c2--calculation expression\n",' '); printf("%20c3--print result\n",' ');printf("%20c4--Quit\n",' ');printf(" please select 1,2,3,4:");do{scanf("%d",&num);}while(num<1 || num>4);return(num);}。