数据结构课程设计_表达式求值【完整版】[精品文档]

课程设计报告课程名称数据结构课程设计题目算术表达式求值指导教师设计起始日期 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)。

高级语言程序设计《算术表达式求值》课程设计报告算术表达式求值系统可以实现实现对算术四则混合运算表达式求值，并打印求值过程中运算符栈、操作数栈的变化过程。

第二章系统分析开始运行时界面如下：你可以输入一个表达式，按E对其进行求值。

#include <stdio.h>#include <conio.h>#include <stdlib.h>#include <string.h>#define N 100double numStack[N]={0};//操作数栈int numTop;char opStack[N];//运算符栈int opTop;void print_num(double str1[],int n) {int i;printf("\n操作数栈：\n");for(i=0;i<n;i++)printf("%g ",str1[i]);}void print_op(char str2[],int m) {int j;printf("\n运算符栈：\n");for(j=0;j<m;j++)printf("%c ",str2[j]);}int op(char ch)//判断运算符优先级{if(ch=='+'||ch=='-') return 2;if(ch=='*'||ch=='/') return 3;if(ch=='(') return -1;return 0;}double result(double num1,char op,double num2)//计算{if(op=='+') return num1+num2;if(op=='-') return num1-num2;if(op=='*') return num1*num2;if(op=='/') return num1/num2;return 0;}int compute(char str[]){double num=0;int i=0,j=1,k=1;numTop=opTop=0;while(str[i]!='\0'||opTop>0){if(str[i]>='0'&&str[i]<='9')num=num*10+str[i]-'0';else if( k==1&&str[i]=='-'&&(i==0||op(str[i-1])) )k=-1;else{if(i>0&&!op(str[i-1])&&str[i]!='('&&str[i-1]!=')') {numStack[numTop++]=num*k;if(opTop!=0&&numTop!=0)print_num(numStack,numTop);num=0; j=1; k=1;}if(opTop==0||str[i]=='('){opStack[opTop++]=str[i];print_op(opStack,opTop);}else if(str[i]==')'){while(opTop>0&&opStack[--opTop]!='('){numStack[numTop-2]=result(numStack[numTop-2],opStack[opTop],numStack[numTop-1]);if(opTop!=0&&numTop!=0){print_num(numStack,numTop);print_op(opStack,opTop);}numTop--;}if(opStack[opTop]!='(') return 0;}else{if(str[i]=='\0'&&numTop==0) return 0;while(opTop>0&&op(str[i])<=op(opStack[opTop-1])){numStack[numTop-2]=result(numStack[numTop-2],opStack[--opTop],numStack[numTop-1]);if(opTop!=0&&numTop!=0){print_num(numStack,numTop-1); print_op(opStack,opTop);}numTop--;}if(str[i]!='\0')opStack[opTop++]=str[i];if(opTop!=0&&numTop!=0)print_op(opStack,opTop);}}if(str[i]!='\0')i++;}if(numTop!=1||opTop!=0)return 0;return 1;}void menu(){system("cls");printf("_______________________________\n");printf(" Clear(C) | Equal(E) | Quit(Q) \n");printf("-------------------------------\n");}int main(void){int i=0,j=0,k;char str[N]="\0";char num[N]="\0";char save[N]="\0";char ch;double temp;unsigned long temp2;menu();printf("input an expression,press key 'E' to compute\n");ch=getch();while( 1 ){if(ch==')'||op(ch)||ch>='0'&&ch<='9'){str[i++]=ch;str[i]='\0';menu();printf("input an expression,press key 'E' to compute\n"); printf("%s",str);if( ch=='-'&&(i==1||op(str[i-2]))||ch>='0'&&ch<='9' ){num[j++]=ch;num[j]='\0';}elsej=0;}if(ch=='C'||ch=='c'){if(strlen(str))str[--i]='\0';menu();printf("input an expression,press key 'E' to compute\n");printf("%s",str);}if(ch=='E'||ch=='e'){if(compute(str)){printf("\n=%g\n",numStack[0]); j=0; temp=numStack[0];if(temp<0){temp=-temp;num[j++]='-';num[j]='\0';}temp2=(unsigned long)temp;k=1;while(temp2/k>=10) k*=10;while(k){num[j++]=temp2/k+'0';num[j]='\0';temp2=temp2%k;k/=10;}temp=temp-(int)temp;if(temp!=0){num[j++]='.';num[j]='\0';temp+=0.0000005;}for(k=6;k>0;k--){if(temp==0) break;temp*=10;num[j++]=(int)temp+'0';num[j]='\0';temp=temp-(int)temp;}}i=0; j=0; str[0]='\0';}if(ch=='Q'||ch=='q'){printf("\nare you sure to quit?（Y/N）\n");ch=getch();if(ch=='Y'||ch=='y') break;else{menu();printf("input an expression,press key 'E' to compute\n");printf("%s",str);}}ch=getch();}return 0;}第五章系统测试1.先输入： 3+2*5 后按E求值2.再输入：12/4-5 后按E求值3.再输入Q4.输入Y，退出系统。

《数据结构》课程设计利用栈求表达式的值班级： 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）。

ＸＸXＸXX大学《数据结构》课程设计报告班级：学号：姓名：指导老师:目录一算术表达式求值一、需求分析二、程序得主要功能三、程序运行平台四、数据结构五、算法及时间复杂度六、测试用例七、程序源代码二感想体会与总结算术表达式求值一、需求分析一个算术表达式就是由操作数(oｐeranｄ）、运算符(operator）与界限符（deｌimiter)组成得。

假设操作数就是正整数，运算符只含加减乘除等四种运算符,界限符有左右括号与表达式起始、结束符“#”，如：＃(7+15）*（2３—２8/４）#。

引入表达式起始、结束符就是为了方便.编程利用“算符优先法”求算术表达式得值.二、程序得主要功能（1）从键盘读入一个合法得算术表达式，输出正确得结果。

(2）显示输入序列与栈得变化过程。

三、程序运行平台Ｖｉsｕaｌ C＋+6、0版本四、数据结构本程序得数据结构为栈。

（1）运算符栈部分：struct SqStaｃk ／/定义栈{char *base； //栈底指针ｃｈａr *toｐ; ／/栈顶指针inｔstacｋsiｚe； //栈得长度};inｔInitSｔack (SqＳｔack &ｓ) //建立一个空栈S{ｉf （!(s、ｂａse= (char ＊）ｍalloc(5０＊ｓizeof（chａr）)）)exｉt（0）；ｓ、ｔop=s、bａse;s、staｃksiｚｅ=５0；retuｒn OK；}ｃhar GeｔTop（SqStack s,char &e) /／运算符取栈顶元素｛iｆ (s、ｔop==s、ｂase) //栈为空得时候返回EＲROR｛ﻩ prｉntf(＂运算符栈为空！＼n")；ﻩ reｔurn ERＲＯR;｝elsee＝*（s、ｔoｐ-1); //栈不为空得时候用ｅ做返回值，返回S得栈顶元素，并返回OK returnＯＫ;｝ｉnt Push(SqStacｋ＆s，cｈａr ｅ） //运算符入栈｛if （s、tｏp—s、baｓe >= ｓ、ｓtacksｉzｅ）ﻩ{ｐriｎtf（＂运算符栈满!＼n"）;ﻩs、basｅ=（cｈaｒ*）reａlloｃ(s、bａｓe，(s、sｔackｓｉze+5)*ｓizeoｆ(cｈar））；//栈满得时候,追加5个存储空间ｉf(！s、basｅ)exｉt （OVERＦＬOW）；s、top=s、ｂａsｅ+s、ｓｔacｋsize;s、ｓtaｃksiｚｅ+=５;}ﻩ＊(s、ｔop）＋＋=e；／/把e入栈ﻩｒeturn OK;}ｉnｔ Pop(SqStaｃk &ｓ，char ＆ｅ） /／运算符出栈｛ｉｆ (s、toｐ==s、base) ／/栈为空栈得时候，返回ERＲOＲ｛ｐrintf（＂运算符栈为空!\n”）;ﻩ return ERROＲ;}else｛ﻩﻩe=＊-—ｓ、tｏp；/／栈不为空得时候用e做返回值，删除S得栈顶元素，并返回ＯK return OK；}}iｎt StackTｒaｖerse（ＳqStacｋ&ｓ)／/运算符栈得遍历｛ﻩchar ＊t；ﻩt=s、ｂａｓｅ；ﻩif (s、top＝=s、baｓe）｛ﻩ printｆ（”运算符栈为空！\ｎ”)； //栈为空栈得时候返回ＥＲRORｒeturn ERＲOＲ;}ｗhile（t！＝s、tｏp)｛ﻩﻩｐrｉｎｔf（" %c",＊t)； //栈不为空得时候依次取出栈内元素t++;ﻩ}ｒeturｎ EＲRＯR；｝（2）数字栈部分：strｕｃt SqSｔackn//定义数栈｛ｉnt *bａse; //栈底指针ｉnt＊tｏp； //栈顶指针ｉnｔ sｔacksｉze； //栈得长度｝;inｔIｎｉtStackｎ (SqSｔackn &s) //建立一个空栈Ｓ{s、base=（int＊）malｌoc（50*sｉzeof(int）);if(！ｓ、ｂase）eｘiｔ（OVEＲFLＯW）；//存储分配失败s、top=s、base；s、stacksizｅ=5０;reｔuｒn OK；｝ｉｎt GｅtToｐn(ＳqＳtａcｋn s,inｔ＆e) //数栈取栈顶元素{if（s、ｔop=＝s、base）{prinｔｆ(＂运算数栈为空!\ｎ＂);//栈为空得时候返回ERRORﻩ rｅturｎ ERROR;}eｌseﻩe＝＊（s、toｐ-1);／/栈不为空得时候，用e作返回值，返回S得栈顶元素，并返回OＫreturｎＯK；｝int Pｕshn（SｑStａckn ＆s，int ｅ) //数栈入栈｛if（s、tｏp—s、ｂasｅ＞＝s、stacksiｚe)｛ﻩﻩprｉｎｔf（"运算数栈满!\ｎ"）；／/栈满得时候,追加5个存储空间ﻩs、base=(int＊）realloc (s、baｓe,(s、stａcksize＋5)＊sｉzｅof（ｉnt));ｉf（!s、base) ｅxit (ＯＶERFLOW)；ﻩs、top=ｓ、bａsｅ＋ｓ、stacｋsize;//插入元素e为新得栈顶元素s、stacksｉｚe+=5；}*（s、top）++=e; /／栈顶指针变化returｎOK;}ｉｎt Popｎ(ＳｑSｔacｋn ＆s，iｎt &e)//数栈出栈｛ﻩif （s、top=＝ｓ、base）｛ﻩ pｒiｎtｆ（"运算符栈为空！\n＂);//栈为空栈得视时候，返回ERRＯＲﻩ retｕrn ERROR；ﻩ｝ｅlse｛ﻩﻩe=＊—-ｓ、tｏp；／/栈不空得时候，则删除S得栈顶元素,用e返回其值，并返回OK ﻩreturｎOK；｝}ｉnt StacｋＴraveｒsｅn（SqStackn &s)/／数栈遍历{ﻩiｎｔ＊t;ﻩｔ=s、basｅ ;ﻩif（s、top==s、basｅ）ﻩ｛pｒinｔf(＂运算数栈为空！\n”）；//栈为空栈得时候返回ERRORﻩ rｅｔｕrn ERＲＯＲ；ﻩ｝ﻩwｈile（t！=ｓ、ｔop)ﻩ{priｎtf(” ％d”，*ｔ); /／栈不为空得时候依次输出t＋＋;｝return ERRＯR；｝五、算法及时间复杂度１、算法:建立两个不同类型得空栈,先把一个‘＃’压入运算符栈。

数据结构课程设计四则运算表达式求值（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 }。

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（）的功能是检查表达式是否有语法错误。

实验表达式求值问题1. 问题描述表达式是数据运算的基本形式。

人们的书写习惯是中缀式，如：11+22* （7-4 ）/3. 中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。

表达式还有后缀表达式（如：11 22 7 4 - * 3 / + ）和前缀表达式（+ 11 / * 22 - 7 4 3 ）。

后缀表达式和前缀表达式中没有括号，给计算带来方便。

如后缀表达式计算时按运算符出现的先后进行计算。

本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。

2. 数据结构设计1）顺序栈类定义：首先应在类中定义成员函数，以此来完成顺序栈的相关操作，如下：class SqStackprivate:T *base; // 栈底指针int top; // 栈顶int stacksize; // 栈容量public:SqStack(int m); // 构建函数~SqStack(){delete [] base;top=0;stacksize=0;} // 析构函数void Push(T x); // 入栈T Pop(); // 出栈T GetTop(); // 获取栈顶元素int StackEmpty(); // 测栈空void ClearStack(); // 清空栈void StackTop(); // 返回栈顶指针void StackTranverse(); // 显示栈中元素};2）顺序栈类实现：对顺序栈进行初始化，初始化的首要操作就是创建一个空顺序栈。

Step1 ：申请一组连续的内存空间为顺序栈使用：base=new T[m];i f(base==NULL)cout<<" 栈创建失败，退出!"<<endl; exit(1);}{Step2 ：给栈顶、栈容量赋相应的值：stacksize=m;t op=-1;（2）顺序栈入栈：入栈需要在栈顶插入一个新元素并相应的调整栈顶。

课程设计报告课程名称：数据结构课程设计设计题目：表达式求值（计算器）学院：信息科学与工程学院专业：计算机科学与技术（软件外包）姓名：指导教师：二零一五年十二月二十九日一、设计容与要求1、问题描述设计一个算术计算器，能运算包括四则运算、括号的表达式的运算。

2、设计要求实现（）、+、-、*、/、^ 等运算，实现小数和整数混合运算，优先级的处理，能判断算术表达式是否正确等。

二、算法设计1、输入并建立表达式，运用数组结构体构建将整型数字与操作符结合定义运算符的优先级。

typedef struct yxj{char operat;int rank;}yxj;2、分别建立一个操作数栈和操作符栈存放数字和操作符，定义操作符栈第一个元素优先级最低。

3、自左向右扫描字符串遇到字符串中的数字时一律提取转换成double型存入操作数栈。

遇到操作符时，则将当前运算符的优先级数与运算符栈顶元素的优先级数相比较。

若当前运算符的优先级数大，则进栈；反之，则取出栈顶的运算符，并在数栈中连续取出两个栈顶元素作为运算对象进行运算，并将运算结果存入数栈，然后继续比较当前运算符与栈顶元素的优先级。

直到当前运算符进栈。

4、对比运算符进行+ - * /（）^ 运算。

三、程序代码#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>#define N 100typedef struct yxj{char operat;int rank;}yxj;typedef struct str{char data[N];}zs;void szys(yxj mark[]){yxj os[N];char ch;double ns[N];zs zhan[20];int numb[N];int Len,p=0,q=1,i,o=1,n=0;char data[N];os[0]=mark[0];printf("请输入算术（+ - * / ^）表达式（以 = 结束）：\n");scanf("%s",data);Len=strlen(data);numb[0]=0;for(i=0;i<20;i++)zhan[i].data[0]='\0';for(i=0;i<Len;i++){int t=0;if(data[i]=='^'||data[i]=='+'||data[i]=='-'||data[i]=='*'||data[i]=='/'||data[ i]=='('||data[i]==')'||data[i]=='='){int j,k=0;if((data[i]=='='||data[i]=='^'||data[i]=='+'||data[i]=='-'||data[i]=='*'||data [i]=='/')&&(data[i-1]=='^'||data[i-1]=='+'||data[i-1]=='-'||data[i-1]=='*'||data[i -1]=='/')){printf("格式错误\n");return;}numb[q++]=i;while(zhan[(p+k)/2].data[0]!='\0'){k++;}for(j=numb[q-2];j<numb[q-1];j++)if(data[j]>='0'&&data[j]<='9'||data[j]=='.')zhan[(p+k)/2].data[t++]=data[j];zhan[(p+k)/2].data[t]='\0';if(zhan[(p+k)/2].data[0]!='\0')ns[n++]=atof(zhan[(p+k)/2].data);p++;for(j=0;j<8;j++)if(mark[j].operat==data[i])break;while(1){if(mark[j].operat=='('){os[o++]=mark[j];break;}else if(mark[j].rank>os[o-1].rank&&mark[j].operat!='(') {os[o++]=mark[j];break;}else{double numb1,numb2,numb;ch=os[--o].operat;if(ch=='+'){numb1=ns[--n];numb2=ns[--n];numb=numb1+numb2;ns[n++]=numb;}if(ch=='-'){numb1=ns[--n];numb2=ns[--n];numb=numb2-numb1;ns[n++]=numb;}if(ch=='*'){numb1=ns[--n];numb2=ns[--n];numb=numb2*numb1;ns[n++]=numb;}if(ch=='/'){numb1=ns[--n];numb2=ns[--n];if(numb1==0){printf("无效操作\n");return;}else{numb=numb2/numb1;ns[n++]=numb;}}if(ch=='^'){numb1=ns[--n];numb2=ns[--n];numb=pow(numb2,numb1);ns[n++]=numb;}}}}else if(data[i]>='0'&&data[i]<='9');else if(data[i]=='.');else{printf("格式错误，请重新输入：\n");szys(mark);break;}}printf("%lf\n",ns[0]);}int main (){yxj mark[9];mark[0].operat='#';mark[0].rank=-1;mark[1].operat='+';mark[1].rank=1;mark[2].operat='-';mark[2].rank=1;mark[3].operat='*';mark[3].rank=2;mark[4].operat='/';mark[4].rank=2;mark[5].operat='(';mark[5].rank=-1;mark[6].operat=')';mark[6].rank=-1;mark[7].operat='=';mark[7].rank=0;mark[8].operat='^';mark[8].rank=3;while(1){char i[N];printf("*****1、计算器*****\n");printf("*****0、退出 *****\n");scanf("%s",&i);if(strcmp(i,"0")==0)break;else if(strcmp(i,"1")==0)szys(mark);elseprintf("没有该选项\n");}}四、运行测试1.正常四则运算2.乘方运算3.除数为零时4.格式出现错误5.小数运算五、结论这次课程设计让我们更加了解大一学到的C和这个学期学到的数据结构。

**大学数据结构课程设计说明书学生姓名:***学号： **********学院: **********学院专业: 网络工程题目: 利用栈求表达式的值成绩指导教师******2009 年 7 月 9 日1．设计目的数据结构课程设计的目的是，通过设计掌握数据结构课程中学到的基本理论和算法并综合运用于解决实际问题中，它是理论与实践相结合的重要过程。

设计要求学会如何对实际问题定义相关数据结构，并采用恰当的设计方法和算法解决问题，同时训练学生进行复杂程序设计的技能和培养良好的程序设计习惯。

2．设计内容和要求利用栈求解表达式的值。

设计内容：1)建立试题库文件，随机产生n个题目；2)题目涉及加减乘除，带括弧的混合运算；3)利用栈求解表达式的值；4)随时可以退出；5)保留历史分数，能回顾历史，给出与历史分数比较后的评价基本要求：1)系统功能的完善；2)代码中有必要的注释3．本设计所采用的数据结构栈的数组表示方法（静态分配整型指针）typedef struct{typedef data[MAXSIZE];int top;};4．功能模块详细设计1.功能一：中缀表达式转化为后缀表达式；2.功能二：后缀表达式求值；3.功能三：文件读写；4.功能四：作业评分；5.功能五：历史成绩本次成绩比较；6.功能六：输入“~”符号退出程序4.1 详细设计思想1.首先实现表达式的求值：要用栈求解一个表达式,就要将这个表达式翻译成正确求值的一个机器指令序列,即正确解释表达式,了解算术四则混合运算的规则：(1).先乘除,后加减;(2).从左算到右;(3).先括号内,后括号外再根据这个运算优先的规定来实现对表达式的编译或解释执行.任何一个表达式都是由操作数(st)和操作符(op)组成的，根据四则运算基本法则，在运算的每一步中，任意两个相继出现的操作符op1和op2之间的优先关系最多有以下3种：(1).op1的优先级低于op2(2).op1的优先级等于op2(3).op1的优先级小于op2为实现运算符优先，可以使用两个操作栈，操作栈st,用于存放操作数及运算结果；操作栈op，用于存放操作符。

计算机科学系《数据结构课程设计》报告课题名称：算术表达式求值目录1.问题描述-----------------------------------------------------------32.基本要求-----------------------------------------------------------33.工具/准备工作----------------------------------------------------34.分析与实现--------------------------------------------------------45. 课程设计体会与感悟------------------------------------------161．问题描述从键盘上输入中缀算术表达式，包括括号，计算出表达式的值。

2.基本要求（1）程序能对所输入的表达式做简单的判断，如表达式有错，能给适当提示。

（2）能处理单目运算符：+，-。

3.工具/准备工作在开始项目之前，应回顾复习相关内容。

需要一台计算机装有visual C++。

4.分析与实现对于中缀表达式，一般运算规则如下：（1）先乘方，再乘除，最后加减；（2）同级运算从左算到右；（3）先括号内再括号外；（4）用到的头文件”utility.h”,”lk_stack.h”,”node.h”,”calculator.h”.根据实践经验，可以对运算符设置统一的优先级，从而方便比较。

表中给出了包括加、上面讨论的的+、—为双目运算符，如为单目运算符，编程实现时，可在前面加上0而转化为双目运算符。

如在+、—的前一个字符（如当前字符不是运算符时，规定用0表示）为‘=’或‘（’，则为单目运算符。

具体实现算法时，可设置两个工作栈，一个为操作栈，一个为操作符栈optr，另外一个为操作数栈opnd,算法基本思路如下：（1）将optr栈和opnd栈清空，在optr栈中加入一个‘=‘。

《计算表达式》课程设计报告标题：计算表达式单位：报告人：指导教师：编程环境：VC6时间：2011年12月20日一、设计要求对于输入的一个中缀表达式，判断表达式是否合法。

如果合法，把中缀表达式转换成一棵二叉树，然后通过后根遍历计算表达式的值，输出运算结果。

合法表达式不能为空，可以出现在表达式中的字符有：*运算符“+”、“-”、“*”、“／”；*左右括号“(”、“)”；*整数(可以是多位的)；*空格符和制表符。

例如：表达式为“20+(3*(4+46)-6)／2-134”将得到结果-42。

数据结构采用二叉树的链接表示。

二、题目分析由设计要求可以确定程序的几大模块，读入源程序（1）读入中缀表达式（2）从中缀表达式ex(长度为n)创建二叉树（3）后根遍历计算表达式的值（4）输出运算结果进一步确定几个子程序及其相互之间的调用关系为：三．流程图四．全局变量与子程序功能说明（1）int extoBinTree(PBinTree pbtree,const char *ex,int n)从中缀表达式ex(长度为n)创建二叉树。

若是一个合法的表达式，则返回TRUE，且算法结束时*pbtree存放二叉树的根节点的地址；否则返回FALSE（2）int cal(BinTree btree,int*presult)计算二叉树btree所代表的表达式的值。

若是一个合法的表达式，则返回TRUE，且算法结束时*presult中存放计算结果；否则，返回FALSE.（3）void delete_BTree(PBinTree ptree){BinTree temp=(*ptree);if(temp==NULL) return;delete_BTree(&(temp->llink));delete_BTree(&(temp->rlink));free(temp);}作用为，当输入的程序有误时，或者一段表达式已经运算结束时清除储存空间，为下一段表达式的计算作准备。

目录1．前言 (2)2．问题描述 (3)3．总体设计··········································································错误!未定义书签。

3.1 概要设计 ······································································错误!未定义书签。

数据结构课程设计报告(二)表达式求值(计算器).课程设计报告课程名称：数据结构课程设计设计题目：表达式求值（计算器）学院：信息科学与工程学院专业：计算机科学与技术（软件外包）姓名：指导教师：二零一五年十二月二十九日word教育资料.一、设计内容与要求1、问题描述设计一个算术计算器，能运算包括四则运算、括号的表达式的运算。

2、设计要求实现（）、+、- 数据结构课程设计设计题目：表达式求值（计算器）学院：信息科学与工程学院专业：计算机科学与技术（软件外包）姓名：指导教师：二零一五年十二月二十九日word教育资料.一、设计内容与要求1、问题描述设计一个算术计算器，能运算包括四则运算、括号的表达式的运算。

2、设计要求实现（）、+、：\n"); scanf("%s",data); Len=strlen(data); numb[0]=0; for(i=0;i20;i++) zhan[i].data[0]='\0'; for(i=0;i='0'data[i]='9'); else if(data[i]=='.'); else { printf("格式错误，请重新输入：\n"); szys(mark); break; } } printf("%lf\n",ns[0]);}int main (){ yxj mark[9]; mark[0].operat='#'; mark[0].rank=-1; mark[1].operat='+'; mark[1].rank=1; mark[2].operat='-'; mark[2].rank=1; mark[3].operat='*'; mark[3].rank=2; mark[4].operat='/'; mark[4].rank=2; mark[5].operat='('; mark[5].rank=-1; mark[6].operat=')'; mark[6].rank=-1; mark[7].opera该选项\n"); }}四、运行测试1.正常四则运算2.乘方运算3.除数为零时4.格式出现错误5.小数运算五、结论这次课程设计让我们更加了解大一学到的C和这个学期学到的数据结构。

课程设计报告课程名称：数据结构课程设计课程设计题目：表达式求值问题姓名：余明旭系：计算机科学与技术专业：计算机科学与技术年级：2010级学号：100310236指导教师：陈老师职称：学生详细设计此算法的基本思想：首先置操作数栈OPS为空栈，表达式起始符“#”为运算符的栈底元素；依次读入表达式中每个字符，若是操作数则进栈，若是运算符则和OPF栈的栈顶运算符比较优先权作相应操作，直至整个表达式求值完毕（即OPF栈的栈顶元素和当前读入的字符均为“#”）此算法的伪代码：ElementType EvaluateExpression(char *exp){ 定义两个字符变量c和ch,c代表输入表达式中的字符，ch代表栈顶运算符;定义字符指针*p,*q,*temp;temp指向运算符后面的一个字符double i=0,a=0,b=0;将传入的实参赋给p,q;定义一个运算符栈OPF;定义一个操作数栈OPS;调用函数InitStack()初始化栈OPS;调用函数CInitCharStack()初始化栈OPF;调用函数CPush(OPF,'#')将#压入运算符栈;c=*p;temp=p;p++;if(第一个字符就为‘-’){c=*p;temp=p;p++;}while(栈不为空或表达式没有结束){//进入最外层循环if(不是运算符)//则解析数字字符串然后进操作数栈{整数部分m=0;小数部分n=0;while(没有遇到小数点并且为数字字符){ 解析整数部分m }if(遇到小数点){ 解析小数部分c=*p;将p指针移到第一个出现的字符;将q指针指向小数的最后一位;while(p指针不指向’.’){将p指向的字符转为小数np--;}p=q;p++;}if(运算符为‘-’并且运算符前一个为‘（’或者为表达式的开始)调用Push(OPS,-(m+n))将m+n的相反数入栈;else调用Push(OPS,m+n)将m+n入栈;}数字进栈结束else//是运算符时则进栈OPF{ if(运算符为‘-’&&运算符前一个为‘（’){ c=*p;temp=p;p++;}else{ 调用函数CGetTop(OPF,ch)得到OPF的栈顶元素;switch(调用函数Precede(ch,c)判断栈顶元素与接收的字符的优生级别) {case 栈顶运算符优先权低:调用函数CPush(OPF,c)将c入运算符栈;接收下一个字符;case 栈顶运算符优先权高：运算符出栈得到ch;数字栈连续出栈两次得到a,b ;调用Operate(a,ch,b)并将结果入栈到数字栈;break;case 优生权相等：脱括号并接收下一个字符;调用CPop(OPF,ch)脱括号;接收下一个字符;default:接收下一个字符;}退出switch循环}//else1}//else2}//退出最外层while循环调用函数GetTop(OPS,i)得到栈顶元素i;将两个栈消毁;}EvaluateExpression函数结束源代码#include<stdlib.h># include <stdio.h># include <string.h>#define ERROR 0#define OK 1#define TRUE 1#define FALSE 0typedef char ElemType;typedef int Status;typedef double ElementType;typedef int Status;# define STACK_INIT_SIZE 30# define STACKINCREAMENT 10# define NUMBER 30typedef struct node{ElementType data;struct node *next;}StackNode, *LinkStack;void InitStack(LinkStack &head){head=(LinkStack)malloc(sizeof(StackNode));head->next=NULL;}Status IsEmpty(LinkStack head){if(head->next==NULL)return TRUE;else return ERROR;}Status Push(LinkStack &head,ElementType element){//入栈LinkStack p;p=(LinkStack)malloc(sizeof(StackNode));if(p== NULL) return FALSE;p->data=element;p->next=head->next;head->next=p;return OK;}Status Pop(LinkStack &head,ElementType &element){//出栈if(IsEmpty(head))return FALSE;LinkStack temp=head->next;element=temp->data;head->next=temp->next;free(temp);return OK;}Status GetTop(LinkStack head, ElementType &element){ if(head->next==NULL)return ERROR;element =head->next->data;return OK;}Status DestroyStack(LinkStack &head){LinkStack q;while(head){q=head->next;free(head);head=q;}return TRUE;}//这个栈是用来存储符号字符的typedef struct node1{ElemType data;struct node1 *next;}StackCharNode,*LinkCharStack;void CInitCharStack(LinkCharStack &head){head=(LinkCharStack)malloc(sizeof(StackCharNode));head->next=NULL;}Status CIsEmpty(LinkCharStack head){return (head->next==NULL)?TRUE:FALSE;}Status CPush(LinkCharStack &head,ElemType element){LinkCharStack temp=(LinkCharStack)malloc(sizeof(StackCharNode));if(!temp)return ERROR;temp->data=element;temp->next=head->next;head->next=temp;return TRUE;}Status CPop(LinkCharStack &head,ElemType &element){if(CIsEmpty(head))return FALSE;StackCharNode *temp=head->next;element=temp->data;head->next=temp->next;free(temp);return TRUE;}Status CGetTop(LinkCharStack head,ElemType &element){if(head->next!=NULL){element=head->next->data;return TRUE;}element='#';return FALSE;}Status CDestroyStack(LinkCharStack &head){LinkCharStack q;while(head){q=head->next;free(head);head=q;}return TRUE;}//判断ch是否为运算符int Comop(char ch){switch(ch){case '+':case '-':case '*':case '/':case '(':case ')':case '[':case ']':case '{':case '}':case '#':return 1;default:return 0;}}//Comop//比较两个运算符的优先级char Precede(char ch,char c)//ch是栈顶字符,c 是表达式字符{switch(ch){case '+':case '-':if(c=='+'||c=='-'||c==')'||c=='#'||c==')'||c==']'||c=='}')return '>';if(c=='*'||c=='/'||c=='('||c=='['||c=='{')return '<';case '*':case '/':if(c=='+'||c=='-'||c=='*'||c=='/'||c==')'||c==']'||c=='}'||c=='#')return '>';if(c=='('||c=='['||c=='{')return '<';case '(':if(c=='+'||c=='-'||c=='*'||c=='/')return '<';if(c==')')return '=';case ')':if(c=='+'||c=='-'||c=='*'||c=='/'||c==']')return '>';if(c=='#')return '>';case'[':if(c=='+'||c=='-'||c=='*'||c=='/'||c=='(')return '<';if(c==']')return '=';case']':if(c=='+'||c=='-'||c=='*'||c=='/'||c=='}')return '>';if(c=='#')return '>';case'{':if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c=='[')return '<';if(c=='}')return '=';case'}':if(c=='+'||c=='-'||c=='*'||c=='/')return '>';if(c=='#')return '>';case '#':if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c=='['||c=='{')return '<';if(c=='#')return '=';default:return '$';}}//precede//运算函数ElementType Operate(ElementType a,char ch,ElementType b){switch(ch){case '+':return a+b;case '-':return a-b;case '*':return a*b;case '/':if(b==0){return -32767;}return a/b;default:return -32767;}}//Operate//错误提示函数int error(char *str){int i=0;while(str[i]!='#') //主要通过判断所有输入的字符数组str[30]{if( ((str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/'||str[i]=='.')&& //其它函数只要一声明err=1也就说明输入有误(str[i+1]==')'||str[i+1]==']'||str[i+1]=='}'))||((str[i]=='+'||str[i]=='*'||str[i]=='/'||str[i]=='.')&&(str[i-1]=='('||str[i-1]=='['||str[i-1]=='{'))||((str[i]==')' || str[i]==']'||str[i]=='}')&& str[i+1]=='.')||(str[i]=='.' &&( str[i+1]=='('||str[i+1]=='['||str[i+1]=='{'))||(str[i]==')' && str[i+1]=='(')||(str[i]=='(' && str[i+1]==')')||(str[i]=='[' && str[i+1]==']')||(str[i]==']' && str[i+1]=='[')||(str[i]=='{' && str[i+1]=='}')||(str[i]=='}' && str[i+1]=='{')||((str[i]==')'||str[i]==']'||str[i]=='}') && str[i+1]>='0'&&str[i+1]<='9')||((str[i]>='0'&&str[i]<='9'&& (str[i+1]=='('||str[i+1]=='['||str[i+1]=='{'))||(str[0]=='+'||str[0]=='*'||str[0]=='/'||str[0]==')'||str[0]==']'||str[0]=='}')||((str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/'||str[i]=='.')&&(str[i+1]=='+'||str[i+1]=='-'||str[i+1]=='*'||str[i+1]=='/'||str[i+1]=='.'))||(int(str[i])>57&&(int(str[i])!=91 && int(str[i])!=93 && int(str[i])!=123 && int(str[i])!=125))||(str[i]=='/' && str[i+1]=='0')||(int(str[i])>31 && int(str[i])<38)))return 1;else if(str[i]=='#')return 0;i++;}//whilereturn 0;}//错误提示函数//表达式计算函数ElementType EvaluateExpression(char *exp){char c,ch; //c代表输入表达式中的字符，ch代表栈顶运算符char *p,*q,*temp;//temp指向运算符后面的一个字符double i=0,a=0,b=0;p=q=exp;LinkCharStack OPF;//运算符栈LinkStack OPS;//操作数栈CInitCharStack(OPF);CPush(OPF,'#');InitStack(OPS);c=*p;temp=p;p++;if(c=='-'){c=*p;temp=p;p++;}while(c!='#'||!CIsEmpty(OPF)) //栈不为空或表达式没有结束{//*********************进入最外层循环********************* if(!Comop(c))//不是运算符则解析数字字符串然后进操作数栈{double m=0,n=0;while(c!='.'&&c>='0'&&c<='9'){//解析整数部分m=m*10+(c-48);c=*p;p++;}if(c=='.'){//解析小数部分c=*p;while(c>='0'&&c<='9'){p++;c=*p;}q=p;p--;while(*p!='.'){n=n/10+(*p-48)/10.0;p--;}p=q;p++;}if(*(temp-2)=='('&&*(temp-1)=='-'||temp-1==exp) Push(OPS,-(m+n));elsePush(OPS,m+n);}//*****数字进栈结束******else//是运算符时则进栈OPF{if(c=='-'&&*(p-2)=='('){c=*p;temp=p;p++;}else//else1{CGetTop(OPF,ch);switch(Precede(ch,c)){case '<'://栈顶运算符优先权低CPush(OPF,c);c=*p;temp=p;p++;break;case '>'://栈顶运算符优先权高CPop(OPF,ch);Pop(OPS,b);Pop(OPS,a);Push(OPS,Operate(a,ch,b));break;case '='://脱括号并接收下一个字符CPop(OPF,ch);c=*p;temp=p;p++;break;default:c=*p;temp=p;p++;}//switch}//else1}//else2}//退出最外层循环GetTop(OPS,i);DestroyStack(OPS);CDestroyStack(OPF);return i;}//EvaluateExpression函数结束//菜单函数void MenuPrint(){printf("\t\t┌─────────┐\n");printf("\t\t│多功能计算器│\n");printf("\t\t├(a)表达式求解│\n");printf("\t\t├(b)清屏│\n");printf("\t\t├(c)退出│\n");printf("\t\t└─────────┘\n");} //菜单函数//清屏函数void Clear(){ system("cls");MenuPrint();}//清屏函数//main主函数void main(){double result=0;char exp[NUMBER],c;freopen("DS1.in", "r", stdin);freopen("DS1.out", "w", stdout);Clear();printf("\t\t请输入你要进行的操作:\n");while(1){scanf("%c",&c);switch(c){ case 'a':Clear();sr:printf("输入要计算的表达式，以##结束\n");scanf("%s",exp);if(!error(exp)){ result=EvaluateExpression(exp);printf("计算结果为：%lf\n",result);printf("请根据屏幕提示选择要进行的操作：\n");scanf("%d",&c);break;}else if(error(exp)){printf("您输入的表达式有误！");goto sr;}case 'b':Clear();printf("\t\t请输入你要进行的操作:");scanf("%d",&c);break;break;case 'c':system("cls");exit(1);default:printf("输入有误！");}//switch}//while}//main调试分析与结果测试数据组别表达式正确值1 12+（9-8）*7-（-6*5）492 3.14*（67.305-65.305）+3.14 9.423 3+{2*[2*(3+4)]} 314 4.3-{2.5*[9.9/(1.1+2.2)]} -3.25 12-（3-6*7）8-4 错误表达式表达式一运算结果表达式二运行结果表达式三运行结果表达式四运行结果由表二可知以上四组表达式运行结果皆正确。

课程设计(论文)题目名称表达式求值问题课程名称数据结构课程设计学生姓名XXX学号xxxxxxxxx系、专业信息工程系、信息工程类指导教师xxxxxx2020年1 月3 日目录1 问题描述 (2)2 需求分析 (2)3 概要设计 (2)3．1抽象数据类型概念 (2)3．2模块划分 (3)4 详细设计 (4)4．1数据类型的概念 (4)4．2要紧模块的算法描述 (4)5．1程序运行结果： (6)5．2程序调试与体会 (7)运用栈的大体操作顺利的解决表达式求值及转换问题，要紧利用栈的先进后出结构，执行出栈进栈操作并在出栈时进行配对并输出配对情形，而整个进程不需要不需要移动元素使程序在空间复杂度上降到最小，采纳指针的移动大大加速了程序的执行效率。

而且对输入进行了改良，以避免用户随意输入时显现的各类意想不到的错误。

系统整体上比较完美，不管是输入、输出，仍是整个系统的界面，都超级美观、简练、大方 (7)6 课程设计总结 (7)参考文献 (8)附录（源程序清单） (9)1 问题描述编写一个表达式求值程序，使输入一个四那么运算表达式后，能够返回正确的结果。

该表达式由数字0～九、+、-、*、/、括号组成，且表达式必需正确无误。

程序的编写可用到栈或队列的大体算法，求出该表达式的值，并分析算法的时刻复杂度和运算的结果。

2 需求分析（1）为实现算符优先算法,能够利用两个工作栈。

一个称做OPTR，用以寄放运算符;另一个称做OPND;用以寄放操作数或运算结果。

算法的大体思想是：①第一置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素;②依次读入表达式中每一个字符,假设是操作数那么OPND栈,假设是运算符,那么和OPTR栈的栈顶运算符比较优先权后做相应操作,直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为"#")。

（2）该程序实现表达式的求值问题：从键盘读入一个合法的算术表达式，利用算符优先关系，实现对算术四那么混合运算的求值，输出正确的结果。