数据结构课程设计 表达式的值
- 格式:doc
- 大小:152.46 KB
- 文档页数:15
课程设计报告课程名称数据结构课程设计题目算术表达式求值指导教师设计起始日期 4.18~4.25学院计算机学院系别计算机科学与工程学生姓名班级/学号成绩一、需求分析设计一个算术表达式四则运算的程序,要求完成包括加、减、乘、除运算,包含括号的基本整数表达式的运算。
在这里运算数可以1位长度,也可以多位长度。
在运算之后输出的正确运算结果,输入表达式后演示在求值中运算数栈内的栈顶数据变化过程,最后得到运算结果。
(1)输入:3*(7-2)(2)输出:数据栈栈顶元素:3,7,2,7,5,3,15结果:15(3)自选数据二、概要设计1、使用栈的数据结构表示数据的存储。
2、设计算法将中缀表达式转换成后缀表达式,用栈的数据结构实现表达式的运算。
3、把中缀表达式转换为后缀表达式算法的基本思路是从头到尾地扫描中缀表达式中的每个字符,对于不同类型的字符按不情况进行处理。
三、详细设计数据结构:字符类型栈/* 定义字符类型栈*/typedef struct{char stackname[20];char *base;char *top;} Stack;算法:将中缀表达式转换为后缀表达式void Change(char* s1, char* s2)// 将字符串s1中的中缀表达式转换为存于字符串s2中的后缀表达式{Stack R; // 定义用于暂存运算符的栈InitStack(R); // 初始化栈Push(R,'#'); // 给栈底放入’#’字符,它具有最低优先级0int i,j;i=0; // 用于指示扫描s1串中字符的位置,初值为0j=0; // 用于指示s2串中待存字符的位置,初值为0char ch=s1[i]; // ch保存s1串中扫描到的字符,初值为第一个字符while( ch!='#'){ // 顺序处理中缀表达式中的每个字符if(ch==' ')// 对于空格字符不做任何处理,顺序读取下一个字符ch=s1[++i];else if(ch=='('){ // 对于左括号,直接进栈Push(R,ch);ch=s1[++i];}else if(ch==')'){ // 对于右括号,使括号内的仍停留在栈中的运算符依次// 出栈并写入到s2中while(Peek(R)!='(')s2[j++]=Pop(R);Pop(R); // 删除栈顶的左括号ch=s1[++i];}else if(ch=='+'||ch=='-'||ch=='*'||ch=='/'){ // 对于四则运算符,使暂存在栈中的不低于ch优先级// 的运算符依次出栈并写入到s2中char w=Peek(R);while(Precedence(w)>=Precedence(ch)){ // Precedence(w)函数返回运算符形参的优先级s2[j++]=w;Pop(R); w=Peek(R); }}四、调试分析调试:在设计过程中出现程序不能运行,发现不能找到结束标识符,因此在设计的时候需要人为动态添加结束标识符‘#’,顺利运行算法时间和空间分析:算法的运行时间主要花在while循环上,它从头到尾扫描后缀表达式中的每一个数据(每个操作数或运算符均为一个数据),若后缀表达式由n个数据组成,则此算法的时间复杂度为O(n)。
课程设计报告课程设计名称:数据结构课程设计课程设计题目:算术表达式求值的实现院(系):*****专业:*****班级:*****学号:*****姓名:*****指导教师:*****目录1 课程设计介绍 (1)1.1课程设计内容 (1)1.2课程设计要求 (1)2 课程设计原理 (2)2.1课设题目粗略分析 (2)2.2原理图介绍 (2)2.2.1 功能模块图 (2)2.2.2 流程图分析 (3)3 数据结构分析 (5)3.1存储结构 (5)3.2算法描述 (5)4 调试与分析 (7)4.1调试过程 (7)4.2程序执行过程 (7)参考文献 (8)附录(关键部分程序清单) (9)1 课程设计介绍1.1 课程设计内容编写算法能够进行整型和实型数的表达式求值,能够根据运算的数据选择正确的运算结果的数据类型,表达式的运算符为:+,—,*,/,(,),且括号可以嵌套。
1.2 课程设计要求1.给出必要的输入、输出信息和提示信息。
2.参考相应的资料,独立完成课程设计任务。
3.交规范课程设计报告和软件代码。
2 课程设计原理2.1 课设题目粗略分析根据课设题目要求,拟将整体程序分为三大模块。
此三个模块相互独立,没有嵌套调用的情况,以下是三个模块的大体分析:1.首先依次定义字符类型栈、整型栈、运算符栈和操作数栈,构造运算符栈和操作数栈,然后运算符、操作数依次入栈。
2. 依次读入表达式,若是操作符即进OPND栈,若是运算符即进OPTR栈。
顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置,base为栈底指针,在顺序栈中,它始终指向栈底,即top=base可作为栈空的标记,每当插入新的栈顶元素时,指针top增1,删除栈顶元素时,指针top减1。
3. 按照运算符的优先级别对表达式进行求值运算。
2.2 原理图介绍该功能模块图介绍了这个程序的主要功能。
2.2.1 功能模块图图2.1功能模块图如图2.1所示,要实现表达式的求值,即必须要实现存储、读取和计算三项功能。
《数据结构》课程设计利用栈求表达式的值班级: 2学号: 100171021330姓名:吴迪指导老师:王方利用栈求表达式的值1、设计思路这个程序的关键是对数字与运算符的判断和运算符优先级的判断,以及出栈的运算。
建立两个栈,分别存储数字与运算符,栈1存运算符,栈2存数字。
依次读取表达式的字符串,先判断是数字还是运算符,如果是数字不能马上压入栈2,因为可能是大于10的数字,应该继续循环,如果还是数字,则利用计算保存数值,直到指到运算符时停止,将计算后的数字压入栈2。
压入运算符之前先将要压入的与栈顶的运算符优先级相比较,如果栈顶是‘(’而当前不是‘)’,则不需比较优先级,直接压入;如果栈顶是‘(’,当前是‘)’,则抵消(弹出‘(’,指向表达式下一个字符);若当前的运算符优先级大于栈顶的,则压入;若当前的运算符优先级小于栈內时,弹出栈顶的运算符,同时弹出两组数字,经过运算符的运算后再重新压到栈内。
为了方便判断运算结束,在存储运算符之前先将‘#’压入栈1中,在输入表达式时以‚#‛结束,所以可以以运算符==‘#’并且栈1顶==‘#’来结束运算,弹出栈2的数值,即为表达式求值的最终结果。
上述操作的算法步骤:(1)初始化算符S1,数字栈S2;,将‘#’压入算符栈S1中。
(2)读表达式字符=>w。
(3)当栈顶为‘#’并且w也是‘#’时结束;否则循环做下列步骤:(3-1)如果w是数字,存储到m,再经过计算存储到num中。
m=w-‘0’;num=num*pow(10,n)+m;n++;读下一个字符=>w,如果是运算符,则跳出循环;转3-2。
(3-2)w若是运算符,则:(3-2-1)如果栈顶为‘(’并且w为‘)’则‘(’出栈,读下一个字符=>w;转(3)。
(3-2-2)如果栈顶为‘(’或者栈顶优先级小于w优先级,则w入栈,读下一个字符=>w;转(3)。
否则:从算符栈中出栈,并从数字栈中弹出两组数字进行运算,将结果重新压入数字栈,转(3)。
(一) 需求分析1、输入的形式和输入值的范围:根据题目要求与提示,先选择你要使用的表达式形式(中缀用1,后缀用0),在输入一个中缀表达式,输入数的范围为int型,此时,程序将计算出表达式的结果。
2、输出的形式:当按照程序要求选择了1或0之后,再输入表达式;如果选择的是1,则程序将自动运算出表达式结果;如果之前选择的是0,则程序将现将中缀表达式转化为后缀表达式并计算出结果。
3、程序所能达到的功能:本程序能计算出含+、-、*、/、(、)等运算符的简单运算。
4、测试数据:输入一个表达式,如果你之前选择的是“中缀表达式”,那么输入5*(4-2)#,那么输出结果是10;如果之前选择的是“后缀表达式”,那么输入5*(4-2)#,那么他将先转换成后缀表达式5 4 2 - * #,再输出结果10。
如果输入表达式没有结束标示符#,如5*(4-2),那将不会输出任何结果,或出现错误结果。
(二) 概要设计为了实现上述操作,应以栈为存储结构。
1.基本操作:(1). int GetTop(SqStack *s)初始条件:栈存在;操作结果:若栈为空,则返回s的栈顶元素;否则返回ERROR。
(2).void Push(SqStack *s,int e)初始条件:栈存在;操作结果:插入e为新的栈顶元素。
(3).int Pop(SqStack *s)初始条件:栈存在;操作结果:若栈不空,则删除之,并返回其值;否则返回REEOR。
(4).void InitStack(SqStack *s)初始条件:栈存在;操作结果:置栈为空。
(5).int Empty(SqStack *s)初始条件:栈存在;操作结果:判定s是否为空栈。
(6).int Operate(int a,char theta, int b)初始条件:操作数a和b存在,且theta是+、-、*、/四则运算;操作结果:返回a与b间theta运算的结果。
(7).int In(char s,char* TestOp)初始条件:s为待判断字符,TestOp为已知的算符集合;操作结果:s为算符集合中的元素则返回1,否则返回0.(8).int ReturnOpOrd(char op,char* TestOp)初始条件:op为待确定运算符,TestOp为已知的算符集合;操作结果:确定运算符类型。
XXXXXX大学《数据结构》课程设计报告班级:学号:姓名:指导老师:目录一算术表达式求值一、需求分析二、程序得主要功能三、程序运行平台四、数据结构五、算法及时间复杂度六、测试用例七、程序源代码二感想体会与总结算术表达式求值一、需求分析一个算术表达式就是由操作数(operand)、运算符(operator)与界限符(delimiter)组成得。
假设操作数就是正整数,运算符只含加减乘除等四种运算符,界限符有左右括号与表达式起始、结束符“#”,如:#(7+15)*(23—28/4)#。
引入表达式起始、结束符就是为了方便.编程利用“算符优先法”求算术表达式得值.二、程序得主要功能(1)从键盘读入一个合法得算术表达式,输出正确得结果。
(2)显示输入序列与栈得变化过程。
三、程序运行平台Visual C++6、0版本四、数据结构本程序得数据结构为栈。
(1)运算符栈部分:struct SqStack //定义栈{char *base; //栈底指针char *top; //栈顶指针intstacksize; //栈得长度};intInitStack (SqStack &s) //建立一个空栈S{if (!(s、base= (char *)malloc(50*sizeof(char))))exit(0);s、top=s、base;s、stacksize=50;return OK;}char GetTop(SqStack s,char &e) //运算符取栈顶元素{if (s、top==s、base) //栈为空得时候返回ERROR{ﻩ printf("运算符栈为空!\n");ﻩ return ERROR;}elsee=*(s、top-1); //栈不为空得时候用e做返回值,返回S得栈顶元素,并返回OK returnOK;}int Push(SqStack&s,char e) //运算符入栈{if (s、top—s、base >= s、stacksize)ﻩ{printf("运算符栈满!\n");ﻩs、base=(char*)realloc(s、base,(s、stacksize+5)*sizeof(char));//栈满得时候,追加5个存储空间if(!s、base)exit (OVERFLOW);s、top=s、base+s、stacksize;s、stacksize+=5;}ﻩ*(s、top)++=e;//把e入栈ﻩreturn OK;}int Pop(SqStack &s,char &e) //运算符出栈{if (s、top==s、base) //栈为空栈得时候,返回ERROR{printf("运算符栈为空!\n”);ﻩ return ERROR;}else{ﻩﻩe=*-—s、top;//栈不为空得时候用e做返回值,删除S得栈顶元素,并返回OK return OK;}}int StackTraverse(SqStack&s)//运算符栈得遍历{ﻩchar *t;ﻩt=s、base;ﻩif (s、top==s、base){ﻩ printf(”运算符栈为空!\n”); //栈为空栈得时候返回ERRORreturn ERROR;}while(t!=s、top){ﻩﻩprintf(" %c",*t); //栈不为空得时候依次取出栈内元素t++;ﻩ}return ERROR;}(2)数字栈部分:struct SqStackn//定义数栈{int *base; //栈底指针int*top; //栈顶指针int stacksize; //栈得长度};intInitStackn (SqStackn &s) //建立一个空栈S{s、base=(int*)malloc(50*sizeof(int));if(!s、base)exit(OVERFLOW);//存储分配失败s、top=s、base;s、stacksize=50;return OK;}int GetTopn(SqStackn s,int&e) //数栈取栈顶元素{if(s、top==s、base){printf("运算数栈为空!\n");//栈为空得时候返回ERRORﻩ return ERROR;}elseﻩe=*(s、top-1);//栈不为空得时候,用e作返回值,返回S得栈顶元素,并返回OKreturnOK;}int Pushn(SqStackn &s,int e) //数栈入栈{if(s、top—s、base>=s、stacksize){ﻩﻩprintf("运算数栈满!\n");//栈满得时候,追加5个存储空间ﻩs、base=(int*)realloc (s、base,(s、stacksize+5)*sizeof(int));if(!s、base) exit (OVERFLOW);ﻩs、top=s、base+s、stacksize;//插入元素e为新得栈顶元素s、stacksize+=5;}*(s、top)++=e; //栈顶指针变化returnOK;}int Popn(SqStackn &s,int &e)//数栈出栈{ﻩif (s、top==s、base){ﻩ printf("运算符栈为空!\n");//栈为空栈得视时候,返回ERRORﻩ return ERROR;ﻩ}else{ﻩﻩe=*—-s、top;//栈不空得时候,则删除S得栈顶元素,用e返回其值,并返回OK ﻩreturnOK;}}int StackTraversen(SqStackn &s)//数栈遍历{ﻩint*t;ﻩt=s、base ;ﻩif(s、top==s、base)ﻩ{printf("运算数栈为空!\n”);//栈为空栈得时候返回ERRORﻩ return ERROR;ﻩ}ﻩwhile(t!=s、top)ﻩ{printf(” %d”,*t); //栈不为空得时候依次输出t++;}return ERROR;}五、算法及时间复杂度1、算法:建立两个不同类型得空栈,先把一个‘#’压入运算符栈。
数据结构表达式求值(中缀)实验报告题目名称表达式求值学号姓名指导教师日期一1. 问题描述:在计算机中,算术表达式由常量、变量、运算符和括号组成。
由于不同的运算符具有不同的优先级,又要考虑括号,因此,算术表达式的求值不可能严格地从左到右进行,在程序设计时,借助栈实现。
2. 表达式求值这个程序,主要利用栈和数组,把运算的先后步骤进行分析并实现简单的运算,以字符列的形式从终端输入语法的正确的、不含变量的整数表达式。
利用已知的算符优先关系,实现对算术四则运算的求值,在求值中运用栈、运算栈、输入字符和主要操作的变化过程。
该程序相当于一个简单的计算机计算程序,只进行简单的加减乘除和带括号的四则运算。
1、基本思想(中缀表达式求值)要把一个表达式翻译成正确求值的一个机器指令序列,或者直接对表达式求值,首先要能够正确解释表达式,要了解算术四则运算的规则即:(1)先乘除后加减;(2)从左到右计算;(3)先括号内,后括号外。
下表定义的运算符之间的关系:b + - * / () # a+ > > < < < > > _ > > < < < > > * > > > > < > > / > > > > < > > ( < < < < < = ) > > > > > > # < < < < < =为了实现运算符有限算法,在程序中使用了两个工作栈。
分别是:运算符栈OPTR,操作数栈OPND.基本思想:(1)首先置操作数栈为空栈,表达式起始符“#”为运算符栈的栈底元素;(2)依次读入表达式中每个字符,若是操作数则进OPND栈,若是运算符则和OPTR栈得栈顶运算符比较优先级后作相应操作。
数据结构课程设计四则运算表达式求值(C语⾔版) 明⼈不说暗话,直接上,输⼊提取码z3fy即可下载。
⽂件中包含程序,程序运⾏⽂件,设计报告和测试样例,应有尽有,欢迎⼩伙伴们在中下载使⽤。
本课程设计为四则运算表达式求值,⽤于带⼩括号的⼀定范围内正负数的四则运算标准(中缀)表达式的求值。
注意事项:1、请保证输⼊的四则表达式的合法性。
输⼊的中缀表达式中只能含有英⽂符号“+”、“-”、“*”、“/”、“(”、“)”、“=”、数字“0”到“9”以及⼩数点“.”,输⼊“=”表⽰输⼊结束。
例如9+(3-1)*3.567+10/2=,特别是请勿输⼊多余空格和中⽂左右括号。
2、输⼊的中缀表达式默认限定长度是1001,可根据具体情况调整字符串数组的长度。
3、请保证输⼊的操作数在double数据类型范围内,单个数字有效数字长度不可超过15位。
本课程设计中操作数是C语⾔中的双精度浮点数类型。
4、本课程设计中的运算数可以是负数,另外如果是正数可直接省略“+”号(也可带“+”号)。
下⾯的程序正常运⾏需要在上⾯的百度⽹盘中下载相应⽂件,否则⽆法正常使⽤哦。
1/*本程序为四则运算表达式求值系统,⽤于计算带⼩括号的四则运算表达式求值。
2具体算法:3先将字符串处理成操作单元(操作数或操作符),再利⽤栈根据四则运算4的运算法则进⾏计算,最后得出结果。
*/56 #include<stdio.h>7 #include<ctype.h>8 #include<stdlib.h>9 #include<string.h>10 #include<stdlib.h>11 #include<ctype.h>1213const int Expmax_length = 1001;//表达式最⼤长度,可根据适当情况调整14struct Ope_unit15 {//定义操作单元16int flag;//=1表⽰是操作数 =0表⽰是操作符 -1表⽰符号单元17char oper;//操作符18double real;//操作数,为双精度浮点数19 };2021void Display();//菜单22void Instru(); //使⽤说明23int Check(char Exp_arry[]);24void Evalua(); //先调⽤Conver操作单元化,再调⽤Calculate函数计算结果并输出25int Conver(struct Ope_unit Opeunit_arry[],char Exp_arry[]);//将字符串处理成操作单元26int Isoper(char ch);//判断合法字符(+ - * / ( ) =)27int Ope_Compar(char ope1,char ope2);//操作符运算优先级⽐较28double Calculate(struct Ope_unit Opeunit_arry[],int Opeunit_count,int &flag);//⽤栈计算表达式结果29double Four_arithm(double x,double y,char oper);//四则运算3031int main()32 {33int select;34while(1)35 {36 Display();37 printf("请输⼊欲执⾏功能对应的数字:");38 scanf("%d",&select);39 printf("\n");40switch(select)41 {42case1: Evalua(); break;43case2: Instru(); break;44case0: return0;45default : printf("⽆该数字对应的功能,请重新输⼊\n");46 system("pause");47 }48 }49return0;50 }5152int Check(char Exp_arry[])53 {//检查是否有⾮法字符,返回1表⽰不合法,0表⽰合法54int Explength=strlen(Exp_arry),i;55for(i=0;i<Explength;i++)56 {57if(!Isoper(Exp_arry[i]) && Exp_arry[i] != '.' && !isdigit(Exp_arry[i]))58return1;59if(isdigit(Exp_arry[i]))60 {61int Dig_number=0,Cur_positoin=i+1;62while(isdigit(Exp_arry[Cur_positoin]) || Exp_arry[Cur_positoin]=='.')63 {64 Dig_number++;65 Cur_positoin++;66 }67if(Dig_number >= 16)//最多能够计算15位有效数字68return1;69 }70 }71return0;72 }7374void Evalua()75 {//先调⽤Conver函数将字符串操作单元化,再调⽤Calculate函数计算结果并输出76char Exp_arry[Expmax_length];77int flag=0;//假设刚开始不合法,1表达式合法,0不合法78struct Ope_unit Opeunit_arry[Expmax_length];7980 getchar();//吃掉⼀个换⾏符81 printf("请输⼊四则运算表达式,以=结尾:\n");82 gets(Exp_arry);83 flag=Check(Exp_arry);84if(flag)85 printf("该表达式不合法!\n");86else87 {88int Opeunit_count = Conver(Opeunit_arry,Exp_arry);89double ans = Calculate(Opeunit_arry,Opeunit_count,flag);90if(flag)91 {92 printf("计算结果为:\n");93 printf("%s%lf\n",Exp_arry,ans);94 }95else96 printf("该表达式不合法!\n");97 }98 system("pause");99 }100101int Conver(struct Ope_unit Opeunit_arry[],char Exp_arry[])102 {//将字符串操作单元化103int Explength=strlen(Exp_arry);104int i,Opeunit_count=0;105for(i=0;i<Explength;i++)106 {107if(Isoper(Exp_arry[i]))//是操作符108 {109 Opeunit_arry[Opeunit_count].flag=0;110 Opeunit_arry[Opeunit_count++].oper=Exp_arry[i];111 }112else//是操作数113 {114 Opeunit_arry[Opeunit_count].flag=1;115char temp[Expmax_length];116int k=0;117for(; isdigit(Exp_arry[i]) || Exp_arry[i]=='.' ;i++)118 {119 temp[k++]=Exp_arry[i];120 }121 i--;122 temp[k]='\0';123 Opeunit_arry[Opeunit_count].real=atof(temp);//将字符转化为浮点数124125//负数126if(Opeunit_count == 1 && Opeunit_arry[Opeunit_count-1].flag==0127 && Opeunit_arry[Opeunit_count-1].oper=='-')128 {129 Opeunit_arry[Opeunit_count-1].flag = -1;130 Opeunit_arry[Opeunit_count].real *= -1;131 }// -9132if(Opeunit_count >= 2 && Opeunit_arry[Opeunit_count-1].flag==0133 && Opeunit_arry[Opeunit_count-1].oper=='-' && Opeunit_arry[Opeunit_count-2].flag==0 134 && Opeunit_arry[Opeunit_count-2].oper !=')')135 {136 Opeunit_arry[Opeunit_count-1].flag = -1;137 Opeunit_arry[Opeunit_count].real *= -1;138 }// )-9139140//正数141if(Opeunit_count == 1 && Opeunit_arry[Opeunit_count-1].flag==0142 && Opeunit_arry[Opeunit_count-1].oper=='+')143 {144 Opeunit_arry[Opeunit_count-1].flag = -1;145 }// +9146if(Opeunit_count >= 2 && Opeunit_arry[Opeunit_count-1].flag==0147 && Opeunit_arry[Opeunit_count-1].oper=='+' && Opeunit_arry[Opeunit_count-2].flag==0148 && Opeunit_arry[Opeunit_count-2].oper !=')')149 {150 Opeunit_arry[Opeunit_count-1].flag = -1;151 }// )+9152 Opeunit_count++;153 }154 }155/*for(i=0;i<Opeunit_count;i++)156 {//查看各操作单元是否正确,1是操作数,0是操作符157 if(Opeunit_arry[i].flag == 1)158 printf("该单元是操作数为:%lf\n",Opeunit_arry[i].real);159 else if(Opeunit_arry[i].flag == 0)160 printf("该单元是操作符为:%c\n",Opeunit_arry[i].oper);161 else162 printf("该单元是负号符为:%c\n",Opeunit_arry[i].oper);163 }*/164return Opeunit_count;165 }166167double Calculate(struct Ope_unit Opeunit_arry[],int Opeunit_count,int &flag)168 {//根据运算规则,利⽤栈进⾏计算169int i,dS_pointer=0,oS_pointer=0;//dS_pointer为操作数栈顶指⽰器,oS_pointer为操作符栈顶指⽰器170double Dig_stack[Expmax_length];//操作数栈(顺序存储结构)171char Ope_stack[Expmax_length];//操作符栈172173for(i=0;i<Opeunit_count-1;i++)174 {175if( Opeunit_arry[i].flag != -1 )176 {177if(Opeunit_arry[i].flag)//是操作数178 {179 Dig_stack[dS_pointer++]=Opeunit_arry[i].real;//⼊操作数栈180//printf("%lf\n",Digit[dS_pointer-1]);181 }182else//是操作符 + - * / ( )183 {184//操作符栈为空或者左括号⼊栈185if(oS_pointer==0 || Opeunit_arry[i].oper=='(')186 {187 Ope_stack[oS_pointer++]=Opeunit_arry[i].oper;188//printf("%oS_pointer\Ope_u_count",Operator[oS_pointer-1]);189 }190else191 {192if(Opeunit_arry[i].oper==')')//是右括号将运算符⼀直出栈,直到遇见左括号193 {194 oS_pointer--;//指向栈顶195 dS_pointer--;//指向栈顶196while(Ope_stack[oS_pointer] != '(' && oS_pointer != 0)197 {198 Dig_stack[dS_pointer-1] = Four_arithm(Dig_stack[dS_pointer-1],Dig_stack[dS_pointer], 199 Ope_stack[oS_pointer--]);//oS_pointer--为操作符出栈200201 dS_pointer--;//前⼀个操作数出栈202//printf("操作数栈顶元素等于%lf\n",Digit[dS_pointer]);203 }204 oS_pointer--;//左括号出栈205206 oS_pointer++;//恢复指向栈顶之上207 dS_pointer++;208 }209else if(Ope_Compar(Opeunit_arry[i].oper,Ope_stack[oS_pointer-1]))//和栈顶元素⽐较210 {211 Ope_stack[oS_pointer++]=Opeunit_arry[i].oper;212//printf("%oS_pointer\Ope_u_count",Operator[oS_pointer-1]);213 }214else//运算符出栈,再将该操作符⼊栈215 {216 oS_pointer--;//指向栈顶217 dS_pointer--;//指向栈顶218while(Ope_Compar(Opeunit_arry[i].oper,Ope_stack[oS_pointer])==0 && oS_pointer != -1) 219 {//当前操作符⽐栈顶操作符优先级⾼220 Dig_stack[dS_pointer-1]=Four_arithm(Dig_stack[dS_pointer-1],Dig_stack[dS_pointer], 221 Ope_stack[oS_pointer--]);222 dS_pointer--;223//printf("操作数栈顶元素等于%lf\n",Digit[dS_pointer]);224 }225 oS_pointer++;//恢复指向栈顶之上226 dS_pointer++;227 Ope_stack[oS_pointer++]=Opeunit_arry[i].oper;228 }229 }230 }231 }232 }233/*for(i=0;i<oS_pointer;i++)234 printf("操作符栈%oS_pointer\Ope_u_count",Operator[i]);235 for(i=0;i<dS_pointer;i++)236 printf("操作数栈%lf\n",Digit[i]);*/237 oS_pointer--;//指向栈顶元素238 dS_pointer--;//指向栈顶元素239while(oS_pointer != -1)240 {241 Dig_stack[dS_pointer-1]=Four_arithm(Dig_stack[dS_pointer-1],Dig_stack[dS_pointer], 242 Ope_stack[oS_pointer--]);//oS_pointer--为操作符出栈243 dS_pointer--;//前⼀个操作数出栈244//printf("操作数栈顶元素为%lf\Ope_u_count",Digit[dS_pointer]);245 }246//printf("%dS_pointer,%dS_pointer\n",oS_pointer,dS_pointer);247if(oS_pointer==-1 && dS_pointer==0)248 flag=1;//为1表⽰表达式合法249return Dig_stack[0];250 }251252int Ope_Compar(char ope1,char ope2)253 {//操作符运算优先级⽐较254char list[]={"(+-*/"};255int map[5][5]={//先⾏后列,⾏⽐列的运算级优先级低为0,⾼为1256// ( + - * /257/* ( */1,0,0,0,0,258/* + */1,0,0,0,0,259/* - */1,0,0,0,0,260/* * */1,1,1,0,0,261/* / */1,1,1,0,0 };262int i,j;263for(i=0;i<5;i++)264if(ope1==list[i]) break;265for(j=0;j<5;j++)266if(ope2==list[j]) break;267return map[i][j];268 }269270double Four_arithm(double x,double y,char oper)271 {//四则运算272switch(oper)//保证不含其它运算符273 {274case'+': return x+y;275case'-': return x-y;276case'*': return x*y;277case'/': return x/y;//y不能为0278default : return0;279 }280 }281282int Isoper(char ch)283 {//判断合法字符 + - * / ( ) =284if(ch=='+' || ch=='-' || ch=='*' || ch=='/' || ch=='(' || ch==')' || ch=='=')285return1;286return0;287 }288289void Display()290 {//打印菜单291 system("cls");292 printf("/******************************************************************************/\n");293 printf("\t\t 欢迎使⽤本四则运算表达式求值系统\n");294 printf("\n\t说明:建议请您先阅读使⽤说明,再输⼊相应的数字进⾏操作,谢谢配合!\n"); 295 printf("\n\t\t1 四则运算表达式求值\n");296 printf("\n\t\t2 使⽤说明\n");297 printf("\n\t\t0 退出\n");298 printf("/******************************************************************************/\n");299 }300301void Instru()302 {//打印使⽤说明303 FILE *fp;304char ch;305if( ( fp=fopen("使⽤说明.txt","r") ) == NULL)306 {307 printf("⽂件打开失败!\n");308 exit(0);309 }310for(; (ch = fgetc(fp)) != EOF; )311 putchar(ch);312 fclose(fp);313 printf("\n");314 system("pause");315 }。
实验课程名称专业班级学生姓名学号指导教师20 至 20 学年第学期第至周算术表达式求值演示一、概述数据结构课程设计.要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面.加深对课程基本内容的理解。
同时.在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
在这次的课程设计中我选择的题目是算术表达式求值演示。
表达式计算是实现程序设计语言的基本问题之一.也是栈的应用的一个典型例子。
设计一个程序.演示用算符优先法对算术表达式求值的过程。
深入了解栈和队列的特性.以便在解决实际问题中灵活运用它们.同时加深对这种结构的理解和认识。
二、系统分析1.以字符列的形式从终端输入语法正确的、不含变量的整数表达式。
利用已知的算符优先关系.实现对算术四则混合运算表达式的求值.并仿照教科书的例子在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。
2.一般来说.计算机解决一个具体问题时.需要经过几个步骤:首先要从具体问题抽象出一个适当的数学模型.然后设计一个解决此数学模型的算法.最后编出程序.进行测试.调试直至得到想要的答案。
对于算术表达式这个程序.主要利用栈.把运算的先后步骤进行分析并实现简单的运算!为实现算符优先算法.可以使用两个栈.一个用以寄存运算符.另一个用以寄存操作数和运算结果。
3.演示程序是以用户于计算机的对话方式执行.这需要一个模块来完成使用者与计算机语言的转化。
4.程序执行时的命令:本程序为了使用具体.采用菜单式的方式来完成程序的演示.几乎不用输入什么特殊的命令.只需按提示输入表达式即可。
(要注意输入时格式.否者可能会引起一些错误)5. 测试数据。
三、概要设计一个算术表达式中除了括号、界限符外.还包括运算数据和运算符。
由于运算符有优先级别之差.所以一个表达式的运算不可能总是从左至右的循序执行。
每次操作的数据或运算符都是最近输入的.这与栈的特性相吻合.故本课程设计借助栈来实现按运算符的优先级完成表达式的求值计算。
数据结构表达式求值在计算机科学中,数据结构是组织和存储数据的方式,而表达式求值则是一个常见且重要的任务。
表达式求值可以帮助我们计算数学表达式的结果,无论是简单的四则运算,还是复杂的包含函数和变量的表达式。
让我们从一个简单的算术表达式开始,比如“2 +3 4”。
要计算这个表达式的值,我们不能简单地从左到右依次计算,因为乘法的优先级高于加法。
所以,正确的计算顺序应该是先计算 3 4 = 12,然后再计算 2 + 12 = 14。
为了能够正确地处理表达式中不同运算符的优先级,我们需要使用特定的数据结构和算法。
其中,栈(Stack)是一种非常有用的数据结构。
栈就像是一个只能从一端进出的容器,遵循“后进先出”(Last In First Out,LIFO)的原则。
在表达式求值中,我们可以使用两个栈,一个用来存储操作数(Operand Stack),另一个用来存储运算符(Operator Stack)。
当我们读取表达式中的数字时,将其压入操作数栈;当读取到运算符时,需要和运算符栈顶的运算符比较优先级。
如果当前运算符的优先级高于栈顶运算符,那么将其压入运算符栈;如果当前运算符的优先级低于或等于栈顶运算符,就从操作数栈中弹出相应数量的操作数,进行计算,将结果压回操作数栈,然后再将当前运算符压入运算符栈。
例如,对于表达式“2 +3 4”,我们首先读取到数字 2,将其压入操作数栈。
接着读取到“+”号,此时运算符栈为空,所以将“+”号压入运算符栈。
然后读取到数字 3,压入操作数栈。
再读取到“”号,由于“”号的优先级高于“+”号,将“”号压入运算符栈。
接着读取到数字 4,压入操作数栈。
此时,表达式已经读取完毕。
因为“”号的优先级高于“+”号,所以先从操作数栈中弹出 3 和 4 进行乘法运算,得到 12,将 12 压回操作数栈。
然后从运算符栈中弹出“+”号,从操作数栈中弹出 2 和 12 进行加法运算,得到 14,这就是表达式的最终结果。
1【实验题目及要求】[问题描述]一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。
假设操作数是正实数,运算符只含加减乘除等四种运算符,界限符有左右括号和表达式起始、结束符“#”,如:#(7+15)*(23-28/4)#。
引入表达式起始、结束符是为了方便。
编程利用“算符优先法”求算术表达式的值。
[基本要求](1)从键盘或文件读入一个合法的算术表达式,输出正确的结果。
(2)显示输入序列和栈的变化过程。
(3)考虑算法的健壮性,当表达式错误时,要给出错误原因的提示。
(4) 实现非整数的处理(可选功能)。
2【源代码(C语言)】#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAXSIZE 20#define OK 1#define ERROR 0#define OVERLOW 0#define YES 1#define NO 0typedefstruct{char * base;char * top;int stacksize; //最大存储量}OPTR; //字符存储栈typedefstruct{float *base;float *top;int stacksize; //最大存储量}OPND; //数值存储栈int InitOptrStack(OPTR *); //字符栈初始化函数int OptrPush(OPTR *, char); //进字符栈操作int OptrPop(OPTR*, char *); //出字符栈操作int OptrEmpty(OPTR ); //判断字符栈是否为空char GetOptrTop(OPTR); //返回字符栈顶元素int InitOpndStack(OPND *); //数值栈初始化函数int OpndPush(OPND *, float); //进数值栈操作int OpndPop(OPND*, float*); //出数值栈操作int OpndEmpty(OPND ); //判断数值栈是否为空int JudgeChar(char); //判断是否为字符float GetFloat(char *); //接收一个数字char Precede(char, char); //判断优先级操作float Caculate(float,float,char);//计算数值{char ch, noMean, ci;float num, number1, number2;OPTR optr;OPND opnd;//system("color 30");InitOptrStack(&optr);InitOpndStack(&opnd);while(1){printf(" 请输入表达式以“#”开始,以“#”结束\n ");do{ch = getchar();}while(ch !='#'); //忽略前面非‘#’字符OptrPush(&optr, ch);ch = getchar();while(ch != '#' || GetOptrTop(optr) != '#'){if(!JudgeChar(ch)){ //如果输入的是数字num = GetFloat( &ch );OpndPush(&opnd, num);else{ //输入的是字符switch(Precede(GetOptrTop(optr),ch)){case'<':OptrPush(&optr,ch); //栈顶优先级低ch = getchar();break;case'=':OptrPop(&optr,&noMean); //左右括号,把左括号出栈ch = getchar ();break;case'>': //栈顶优先级高if(OpndPop(&opnd, &number2) && OpndPop(&opnd,&number1)){OptrPop(&optr, &ci);num = Caculate(number1, number2, ci ); //出栈计算OpndPush(&opnd, num);}else{printf(" 输入过多运算符!\n");system ("PAUSE");exit(0);}break;}//witch}//else}if(opnd.top -opnd.base >= 2){printf(" 俩个括号之间缺少运算符!\n ");system ("PAUSE");exit( 0 );}OpndPop(&opnd,&num); //直接把OPND的栈元素赋值给numprintf(" 运算结果为%.3f\n", num);}system ("PAUSE");}int InitOptrStack(OPTR * OP){OP->base = (char*)malloc((MAXSIZE+1)*sizeof(char));OP->top = OP->base;OP->stacksize = MAXSIZE;return OK;}int OptrPush(OPTR *OP, char ch){*(OP->top) = ch;OP->top++;return OK;}int OptrPop(OPTR *OP, char *ch){if(OP->base == OP->top)return ERROR;else{OP->top--;*ch = *(OP->top);return OK;}}int OptrEmpty(OPTR OP){if(OP.top == OP.base )return YES;elsereturn NO;}char GetOptrTop(OPTR OP){return *(OP.top -1);}int InitOpndStack(OPND * OP){if(!(OP->base = (float*)malloc((MAXSIZE+1)*sizeof(float)))) exit(OVERLOW);OP->top = OP->base;OP->stacksize = MAXSIZE;return OK;}int OpndPush(OPND *OP, float number) {*(OP->top) = number;OP->top++;return OK;}int OpndPop(OPND *OP, float* number) {if(OP->top == OP->base)return ERROR;else{OP->top--;*number = *(OP->top);return OK;}}int OpndEmpty(OPND OP){if(OP.top == OP.base )return YES;elsereturn NO;}int JudgeChar(char ch){if(ch>='0'&&ch<= '9')return NO;elsereturn YES;}float GetFloat(char* ch){int i;float num = 0;for( i = 0; *ch>= '0'&& *ch<= '9'; i++){ num = num*10 + *ch - '0';*ch = getchar();}return num;}char Precede(char a, char b){char ch;switch(a){case'+':case'-': if(b == '*' || b == '/' || b == '(')ch = '<';elsech = '>';break;case'*':case'/': if( b == '(')ch = '<';elsech = '>';break;case'(': if(b == ')')ch = '=';elseif(b == '#'){printf(" 缺少反括号\n");system ("PAUSE");exit(0);}elsech = '<';break;case')': if(b == '('){printf(" 两个括号之间没有符号相连!\n");system("PAUSE");exit(0);}ch = '>';break;case'#': if(b == '#')ch = '=';elseif(b == ')'){printf(" 没有左括号!\n ");system("PAUSE");exit(0);}elsech = '<';break;default: printf(" 输入运算符超出范围! \n ");system ("PAUSE");exit(0);break;}return ch;}float Caculate(float number1, float number2, char ci){float num;switch( ci){case'+': num = number1 + number2; break;case'-': num = number1 - number2; break;case'*': num = number1 * number2; break;case'/': num = number1 / number2; break;}return num;}3【算法思想】根据栈的原理,建立数字栈OPND和运算符号栈OPTR,对读入的字符进行判断,存入不同的栈内,每次读入一个字符就把该字符和运算符栈顶的优先级进行比较,然后选择相应的操作,这是这个程序的核心代码,如下:switch(Precede(GetOptrTop(optr),ch)){case '<':OptrPush(&optr,ch); //栈顶优先级低ch = getchar();break;case '=':OptrPop(&optr,&noMean); //左右括号,把左括号出栈ch = getchar ();break;case '>': //栈顶优先级高if(OpndPop(&opnd, &number2) && OpndPop(&opnd, &number1)){OptrPop(&optr, &ci);num = Caculate(number1, number2, ci ); //出栈计算OpndPush(&opnd, num);}else{printf(" 输入过多运算符!\n");system ("PAUSE");exit(0);}break;}//witch4【实现效果】完全可以实现题目的要求,除了下图的错误提示,本程序还可以提示的错误有:输入过多运算符,缺少反括号,两个括号之间缺少运算符相连,缺少左括号,输入的运算符超出范围等提示。
目录1 题目的内容及要求 (2)2 需求分析 (2)3 概要设计 (2)4 详细设计 (4)5 源代码 (6)6 运行结果及分析 (13)7 收获及体会 (14)1 题目的内容及要求从文件读取表达式,判断表达式是否合理,将表达式转换成后缀形式,按后缀表达式求值;题目涉及加减乘除,带括弧的混合运算;随时可以退出。
2 需求分析利用栈设计一个程序,该程序能够用于表达式求值,程序将读入的中缀表达式转换为后缀表达式,然后读取后缀表达式,输出结果。
本程序具有检测表达式语法是否正确的功能,如果表达式出现错误的时候,程序会提示操作人员执行的表达式不合理,语法是不能执行的。
语法正常的情况下,程序可以实现了加、减、乘、除以及带括号的基本运算。
程序在执行表达式的时候,先检查表达式是否合理,不合理则输出表达式不符合要求,合理则将中缀表达式转化为后缀表达式,然后则对表达式求值,输出结果。
3 概要设计本程序选用的是线性表数据结构。
它按照后进先出的原则存储数据,先进的数据被压入栈底,最后的数据在栈顶,需要度数据的时候才栈顶开式探出数据。
程序采用的是顺序存储结构,可以将逻辑上相邻的数据元素在物力上相邻的存储单元里,节电之间的关系由存储单元相邻的关系来决定。
选择线性表结构是因为程序是用栈来设计的,可以将优先运算的送至栈顶,低级别的运算则最后根据先后进栈的顺序来执行。
选择顺序存储结构是因为顺序存储结构存取数据数度快,占用的存储空间小。
系统的功能模块划分:Translate()的功能是将中缀表达式转换为后缀表达式DispPostfix()的功能是输出后缀表达式ProcessExpress()的功能是将原表达式进行预处理,检查符号是否匹配,转化为中缀式。
endright的功能是先对表示式的运算符进行处理,考虑其计算的优先级。
FindSymbol()的功能是对表达式的括号进行优先处理。
FindWord()的功能是检查表达式是否有语法错误。
操作之间的调用关系:各个函数是通过主函数main()来调用的,当程序接受一段表达式的时候,先通过ProcessExpress()对整个表达式做一个运算的预处理,转化为中缀式。
FindWord()检查表达式是否出现可以执行,然后送入FindSymbol()进行处理,带括号的运算优先处理,之后endright函数检查表达式的优先级,高级的运算先进行处理。
接着Translate()函数把表达式转换为后缀式。
DispPostfix()的功能是输出后缀表达式。
计算表达式。
最后主函数输出计算结果。
系统流程图:开始输入表达式表达式是否合法将表达式转换为后缀式计算输出计算结果结束4 详细设计在计算机中,算数表达式的计算通常是通过使用栈来实现的。
所以表达式求值程序最主要的数据结构就是栈。
可以使用栈来存储输入表达式的操作符和操作数。
输入的表达式是由操作数和操作符以及改变运算次序的括号连接而成的。
(1)本程序通过DispPostfix()的功能是输出后缀表达式。
将中缀式转化为后缀式,要将遇到的运算对象直接放入后缀式的存储区。
将刚读入的字符送至操作数栈,如果遇到运算符则送入运算符栈。
通过栈的先后进栈的顺序来将操作数和操作符进行出栈,然后输出后缀表达式。
void DispPostfix(){ int i;printf(" 后缀表达式:");for (i=0;i<=postlength;i++){ if (strcmp(lexicon[postfix[i]].name,"number")==0)printf("%g ",lexicon[postfix[i]].info.val);elseprintf("%s ",lexicon[postfix[i]].name); } }(2)程序通过FindSymbol()的功能是对表达式的括号进行优先处理。
该函数使用栈的方法,来解决表达式中带括号的进行先处理,当两个栈都处于一个优先级的是时候,说明表达式出现左右括号,进行优先运算。
对表达式的括号优先处理。
int FindSymbol(char str[],int pos){ int h,k;char word[MAXTOKEN];word[0]=str[pos];word[1]='\0';pos++;if ((h=hashtable[Hash(word)])==-1){ printf("表达式中存在不能识别的符号\n");return -1; }else if (Leading()==1){ if (Kind(h)==RIGHTPAREN){ printf("不应为右括号\n");return -1; }else if (Kind(h)!=BINARYOP)PutToken(h);else{ if (strcmp(word,"+")==0);else if (strcmp(word,"-")==0)PutToken(hashtable[Hash("~")]);else{ printf(" >>二元运算符不正确\n");return -1; } } }else{ if (Kind(h)==BINARYOP || Kind(h)==RIGHTPAREN)PutToken(h);else { printf("二元运算符不正确\n");return -1; } }if ((k=Kind(h))==LEFTPAREN)parencount++;else if (k==RIGHTPAREN)if (--parencount<0){ printf("太多的右括号\n");return -1;}return pos;}(3)FindWord()的功能是检查表达式是否有语法错误。
通过主函数调用后,对表达式进行语法差错。
当语法出现错误时,则通过return()=0,f返回到主函数,报告表达式出错。
输出结果,表达式出错。
当表达式是合理的时候,该函数运行结束,则停止调用,进入主函数。
实现下一个函数的调用。
int FindWord(char str[],int pos){ int h;char word[MAXTOKEN];pos=ExtractWord(str,pos,word);h=hashtable[Hash(word)];if (h!=-1){ if (Leading()==1){ if (Kind(h)==BINARYOP){printf("二元运算符位置不正确\n");return -1; }elsePutToken(h);}else{ if (Kind(h)!=BINARYOP){ printf("应为二元运算符\n");return -1; }elsePutToken(h); }return pos; }else { printf(" >>不正确的标识符\n");return -1; } }int FindNumber(char str[],int pos){ if (Leading()==0){ printf("常量位置不正确\n");return -1;}else{ lexicon[++tokencount].kind=OPERAND;lexicon[tokencount].info.val=atof(&str[pos]);strcpy(lexicon[tokencount].name,"number");PutToken(tokencount);for (;isdigit(str[pos]) || str[pos]=='.';pos++);return pos; } }5 源代码#include<stdio.h>#include<string.h>#include<ctype.h>#include<math.h>#define MAXNAME 7#define MAXPRIORITY 6#define MAXTOKEN 100#define MAXSTACK 100#define MAXSTRING 101#define HASHSIZE 101#define LASTOPERAND 17typedef double Value_type;typedef enum kind_tag {UNARYOP,BINARYOP,OPERAND,LEFTPAREN,RIGHTPAREN,ENDEXPR} Kind_type; typedef struct{ char name[MAXNAME];Kind_type kind;union{ int pri;Value_type val;} info;} Token_type;Token_type lexicon[MAXTOKEN]={{"#",ENDEXPR},{"(",LEFTPAREN},{")",RIGHTPAREN},{"~",UNARYOP,6},{"abs",UNARYOP,6},{"sqrt",UNARYOP,6},{"exp",UNARYOP,6},{"ln",UNARYOP,6},{"log10",UNARYOP,6},{"sin",UNARYOP,6},{"cos",UNARYOP,6},{"tanh",UNARYOP,6},{"+",BINARYOP,4},{"-",BINARYOP,4},{"*",BINARYOP,5},{"/",BINARYOP,5},{"%",BINARYOP,5},{"^",BINARYOP,6}};int hashtable[MAXTOKEN];int infix[MAXTOKEN];int postfix[MAXTOKEN];int inlength;int postlength;int parencount;int tokencount;int Hash(char *name){ int h=name[0] % HASHSIZE;while (1){ if (hashtable[h]==-1)break;else if (strcmp(lexicon[hashtable[h]].name,name)==0) break;else{ if (name[1]=='\0')h+=31;elseh+=name[1];h%=HASHSIZE; } }return abs(h); }void MakeHashTable(){ int i;for (i=0;i<HASHSIZE;i++)hashtable[i]=-1;for (i=1;i<=LASTOPERAND;i++)hashtable[Hash(lexicon[i].name)]=i; }Kind_type Kind(int h){ return(lexicon[h].kind); }int Priority(int h){ return(lexicon[h].info.pri); }int Leading(){ int k;if (inlength<=-1)return 1;elsereturn (k=Kind(infix[inlength]))==LEFTPAREN || k==UNARYOP || k==BINARYOP; } void PutToken(int h){ inlength++;infix[inlength]=h; }void PutToken1(int h){ postlength++;postfix[postlength]=h; }int ExtractWord(char str[],int pos,char *word){ int i;char *pw=word;for (i=pos;isalpha(str[i]) || isdigit(str[i]);i++)*pw++=tolower(str[i]);*pw='\0';return i; }int FindWord(char str[],int pos){ int h;char word[MAXTOKEN];pos=ExtractWord(str,pos,word);h=hashtable[Hash(word)];if (h!=-1){ if (Leading()==1){ if (Kind(h)==BINARYOP){printf("二元运算符位置不正确\n");return -1; }elsePutToken(h);}else{ if (Kind(h)!=BINARYOP){ printf("应为二元运算符\n");return -1; }elsePutToken(h); }return pos; }else { printf(" >>不正确的标识符\n");return -1; } }int FindNumber(char str[],int pos){ if (Leading()==0){ printf("常量位置不正确\n");return -1;}else{ lexicon[++tokencount].kind=OPERAND;lexicon[tokencount].info.val=atof(&str[pos]);strcpy(lexicon[tokencount].name,"number"); PutToken(tokencount);for (;isdigit(str[pos]) || str[pos]=='.';pos++);return pos; } }int FindSymbol(char str[],int pos){ int h,k;char word[MAXTOKEN];word[0]=str[pos];word[1]='\0';pos++;if ((h=hashtable[Hash(word)])==-1){ printf("表达式中存在不能识别的符号\n");return -1; }else if (Leading()==1){ if (Kind(h)==RIGHTPAREN){ printf("不应为右括号\n");return -1; }else if (Kind(h)!=BINARYOP)PutToken(h);else{ if (strcmp(word,"+")==0);else if (strcmp(word,"-")==0)PutToken(hashtable[Hash("~")]);else{ printf(" >>二元运算符不正确\n");return -1; } } }else{ if (Kind(h)==BINARYOP || Kind(h)==RIGHTPAREN) PutToken(h);else { printf("二元运算符不正确\n");return -1; } }if ((k=Kind(h))==LEFTPAREN)parencount++;else if (k==RIGHTPAREN)if (--parencount<0){ printf("太多的右括号\n");return -1;}return pos;}void GetToken(int &h){ inlength++;h=infix[inlength];}void GetToken1(int &h){ postlength++;h=postfix[postlength];} void Translate(){ int St[MAXSTACK];int top=-1;int h,h1;Kind_type type;postlength=-1;inlength=-1;int endright;do{ GetToken(h);switch(type=Kind(h)){ case OPERAND: PutToken1(h); break;case LEFTPAREN: top++; St[top]=h; break;case RIGHTPAREN: h=St[top];top--;while (top>-1 && Kind(h)!=LEFTPAREN){PutToken1(h);h=St[top];top--; }break;case UNARYOP:case BINARYOP: endright=0;do{ if (top==-1)endright=1;else if (Kind(St[top])==LEFTPAREN)endright=1;else if (Priority(St[top])<Priority(h))endright=1;else if (Priority(St[top])==Priority(h) && Priority(h)==MAXPRIORITY) endright=1;else{ h1=h;endright=0;h=St[top];top--;PutToken1(h);h=h1; } } while (endright==0);top++;St[top]=h;break;case ENDEXPR: while (top>-1){ h=St[top];top--;PutToken1(h); }break; } } while (type!=ENDEXPR); PutToken1(0); }int ProcessExpress(char *instring){ int len,pos;inlength=-1;parencount=0;tokencount=LASTOPERAND;len=strlen(instring);instring[len]='\0';for (pos=0;pos<len;){ if (instring[pos]==' ') pos++;else if (isalpha(instring[pos]))pos=FindWord(instring,pos);else if (isdigit(instring[pos]) || instring[pos]=='.')pos=FindNumber(instring,pos);else pos=FindSymbol(instring,pos);if (pos==-1)return 0; }if (parencount!=0)printf("左右括号不匹配\n");PutToken(0);return 1; }void DispPostfix(){ int i;printf(" 后缀表达式:");for (i=0;i<=postlength;i++){ if (strcmp(lexicon[postfix[i]].name,"number")==0) printf("%g ",lexicon[postfix[i]].info.val);elseprintf("%s ",lexicon[postfix[i]].name); } }Value_type DoBinary(int h,Value_type x,Value_type y) { switch(h) { case 12: return(x+y);case 13: return(x-y);case 14: return(x*y);case 15: if (y!=(Value_type)0)return(x/y);else{ printf(" >>除零错误\n"); break; }case 16: if (y!=(Value_type)0)return(fmod(x,y));else{ printf(" >>除零错误\n"); break; }case 17: return(pow(x,y));default: printf(" >>%d是无效的二元运算符\n",h); break; } }Value_type DoUnary(int h,Value_type x){ switch(h) { case 3: return(-x);case 4:return(abs(x));case 5: if (x>=0)return(sqrt(x));else{ printf(" >>负数不能开平方\n");break; }case 6: return(exp(x));case 7: if (x>0)return(log(x));else{ printf(" >>负数不能求ln\n");break; }case 8: if (x>0)return(log10(x));else{printf(" >>负数不能求log10\n"); break;}case 9: return(sin(x));case 10: return(cos(x));case 11: return(tanh(x)); } }Value_type GetValue(int h){ if (Kind(h)!=OPERAND)printf(" >>不是一个操作数\n");elsereturn(lexicon[h].info.val);}Value_type EvaluatePostfix(){ Kind_type type;int h;Value_type x,y;double St[MAXSTACK];int top=-1;postlength=-1;do { GetToken1(h);switch(type=Kind(h)){case OPERAND: top++;St[top]=GetValue(h); break;case UNARYOP: x=St[top];top--;top++;St[top]=DoUnary(h,x);break;case BINARYOP: y=St[top];top--;x=St[top];top--;top++; St[top]=DoBinary(h,x,y);break;case ENDEXPR: x=St[top];top--;if (top>-1) printf(" >>不正确的表达式\n"); break;}} while (type!=ENDEXPR);return(x); };void main(){ char instring[MAXSTRING];MakeHashTable();printf("\n");printf(" 输入一个表达式:");gets(instring);while (strlen(instring)!=0){ if (ProcessExpress(instring)){ Translate(); DispPostfix();printf(" 运算结果:%g\n\n",EvaluatePostfix()); }printf(" 输入一个表达式:");gets(instring); }printf("\n"); } }6 运行结果及分析输入的表达式是合理的时候,程序会计算出结果并给出转化后的后缀式。