利用栈求表达式的值,可供小学生作业,并能给出分数

数据结构课程设计可选题目一、课程设计的目的学习数据结构与算法的最终目的是解决实际的应用问题，特别是非数值计算类型的应用问题。

课程设计要求同学独立完成一个较为完整的应用需求分析，在完成设计和编程大型作业的过程中，深化对数据结构与算法课程中基本概念、理论和方法的理解；训练综合运用所学知识处理实际问题的能力，强化面向对象的程序设计理念；使同学的程序设计与调试水平有一个明显的提高。

二、数据结构课程设计可选题目1. 运动会分数统计（限1 人完成）任务：参加运动会有n个学校，学校编号为1……n。

比赛分成m个男子项目，和w个女子项目。

项目编号为男子1……m，女子m+1……m+w。

不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。

（m<=20,n<=20）功能要求：1) 可以输入各个项目的前三名或前五名的成绩；2) 能统计各学校总分，3) 可以按学校编号或名称、学校总分、男女团体总分排序输出；4) 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校；5) 数据存入文件并能随时查询；6) 规定：①输入数据形式和范围：可以输入学校的名称，运动项目的名称；②输出形式：有中文提示，各学校分数为整形；③界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。

④存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。

（数据文件的数据读写方法等相关内容在c语言程序设计的书上）请在最后的上交资料中指明你用到的存储结构；⑤测试数据：要求使用a.全部合法数据；b.整体非法数据；c.局部非法数据进行程序测试，以保证程序的稳定。

测试数据及测试结果请在上交的资料中写明。

2. 飞机订票系统任务：通过此系统可以实现如下功能：⑴录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）⑵查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；⑶可以输入起飞抵达城市，查询飞机航班情况；⑷订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；⑸退票：可退票，退票后修改相关数据文件；⑹客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。

⽤栈求算术表达式的值题⽬:1 将中缀表达式转换为后缀表达式2 求后缀表达式的值#include<stdio.h>#define MaxSize 100struct{char data[MaxSize];int top; //栈顶指针}op; //定义运算符栈struct{float data[MaxSize];int top;}st; //定义数值栈void trans(char exp[],char postexp[]){int i = 0;int j = 0;char ch;op.top = -1; //栈顶指针初始化为-1ch = exp[i];i++;while (ch != '\0'){switch (ch){case '(': //判定为左括号直接⼊栈op.top++;op.data[op.top] = ch;break;case ')':while (op.data[op.top] != '('){postexp[j] = op.data[op.top];op.top--;j++;}op.top--; //左括号也出栈但不输出break;case '+':case '-'://为 + 或者 - 时候，优先级不⼤于栈顶任何运算符的优先级直到 )while (op.top != -1 && op.data[op.top] != '('){postexp[j] = op.data[op.top];j++;op.top--;}op.top++;op.data[op.top] = ch;break;case '*':case '/'://为 * 或者是 / 时，其优先级不⼤于栈顶为 * 或者为 /的优先级直到（while (op.top != -1 && op.data[op.top] != '('&& (op.data[op.top] == '*' || op.data[op.top] == '/')){//将栈顶运算符弹出并输出postexp[j] = op.data[op.top];j++;op.top--;}//该运算符的优先级⼤于栈顶运算符的优先级直接压栈op.top++;op.data[op.top] = ch;break;case ' ': //过滤掉空格break;default:while (ch >= '0' && ch <= '9') //判定为数字{postexp[j] = ch;j++;ch = exp[i];i--;postexp[j] = '#'; //⽤#标识⼀个数值串结束j++;break;}ch = exp[i];i++;}while (op.top != -1) //此时exp扫描完毕栈不空时出栈并存放到postexp {postexp[j] = op.data[op.top];j++;op.top--;}postexp[j] = '\0'; //添加结束标识符}//后缀表达式的求值过程float Compvalue(char postexp[]){char ch;float d;int i = 0;ch = postexp[i];i++;st.top = -1;while (ch != '\0'){switch (ch){case '+':st.data[st.top - 1] = st.data[st.top - 1] + st.data[st.top];st.top = st.top - 1;break;case '-':st.data[st.top - 1] = st.data[st.top - 1] - st.data[st.top];st.top = st.top - 1;break;case '*':st.data[st.top - 1] = st.data[st.top] * st.data[st.top - 1];st.top = st.top - 1;break;case '/':if (st.data[st.top] != 0){st.data[st.top - 1] = st.data[st.top - 1] / st.data[st.top];st.top = st.top - 1;}else{printf("除数为0.\n");return 0.0;}break;default:d = 0;while (ch >= '0' && ch <= '9'){d = d * 10 + ch - '0';ch = postexp[i];i++;}st.top++;st.data[st.top] = d;break;}ch = postexp[i];i++;}return st.data[st.top];}int main(){int i = 0;char exp[] = {"(2*2)*1+3*2/1"};char postexp[MaxSize];trans(exp,postexp);while (postexp[i] != '\0'){printf("%c",postexp[i]);printf("\n");printf("运算结果为:%f.\n", Compvalue(postexp));system("pause");return 0;}后缀表达式求值如下：while(从postexp中间读取字符ch,ch != '\0'){若ch为数字，将后继的所有数字构成⼀个整数存放到数值栈st中若ch为 "+",则从数值栈st中退栈两个运算数，相加后进栈st中若ch为 "-",则从数值栈st中退栈两个运算数，相减后进栈st中若ch为 "*",则从数值栈st中退栈两个运算数，相乘后进栈st中若ch为 "/",则从数值栈st中退栈两个运算数，相除后进栈st中(若除数为0，则提⽰错误) }运⾏结果参考资料:1 《新编数据结构习题与解析》。

中北大教之阳早格格创做数据结构 课程安排证明书籍1. 安排任务概括（包罗系统总体框图及功能形貌）此课题是钻研表白式供值的问题，以助闲小教死完毕尝试.为了达到那个功能，本质咱们要搞的便是出题，战估计分数给出评介的处事.完全安排皆是以那个央供为轴心举止的.为了曲瞅战便当，现绘出硬件完全安排模块图.2.排步调完毕功能；3. 功能模块仔细安排正在此证明每个部分的算法安排证明（不妨是形貌算法的过程图），每个步调中使用的保存结构安排证明（如果指定保存结构请写出该保存结构的定义）.3.1 仔细安排思维教死要举止尝试，最先要有试题.那么咱们便要先修坐试题库.那个试题库的试题是咱们正在步调运止历程中脚动输进，存搁正在一个shujuku.txt的文献中.最先正在主函数中调用创修试题库函数，将试题存进到试题库文献shitiku.txt中，而后将该调用从主函数中简略.创修试题库函数：创修指背xuanti典型的指针，利用循环将输进的尝试题该指针的xuanti单元中，末尾将该指针中的尝试题写进试题库文献shitiku.txt中.3.2 核心代码(正文宋体小四号字，1.5倍止距)#include <stdio.h>#include <stdlib.h>#include <time.h>#include<string.h>#include <conio.h>#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define ERROR 0#define OK 1//定义表白式typedef struct shiti{char a[20];long result;}xuanti;typedef struct SqStack1{ //修坐数字栈int *base;int *top;int stacksize;}SqStack1;typedef struct SqStack2{//修坐运算符栈char *base;char *top;int stacksize;}SqStack2;void WriteToFile(xuanti *pstu,int num);void ReadFromFile(xuanti *pstu,int num);void page_title(char *menu_item){//修坐菜单printf(">>> 数教习题库 <<<\n\n- %s -\n\n",menu_item); }void return_confirm(){printf("\n按任性键返回……\n");getch();}void IntInitStack(SqStack1 *S1){S1->base=(int *)malloc(STACK_INIT_SIZE*sizeof(int)); if(!S1->base)exit(ERROR);S1->top=S1->base;S1->stacksize=STACK_INIT_SIZE;}//IntInitStackvoid CharInitStack(SqStack2 *S2){S2->base=(char *)malloc(STACK_INIT_SIZE*sizeof(char)); if(!S2->base)exit(ERROR);S2->top=S2->base;S2->stacksize=STACK_INIT_SIZE;}//CharInitStacklong IntGetTop(SqStack1 *S1){ //与栈顶元素long e1;if((*S1).top==(*S1).base)return 0;e1=*((*S1).top-1);return e1;}//IntGetTopchar CharGetTop(SqStack2 *S2){ //与栈顶元素char e2;if((*S2).top==(*S2).base) return 0;e2=*((*S2).top-1);return e2;}//IntGetTopint IntPush(SqStack1 *S1,int e1) {//进栈*(*S1).top++=e1;return OK;}//IntPushint CharPush(SqStack2 *S2,char e2) {//进栈*(*S2).top++=e2;return OK;}//CharPushint IntPop(SqStack1 *S1){//出栈int e1;if((*S1).top==(*S1).base)return 0;e1=*--(*S1).top;return e1;}//IntPopint CharPop(SqStack2 *S2){//出栈char e2;if((*S2).top==(*S2).base) return 0;e2=*--(*S2).top;return e2;}//CharPopchar Precede(char a,char b){int i,j;char Table[8][8]={ ' ','+','-','*','/','(',')','#', '+','>','>','<','<','<','>','>','-','>','>','<','<','<','>','>','*','>','>','>','>','<','>','>','/','>','>','>','>','<','>','>','(','<','<','<','<','<','=',' ',')','>','>','>','>',' ','>','>','#','<','<','<','<','<',' ','=', }; //劣先级表格for(i=0;i<8;i++)if(Table[0][i]==a) //纵坐标觅找 break;for(j=0;j<8;j++) //横坐标觅找 if(Table[j][0]==b)break;return Table[j][i];}//Precedeint Operate(int a,char theta,int b){ //估计表白式值：主假如将大的表白式转移成小的表白式举止逐步供值int c;if(theta=='+') c=a+b;else if(theta=='-') c=a-b;else if(theta=='*') c=a*b;else c=a/b;return c;}//Operateint IsOptr(char ch){char ptr[10]={'+','-','*','/','(',')','#'};for(int i=0;i<7;i++){if(ch==ptr[i])return true;}return false;}long result(char *a,SqStack1 *OPND,SqStack2 *OPTR){//供值char theta;int b,d,k=0,i=0,j=0,num2=0;IntInitStack(OPND);CharInitStack(OPTR);CharPush(OPTR,'#');while(a[i]!='='){if(!IsOptr(a[i])){k++;if(k<=j){num2=(int(a[i])-48);i++;}if(k>j){num2=num2*10+(int(a[i])-48); k=j=0;i++;}if(!IsOptr(a[i]))k++;if(k==j)IntPush(OPND,num2);}else if(IsOptr(a[i])){switch(Precede(a[i],CharGetTop(OPTR))) {case '<':CharPush(OPTR,a[i++]);if(a[i]!='('&&a[i]!=')')j++;break;case '=':CharPop(OPTR);i++;break;case '>':theta=CharPop(OPTR);d=IntPop(OPND);b=IntPop(OPND);IntPush(OPND,Operate(b,theta,d)); break;}//switch} //else if}//whileprintf("表白式的精确截止为:");printf("%d\n",IntGetTop(OPND));return (IntGetTop(OPND));}//reslutvoid Built_shitiKu(){int i,num;xuanti *pstu;printf("输进试题数目：\n");scanf("%d",&num);fflush(stdin);pstu=(xuanti *)malloc(num*sizeof(xuanti));//动背调配内存 if(pstu==NULL){printf("不脚够的内存空间！\n");return;}for(i=0;i<num;i++){//输进试题printf("第%d讲试题:",i+1);gets(pstu[i].a);fflush(stdin);printf("\n");}WriteToFile(pstu,num);//将pstu所指背的教死疑息写进文献中memset(pstu,0,num*sizeof(xuanti));//将pstu所指背的内存块浑0ReadFromFile(pstu,num);//从文献中读与教死疑息到pstu 所指背的内存块中printf("试题列表：\n");for(i=0;i<num;i++){//输进试题printf("第%d讲试题:",i+1);printf("%s",pstu[i].a);printf("\n");}free(pstu);//释搁动背调配的内存}void WriteToFile(xuanti *pstu,int num)FILE *fp;fp=fopen("shitiku.txt","at");if(fp==NULL){printf("不克不迭创修shitiku.txt\n");free(pstu);exit(0);}fwrite(pstu,sizeof(xuanti),num,fp);fclose(fp);}void ReadFromFile(xuanti *pstu,int num){//从试题库中提与试题FILE *fp;fp=fopen("shitiku.txt","rt");if(fp==NULL){printf("不克不迭挨启shitiku.txt\n");free(pstu);exit(0);}fread(pstu,sizeof(xuanti),num,fp);fclose(fp);}//****************************************** void RecMark(int *m,int num)mp=fopen("markrec.txt","at");if(mp==NULL){printf("不克不迭创修markrec.txt\n"); free(m);exit(0);}fwrite(m,sizeof(int),num,mp);fclose(mp);}//Recmarkvoid LookMark(int *m,int num){//查看得分记录FILE *mp;mp=fopen("markrec.txt","rt");if(mp==NULL){printf("不克不迭挨启markrec.txt\n"); free(m);exit(0);}fread(m,sizeof(int),num,mp);}//************************************* void RecN(int *m,int num)FILE *mp;mp=fopen("n_rec.txt","wt");if(mp==NULL){printf("不克不迭创修n_rec.txt\n");free(m);exit(0);}fwrite(m,sizeof(int),num,mp);fclose(mp);}//Recmarkvoid LookN(int *m,int num){//查看m的值FILE *mp;mp=fopen("n_rec.txt","rt");if(mp==NULL){printf("不克不迭挨启n_rec.txt\n");exit(0);}fread(m,sizeof(int),num,mp);fclose(mp);}//************************************* int excersice_begin(){int i, j, temp, KEY[20];int mark,count=0;int *Mark;char g;SqStack1 s1,*OPND;SqStack2 s2,*OPTR;xuanti *XT;OPND=&s1;OPTR=&s2;Mark=(int *)malloc(20*sizeof(int));XT=(xuanti *)malloc(20*sizeof(xuanti));ReadFromFile(XT,20);do{mark=0;srand((unsigned)time(NULL)); KEY[0] = rand()%20;for(i=1;i<20;i++){while(1){temp = rand()%20;for(j=0;j<i;j++){if(KEY[j]==temp)break;}if(j==i){KEY[i]=temp;break;}}}system("cls");printf("随机的10个训练题 :\n");for(i=0;i<10;i++){printf("第%d个训练题:",i+1);printf("%s\n",XT[KEY[i]].a);printf("请输进估计截止:");scanf("%ld",&XT[KEY[i]].result);fflush(stdin);if(XT[KEY[i]].result==result(XT[KEY[i]].a,OPND,OPTR)) {mark+=10;printf("问案精确!");printf("\n\n");}else{printf("问案过失!");printf("\n\n");}}printf("****得分情况****\n");printf("末尾的得分为:%d\n",mark);if(mark>=90)printf("Very Good!\n");else if(mark>=60)printf("结果不错.\n");else printf("很遗憾结果不迭格！\n");printf("\n");RecMark(Mark,count);Mark[count]=mark;count++;//记录次数递加printf("是可继承搞训练?('y'—是，'n'—可):"); g=getchar();fflush(stdin);printf("\n");if(count>=20)//超出最大记录次数浑0count=0;}while(g=='y');RecMark(Mark,count);return count;return_confirm();}void Look_Mark(int count){//printf("是可查看履历得分?('y'—是，'n'—可):");int *Mark;int i;Mark=(int *)malloc(20*sizeof(int));system("cls");printf("****查询履历得分情况****\n");LookMark(Mark,count);for(i=0;i<count;i++)printf("****第%d次得%d分****\n", i+1, Mark[i]);if(i>1){if(Mark[i-1]>60||Mark[i-2]>60){if(Mark[i-1]>Mark[i-2])printf("有先进，还要加油哦.\n");else if(Mark[i-1]==Mark[i-2]) printf("结果还不妨，但是不先进，还要多多全力呀！\n");else printf("结果有面下落，要多多训练，不要气馁！！\n");}else printf("结果很短佳！要越收全力教习！\n");}else{if(Mark[0]>=90)printf("Very Good!\n");else if(Mark[0]>=60)printf("结果不错.\n");else printf("很遗憾结果不迭格！\n"); }return_confirm();}void main(){int m=0;int *RN;char ch;RN=(int *)malloc(1*sizeof(int));RN[0]=0;printf("***如果是第一次运止***\n"); printf("**请先修坐 n_rec.txt**\n");printf("*****可则会堕落 !*****\n"); printf("('y'--创修**'n'--不修)\n");ch=getchar();if(ch=='y')RecN(RN,1);LookN(RN,1);RN[0]+=m;fflush(stdin);printf("是可背试题库中增加试题: "); printf("('y'--是,'n'--可)?\n");ch=getchar();if(ch=='y')Built_shitiKu();menu: page_title("支配选单");printf("请用数字键采用支配\n\n"); printf("1 启初训练\n");printf("2 查看得分记录\n");printf("0 退出\n");printf("******************\n");RN[0]+=m;m=0;switch(getch()){case '1' : m=excersice_begin();break;case '2' : Look_Mark(RN[0]);break;case '0' : {RecN(RN,1);exit(0);}}system("cls");goto menu;}3.3步调运止截止（拷屏）4.课程安排心得、存留问题及办理要领连绝二个星期的课程安排搞完了，感觉自己的本领得到了大大的普及.刚刚启初瞅睹题脚段时间，很不以为然，感触那样简朴.但是当自己启初收端搞的时间才创造本来不是那么回事.一个瞅似简朴的问题，偶尔间却牵扯甚多.通过二个星期的上机试验教习，使尔对于C谈话有了更进一步的认识战相识，要念教佳它要沉正在试验，要通过不竭的上机支配才搞更佳天教习它，通过试验，尔也创造尔的佳多缺累之处，对于C谈话教习通常不过马马虎虎的往日了，真真自己来办理本质问题的时间才会创造自己教的如许糟糕，通过课程安排对于自己的编程本领也有所普及；再有对于C谈话的文献支配那一齐，果然是易了尔佳暂.另有对于函数调用的精确使用不敷认识，另有对于C 谈话中时常出现的过失也不相识，通过试验，使尔正在那几个圆里的认识有所普及.通过试验的教习，尔认到教佳估计秘密沉视试验支配，不但是仅是教习C谈话，仍旧其余的谈话，以及其余的估计机圆里的知识皆要沉正在试验，所以来正在教习历程中，尔会越收注沉试验支配本领的培植，无论教习什么，亲自动脚来搞了才搞得到最深刻的体验.。

c语言栈计算表达式在计算机科学中，栈是一种非常重要的数据结构，被广泛应用于编译器、操作系统、网络通信等领域。

在本文中，我们将探讨如何使用C语言实现栈来计算表达式。

表达式是由操作数、操作符和括号组成的数学式子，例如：3 + 4 * 2 / (1 - 5)。

在计算表达式时，我们需要遵循一定的计算规则，如乘除法优先于加减法，括号内的计算优先于括号外的计算等。

我们可以使用栈来实现对表达式的计算。

具体步骤如下：1. 定义两个栈：一个操作数栈和一个操作符栈。

2. 从左到右遍历表达式的每一个字符，如果是数字则将其压入操作数栈；如果是操作符则将其压入操作符栈，并根据运算规则进行计算。

3. 在遍历完成后，操作符栈中可能还有未计算的操作符，需要继续计算，直到操作符栈为空。

4. 最终操作数栈中只剩下一个数，即为表达式的计算结果。

下面是一段示例代码，用于计算简单的表达式：```#include <stdio.h>#include <stdlib.h>#include <ctype.h>#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int top;} Stack;void initStack(Stack *s) {s->top = -1;}void push(Stack *s, int item) { if (s->top == MAX_SIZE - 1) { printf('Stack Overflow');exit(1);}s->data[++s->top] = item;}int pop(Stack *s) {if (s->top == -1) {printf('Stack Underflow');exit(1);}return s->data[s->top--];}int isEmpty(Stack *s) {return s->top == -1;}int isFull(Stack *s) {return s->top == MAX_SIZE - 1;}int peek(Stack *s) {return s->data[s->top];}int evaluate(char *expr) {Stack operandStack, operatorStack; initStack(&operandStack);initStack(&operatorStack);int i = 0;while (expr[i] != '0') {if (isdigit(expr[i])) {int num = 0;while (isdigit(expr[i])) {num = num * 10 + (expr[i] - '0'); i++;}push(&operandStack, num);}else if (expr[i] == '(') {push(&operatorStack, expr[i]);i++;}else if (expr[i] == ')') {while (!isEmpty(&operatorStack) && peek(&operatorStack) != '(') {int op2 = pop(&operandStack);int op1 = pop(&operandStack);char op = pop(&operatorStack);int result;switch (op) {case '+':result = op1 + op2;break;case '-':result = op1 - op2;break;case '*':result = op1 * op2;break;case '/':result = op1 / op2;break;}push(&operandStack, result);}pop(&operatorStack);i++;}else if (expr[i] == '+' || expr[i] == '-' || expr[i] == '*' || expr[i] == '/') {while (!isEmpty(&operatorStack) &&peek(&operatorStack) != '(' &&((expr[i] == '*' || expr[i] == '/') || (expr[i] == '+' || expr[i] == '-') &&(peek(&operatorStack) == '*' || peek(&operatorStack) == '/'))) {int op2 = pop(&operandStack);int op1 = pop(&operandStack);char op = pop(&operatorStack);int result;switch (op) {case '+':result = op1 + op2;break;case '-':result = op1 - op2;break;case '*':result = op1 * op2;break;case '/':result = op1 / op2;break;}push(&operandStack, result); }push(&operatorStack, expr[i]); i++;}else {i++;}}while (!isEmpty(&operatorStack)) { int op2 = pop(&operandStack);int op1 = pop(&operandStack);char op = pop(&operatorStack);int result;switch (op) {case '+':result = op1 + op2;break;case '-':result = op1 - op2;break;case '*':result = op1 * op2;break;case '/':result = op1 / op2;break;}push(&operandStack, result);}return pop(&operandStack);}int main() {char expr[MAX_SIZE];printf('Enter an expression: ');fgets(expr, MAX_SIZE, stdin);int result = evaluate(expr);printf('Result = %d', result);return 0;}```在这段代码中，我们定义了一个栈结构体，包含了栈的数据和栈顶指针。

算法设计综合实训题目0．逆序数字（借助栈）编写一个函数，接收一个4位整数值，返回这个数中数字逆序后的结果值。

例如，给定数7631，函数返回1367.输入：第一行一个正整数T（T<=10），表示有T组测试数据; 以下T行，每行一个非负的整数N。

输出：共T行，对于每组输入数据输出一行，即数字逆序后的结果值。

样本输入：3763110185158样本输出：1367810185151．人见人爱A+B这个题目的A和B不是简单的整数，而是两个时间，A和B 都是由3个整数组成，分别表示时分秒，比如，假设A为34 45 56，就表示A所表示的时间是34小时 45分钟 56秒。

输入：输入数据有多行组成，首先是一个整数N，表示测试实例的个数，然后是N行数据，每行有6个整数AH,AM,AS,BH,BM,BS，分别表示时间A和B所对应的时分秒。

题目保证所有的数据合法。

输出：对于每个测试实例，输出A+B，每个输出结果也是由时分秒3部分组成，同时也要满足时间的规则（即：分和秒的取值范围在0-59），每个输出占一行，并且所有的部分都可以用32位整数表示。

样本输入：21 2 3 4 5 634 45 56 12 23 34样本输出：5 7 947 9 302．敲七【问题描述】输出7和7的倍数，还有包含7的数字例如（17，27，37...70，71，72，73...）【要求】【数据输入】一个整数N。

(N不大于30000)【数据输出】从小到大排列的不大于N的与7有关的数字，每行一个。

【样例输入】20【样例输出】714173．统计同成绩学生人数问题【问题描述】读入N名学生的成绩，将获得某一给定分数的学生人数输出。

【要求】【数据输入】测试输入包含若干测试用例，每个测试用例的格式为第1行：N第2行：N名学生的成绩，相邻两数字用一个空格间隔。

第3行：给定分数当读到N=0时输入结束。

其中N不超过1000，成绩分数为（包含）0到100之间的一个整数。

数据结构课程设计姓名：王宗敏班级:软件1021111217班学号：1021111217目录:1．需求分析……………………………2．概要设计……………………………3．详细设计……………………………4．调试分析……………………………5．用户使用说明………………………6．测试结果……………………………利用栈求表达式的值，可供小学生作业,并能给出分数。

1．需求分析任务：通过此系统可以实现如下功能：此系统能够输入一个表达式,并计算该表达式的值。

可以根据计算结果给出分数。

能供小学生进行简单的四则运算，此外这里特别强调括号的匹配!要求：根据以上功能说明，设计运算信息,堆栈的存储结构，设计程序完成功能;2. 概要设计在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义)。

3．详细代码#include "string.h"#include ”stdio.h”＃include”conio.h"#define maxsize 100#include ”ctype.h"typedef char datatype；typedef struct｛datatype stack[maxsize］；int top；} seqstack；void stackinitiate(seqstack *s)｛s—>top=0;｝int stacknotempty（seqstack s）｛if(s.top<=0）return 0;else return 1；}int stackpush(seqstack ＊s，datatype x) {if（s->top>=maxsize）{printf(”堆栈已满无法插入！\n")；return 0;}else{s—>stack［s—〉top]=x；s->top++;return 1;}｝int stackpop（seqstack *s,datatype ＊d){if(s->top<=0)｛printf("堆栈已空无数据元素出栈！\n"）；return 0；｝else｛s-〉top——;*d=s->stack[s—〉top］；return 1；}}int stacktop(seqstack s,datatype *d)｛if（s。

利用栈来实现算术表达式求值的算法利用栈来实现算术表达式求值的算法算术表达式是指按照一定规则组成的运算式，包含数字、运算符和括号。

在计算机中，求解算术表达式是一项基本的数学运算任务。

根据算术表达式的性质，我们可以考虑利用栈这一数据结构来实现求值算法。

一、算法思路首先，我们需要明确一个重要概念——逆波兰表达式（ReversePolish notation）。

逆波兰表达式是一种没有括号的算术表达式，其运算规则是先计算后面的数字和运算符，再计算前面的数字和运算符。

例如，对于算术表达式“3+4*5-6”，其对应的逆波兰表达式为“3 45 * +6 -”。

那么，我们可以利用栈来实现将中缀表达式转化为逆波兰表达式的过程，具体步骤如下：1. 创建两个栈——操作数栈和操作符栈。

2. 从左到右扫描中缀表达式的每一个数字和运算符，遇到数字则压入操作数栈中，遇到运算符则进行如下操作：（1）如果操作符栈为空或当前运算符的优先级大于栈顶运算符的优先级，则将当前运算符压入操作符栈中。

（2）如果当前运算符的优先级小于或等于栈顶运算符的优先级，则将栈顶运算符弹出并加入操作数栈中，重复此过程直到遇到优先级较低的运算符或操作符栈为空为止，然后将当前运算符压入操作符栈中。

3. 扫描完中缀表达式后，若操作符栈不为空，则将其中所有运算符弹出并加入操作数栈中。

4. 最终，操作数栈中存放的就是逆波兰表达式，我们可以按照逆波兰表达式的计算规则来计算其结果。

二、算法优点利用栈来实现算术表达式求值的算法具有以下优点：1. 代码简洁易懂，易于实现和维护。

2. 由于将中缀表达式转化为逆波兰表达式后，可以减少运算符的优先级关系而消除括号，从而减少求值的复杂度，提高程序的执行效率。

三、代码实现下面是利用栈来实现算术表达式求值的算法的Python代码实现：```pythonclass Stack:def __init__(self):self.items = []def push(self, item):self.items.append(item)def pop(self):return self.items.pop()def peek(self):return self.items[-1]def is_empty(self):return len(self.items) == 0def size(self):return len(self.items)def calculate(op_num1, op_num2, operator):if operator == "+":return op_num1 + op_num2elif operator == "-":return op_num1 - op_num2elif operator == "*":return op_num1 * op_num2elif operator == "/":return op_num1 / op_num2def infix_to_postfix(infix_expr):opstack = Stack()postfix_expr = []prec = {"+": 1, "-": 1, "*": 2, "/": 2, "(": 0} token_list = infix_expr.split()for token in token_list:if token.isdigit():postfix_expr.append(token)elif token == '(':opstack.push(token)elif token == ')':top_token = opstack.pop()while top_token != '(':postfix_expr.append(top_token)top_token = opstack.pop()else:while (not opstack.is_empty()) and(prec[opstack.peek()] >= prec[token]):postfix_expr.append(opstack.pop())opstack.push(token)while not opstack.is_empty():postfix_expr.append(opstack.pop())return " ".join(postfix_expr)def postfix_eval(postfix_expr):opstack = Stack()token_list = postfix_expr.split()for token in token_list:if token.isdigit():opstack.push(int(token))else:op_num2 = opstack.pop()op_num1 = opstack.pop()result = calculate(op_num1, op_num2, token) opstack.push(result)return opstack.pop()infix_expr = "3 + 4 * 5 - 6"postfix_expr = infix_to_postfix(infix_expr)print(postfix_expr)print(postfix_eval(postfix_expr))```四、总结算术表达式求值是一项常见的数学运算任务，利用栈这一数据结构来实现求值算法是一种简单有效的方法，它将中缀表达式转化为逆波兰表达式后，可以消除括号并减少运算符的优先级关系，从而提高程序的执行效率。

//1.h#include<ctime>#include<cstring>#include<fstream>#include<iomanip>#include<iostream>using namespace std;//template<class T>struct Ti //定义一个结构体，用于存储题习题库中的每一道台?题目{char chh[30];};template<class T>struct Stack //定义栈，其中数据元素为字符型í{T data[50];int top;};template<class T>struct Stack2 //定义栈，其中数据元素为整型í{float data[50];int top;};template<class T>class link{public:void Push(Stack<T> &S,char x);char Pop(Stack<T> &S,char x);void Push2(Stack2<T> &S,float x);float Pop2(Stack2<T> &S,float x);void pingjia(int m) ;int In(char c);int change(char x);int Precede(int a,int b);float Operate(float a,char c,float b);void toEmpty(char s[],int n);void isStay(char s1[],int n1,char s2[],int n2);int isInt(char s[],int n);void xitiku(char a[],int n);float Expression();Stack<T> setStack();Stack2<T> setStack2();};//1.cpp#include<ctime>#include"1.h"#include<cstring>#include<fstream>#include<iomanip>#include<iostream>using namespace std;template<class T>void link<T>::Push(Stack<T> &S,char x) {if(S.top==49){cout<<"栈已满！?"<<endl;}elseS.top++;S.data[S.top]=x;}template<class T>char link<T>:: Pop(Stack<T> &S,char x) {if(S.top==-1){cout<<"栈空！"<<endl;}x=S.data[S.top];S.top--;return x;template<class T>void link<T>::Push2(Stack2<T> &S,float x) {if(S.top==49){cout<<"栈已满！"<<endl;}elseS.top++;S.data[S.top]=x;}template<class T>float link<T>::Pop2(Stack2<T> &S,float x) {if(S.top==-1){cout<<"栈空！"<<endl;}x=S.data[S.top];S.top--;return x;template<class T>void link<T>::pingjia(int m){switch(m/10){case 0:case 1:case 2:case 3:case 4:case 5:cout<<"对不起，你没能及格，要加油哦！\n";break;case 6:case 7:cout<<"恭喜您及格了，但离高分还有距离哦！\n";break;case 8:case 9:cout<<"哇，您居然得了这么高的分数，真棒！\n";break;case 10:cout<<"OH MY GOD!，您竟然考了满分!!\n";break;}}template<class T>int link<T>::In(char c) //判断字符是否为运算符? {int m=0,i;char OP[7]={'+','-','*','/','(',')','#'};for(i=0;i<7;i++){if(c==OP[i])m++;}if(m==0)return 0;elsereturn 1;}template<class T>int link<T>::change(char x) //将运算符转换成为数字{int a;switch(x){case'+': a=0;break;case'-': a=1;break;case'*': a=2;break;case'/': a=3;break;case'(': a=4;break;case')': a=5;break;case'#': a=6;break;}return a;}template<class T>int link<T>:: Precede(int a,int b) //比括较运算符之间的优先级{int A;int token[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,2},{1,1,1,1,2,1,1},{-1,-1,-1,-1,-1,2,0}};switch(token[a][b]){case -1:A=-1;break;case 0:A= 0;break;case 1:A= 1;break;}return A;}template<class T>float link<T>::Operate(float a,char c,float b) //对两个数进行四则运算{float s;switch(c){case'+':s=a+b;break;case'-':s=a-b;break;case'*':s=a*b;break;case'/':s=a/b;break;}return s;}template<class T>void link<T>::toEmpty(char s[],int n) //把一个数组置空{int i;for(i=0;i<n;i++)s[i]='\0';}template<class T>void link<T>::isStay(char s1[],int n1,char s2[],int n2) //把一个表达式分成几段{int i=0,j=0;while(s1[i]==' '){if(s1[i]==' '){i++;}}if(s1[i]=='\0')exit(0);while(s1[i]!='\0'){if(In(s1[i+1])!=In(s1[i])||In(s1[i+1])*In(s1[i])==1||s1[i]=='\0 '){s2[j]=s1[i];s1[i]=' ';break;}if(In(s1[i+1])==In(s1[i])){s2[j]=s1[i];s1[i]=' ';i++;j++;}}}template<class T>int link<T>::isInt(char s[],int n){int i=0,j=0,x;while(s[i]!=' '&&s[i]!='\0'){if(s[i]>='0'&&s[i]<='9'||s[0]=='-') j++;i++;}if(i==j){x=atoi(s);return x;}elsereturn -1;}template<class T>void link<T>::xitiku(char a[],int n) //创建习题库{int TIME,T;Ti t[100]={'\0'};char ch[30]={'\0'};int i;ifstream file("TextFile1.txt",ios_base::in);if(!file){cout<<"打洙?开a习°题琣库a文?件t失骸?败悒?！?"<<endl;exit(0);}i=0;while(!file.eof()){file.getline(ch,50);strcpy(t[i].chh,ch);i++;}srand(time(0));TIME=rand()%7;T=TIME;int j=0;while(t[T].chh[j]!='#'){cout<<t[T].chh[j];j++;}cout<<'=';strcpy(a,t[T].chh);file.close();}template<class T>float link<T>::Expression() //试题测试{char x=0,theta=0;char s[30]={'\0'},shu[5]={'\0'};float a=0,b=0,n;int i,j;Stack<T> R;Stack2<T> D;R=setStack();Push(R,'#');D=setStack2();xitiku(s,30);isStay(s,30,shu,5);while((shu[0]!='#'||R.data[R.top]!='#')) {if(In(shu[0])==0){float S1=atoi(shu);Push2(D,S1);toEmpty(shu,5);isStay(s,30,shu,5);}else{i=change(R.data[R.top]);j=change(shu[0]);switch(Precede(i,j)){case -1:Push(R,shu[0]);toEmpty(shu,5);isStay(s,30,shu,5);break;case 0:Pop(R,x);toEmpty(shu,5);isStay(s,30,shu,5);break;case 1:theta=Pop(R,theta);b=Pop2(D,b);a=Pop2(D,a);n=Operate(a,theta,b);Push2(D,n);break;}}}return n;}template<class T>Stack2<T> link<T>::setStack2() {Stack2<T> s;s.top=-1;return s;}template<class T>Stack<T> link<T>::setStack() {Stack<T> s;s.top=-1;return s;}//main.cpp#include"1.cpp"#include"iostream"using namespace std;int main(){link <int> t;cout<<"---------------------------------表达式求值-------------------------------------\n";int i=0,j,geshu=0,n,m,jieguo[100],daan[100];char ch,c[6]={'\0'};cout<<"***做题请输入A，查看成绩单请输入B,结束程序请输入C***\n\n";cin>>ch;cout<<endl;while(ch){switch(ch){case'A':cout<<"-------------现在开始做题--------------\n\n";n=int(t.Expression()+0.5);cout<<"\n\n请输入你的答案?输入-1表示停止做题：";cin>>c;m=t.isInt(c,6);while(m!=-1){if(m==-1111){cout<<"\n输入错误,请重新输入您的答案！";cout<<"\n\n请输入你的答案（输入-1表示停止做题)：";cin>>c;m=t.isInt(c,6);}else{i++;jieguo[i-1]=m;daan[i-1]=n;if(m==n)geshu++;cout<<endl;n=int(t.Expression()+0.5);cout<<"\n\n请输入你的答鋏案(输入-1表示停止做题)：";cin>>c;m=t.isInt(c,6);}}cout<<"----------------------------------------\n\n";break;case'B':if(i==0)cout<<"成绩单为空！\n\n";else{cout<<" *********您的成绩单******* \n\n";cout<<"-----------------------------------\n";cout<<"题号你的答案正确答案结论\n";for(j=0;j<i;j++){cout<<setw(2)<<j+1;cout<<setw(11)<<jieguo[j];cout<<setw(11)<<daan[j];if(jieguo[j]==daan[j])cout<<setw(11)<<"正确！";elsecout<<setw(11)<<"错误！";cout<<endl;}cout<<"-----------------------------------\n";cout<<"共做了"<<i<<"道题，其中\n";cout<<"做对了"<<geshu<<"道题，做错了"<<i-geshu<<"道题.\n";int fenshu=geshu*100/i;cout<<"最后成绩为:"<<fenshu<<"分！"<<endl;t.pingjia(fenshu);cout<<"-----------------------------------\n";}break;case'C':cout<<"程序结束,谢谢使用！"<<endl;exit(0);default:cout<<"输入错误，请重新输入！"<<endl;break;}cout<<"\n***做题请输入A，查看历史请输入B,结束程序请输入C***\n\n";cin>>ch;cout<<endl;ch=toupper(ch);}system("pause");return 0;}。

栈的应⽤——表达式求值 表达式求值是程序设计语⾔编译中的⼀个基本问题，它的实现就是对“栈”的典型应⽤。

本⽂针对表达式求值使⽤的是最简单直观的算法“算符优先法”。

本⽂给出两种⽅式来实现表达式求值，⽅式⼀直接利⽤中缀表达式求值，需要⽤到两个栈，操作数栈和操作符栈。

⾸先置操作数栈为空栈，操作符栈仅有“#”⼀个元素。

依次读⼊表达式中的每个字符，若是操作数则进操作数栈，若是操作符则和操作符栈的栈顶运算符⽐较优先权作相应操作，直⾄整个表达式求值完毕。

⽅式⼆⾸先把中缀表达式转换为后缀表达式并存储起来，然后利⽤读出的后缀表达式完成求值，其本质上是⽅式⼀的分解过程。

表达式求值的代码如下：#include <iostream>#include "stack"#include "map"using namespace std;/* 只能求⼀位整数的加减乘除混合运算 */map<char, pair<int, int>> priority; // 存放各个操作符的栈内栈外优先级,first是栈内,second是栈外char infix[50]; // 存放初始的中缀表达式char postfix[50]; // 存放转化的后缀表达式int result;void MakePriority() // 构造运算符优先级表{priority.insert(make_pair('#', make_pair(0, 0))); // isp(#)=0, icp(#)=0priority.insert(make_pair('\n', make_pair(0, 0))); // isp(\n)=0, icp(\n)=0 表达式结尾的'#'⽤'\n'代替,这样可以省略表达式末尾的结束符'#'priority.insert(make_pair('(', make_pair(1, 6))); // isp(()=1, icp(()=6priority.insert(make_pair('*', make_pair(5, 4))); // isp(*)=5, icp(*)=4priority.insert(make_pair('/', make_pair(5, 4))); // isp(/)=5, icp(/)=4priority.insert(make_pair('%', make_pair(5, 4))); // isp(%)=5, icp(%)=4priority.insert(make_pair('+', make_pair(3, 2))); // isp(+)=3, icp(+)=2priority.insert(make_pair('-', make_pair(3, 2))); // isp(-)=3, icp(-)=2priority.insert(make_pair(')', make_pair(6, 1))); // isp())=6, icp())=1}void InfixToPostfix() // 把中缀表达式转换为后缀表达式{int i = 0;stack<char> optrStack; // 操作符栈char optr; // optr为栈顶的操作符optrStack.push('#');while (!optrStack.empty()){if (isdigit(infix[i])) // 是操作数则直接输出(追加到postfix结尾){postfix[strlen(postfix)] = infix[i];postfix[strlen(postfix) + 1] = '\0';i++; // 读⼊中缀表达式的下⼀个字符}else// 是操作符, ⽐较优先级{optr = optrStack.top(); // 取出栈顶操作符if (priority[infix[i]].second > priority[optr].first) // icp(infix[i]) > isp(optr),infix[i]⼊栈{optrStack.push(infix[i]);i++;}else if (priority[infix[i]].second < priority[optr].first)// icp(infix[i]) < isp(optr),optr退栈并输出{postfix[strlen(postfix)] = optr;postfix[strlen(postfix) + 1] = '\0';optrStack.pop();}else// icp(infix[i]) = isp(optr),退栈但不输出,若退出的是'(',则继续读⼊下⼀个字符{optrStack.pop();if (optr == '(')i++;}}}}void CalculateByPostfix() // 通过后缀表达式求值{int i = 0;stack<int> opndStack; // 操作数栈int left, right; // 左右操作数int value; // 中间结果int newOpnd;while (postfix[i] != '#' && i < strlen(postfix)){switch (postfix[i]){case'+':right = opndStack.top(); // 从操作数栈中取出两个操作数opndStack.pop();left = opndStack.top();opndStack.pop();value = left + right;opndStack.push(value); // 中间结果⼊栈break;case'-':right = opndStack.top();opndStack.pop();left = opndStack.top();opndStack.pop();value = left - right;opndStack.push(value);break;case'*':right = opndStack.top();opndStack.pop();left = opndStack.top();opndStack.pop();value = left * right;opndStack.push(value);break;case'/':right = opndStack.top();opndStack.pop();left = opndStack.top();opndStack.pop();if (right == 0){cerr << "Divide by 0!" << endl;}else{value = left / right;opndStack.push(value);}break;default:newOpnd = (int)(postfix[i] - 48); // 操作数直接⼊栈opndStack.push(newOpnd);break;}i++;}result = opndStack.top();}void CalculateByInfix() // 直接利⽤中缀表达式求值{int i = 0;stack<char> optrStack; // 操作符栈stack<int> opndStack; // 操作数栈char optr; // optr为操作符栈顶的操作符int left, right, value; // 左右操作数以及中间结果optrStack.push('#');optr = optrStack.top();while (!optrStack.empty()) // 直到操作符栈为空{if (isdigit(infix[i])) // 是操作数, 进操作数栈{value = (int)(infix[i] - 48);opndStack.push(value);i++;}else// 是操作符, ⽐较优先级{optr = optrStack.top(); // 取出操作符栈顶的操作符if (priority[infix[i]].second > priority[optr].first) // icp(infix[i]) > isp(optr),infix[i]⼊栈 {optrStack.push(infix[i]);i++;}else if (priority[infix[i]].second < priority[optr].first) // icp(infix[i]) < isp(optr),optr退栈并输出{optrStack.pop();right = opndStack.top(); // 从操作数栈中取出两个操作数opndStack.pop();left = opndStack.top();opndStack.pop();switch (optr){case'+':value = left + right;opndStack.push(value); // 中间结果⼊栈break;case'-':value = left - right;opndStack.push(value); // 中间结果⼊栈break;case'*':value = left * right;opndStack.push(value); // 中间结果⼊栈break;case'/':if (right == 0){cerr << "Divide by 0!" << endl;}else{value = left / right;opndStack.push(value);}break;default:break;}}else{optrStack.pop();if (optr == '(')i++;}}}result = opndStack.top();}int main(){MakePriority(); // 构造运算符优先级表cout << "请输⼊中缀表达式：";cin >> infix;cout << "直接利⽤中缀表达式求值为：";CalculateByInfix();cout << result << endl;cout << "转化为后缀表达式：";InfixToPostfix();for (int i = 0;i < strlen(postfix);i++){cout << postfix[i];}cout << endl;cout << "利⽤后缀表达式求值为：";CalculateByPostfix();cout << result << endl;return0;} 为了⽅便起见，本⽂只是简单的设计了⼀个针对⼀位整数的四则运算进⾏求值的算法，对于处理多位整数的四则运算，需要对本⽂接受输⼊的数据类型进⾏“升阶”，把字符数组换成字符串数组，将⼀个整数的多位数字存⼊⼀个字符串进⾏处理。

**大学数据结构课程设计报告题目：利用栈求表达式的值院（系）：计算机工程学院学生姓名:班级：学号:起迄日期: 2011、6、30指导教师:20XX—20XX年度第 2 学期一、需求分析1、从键盘上输入表达式。

2、分析该表达式是否合法：（1）是数字，则判断该数字的合法性。

若合法，则压入数据到堆栈中。

（2）是规定的运算符，则根据规则进行处理。

在处理过程中，将计算该表达式的值。

（3）若是其它字符，则返回错误信息。

3、若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。

程序中应主要包含下面几个功能函数：void initstack()：初始化堆栈int Make_str()：语法检查并计算int push_operate(int operate)：将操作码压入堆栈int push_num(double num)：将操作数压入堆栈int procede(int operate)：处理操作码int change_opnd(int operate)：将字符型操作码转换成优先级int push_opnd(int operate)：将操作码压入堆栈int pop_opnd()：将操作码弹出堆栈int caculate(int cur_opnd)：简单计算+，-，*，/double pop_num()：弹出操作数二、概要设计1.定义一个expression全局表达式结构体expr[1000]存放计算过的表达式(expstr[MAXSIZE])和计算结果(result)、一个计量器(i)、一个表达式字符串、一个操作码栈和一个操作数栈；2.把表达式字符串从头到尾逐一扫描，将输入的表达式进行语法检查；3.第一个字符只能是数字或“（”，最重一个字符只能是“=”；4.表达式括号必须配对，中间不能出现“=”；5.在“（”前面只能是“+、－、*、/、( ”，在“+、－、*、/、=、)”前面只能是数字或“）”；6.把表达式字符串从头到尾逐一扫描，直到表达式扫描完毕，操作码栈为空；7.把字符根据运算优先级别选择操作；8.把表达式中的数值部分字符串转成数值压入操作数栈；9.是“(”直接压入到操作码栈，级别比操作码栈顶元素高的，把运算符压入操作码栈；10.级别比操作码栈低的，弹出操作码栈的栈顶元素和操作数栈的两个栈顶元素，进行运算后再压入操作数栈；11.是“)”，若操作码栈顶是“(”，把弹出操作码栈顶元素，否则“)”视为级别最低的元素，重复7；12.最后计算出结果并将其存放在expr[i]，计量器加1；13.重复计算后，将结果保存在文件里，并统计计算次数；14.查看多次计算结果，以表形式输出；15.查看本次计算记录，以表形式输出；清除计算记录，重新计算三、详细设计(一)程序总共有如下函数：主要函数：void start(opnd *op,num *nu)//程序主菜单void start2(opnd *op,num *nu)//第二层计算选择，子菜单void load()//显示所有计算记录void save()//保存计算结果void check()//显示本次计算结果void result(opnd *op,num *nu)//计算结果double caculate(opnd *op,num *nu)//简单计算+，-，*，/表达式处理函数：int make_str()//语法检查double change_num(char str[])//数字字符串转成double型数字char procede(char top,char code)//处理操作码，判断栈的操作int change_opnd(char code)//字符型操作码转换优先级，非表达式字符返回-2 栈操作函数：double get_num(num *nu)//查看操作数栈栈顶double pop_num(num *nu)//操作数栈出栈int push_num(num *nu,double da)//压入操作数栈int empty_num(num *nu)//判空void initstack(num *nu)char get_opnd(opnd *op)//查看栈顶char pop_opnd(opnd *op)//出栈int push_opnd(opnd *op,char co)//压栈int empty_opnd(opnd *op)//判空void initstack(opnd *op)//初始化栈(二)函数间的调用关系：●main()：主函数→start();↗load() →start();●start()程序模式函数→清空文件→exit();↘make_str()→result(op,nu)→start2()→start();↗load →start();●start2()子菜单→save() →start2();↘check() →start2();●result(op,nu)计算结果→initstack(op) →initstack(nu) →push_opnd(op,'=') →↗push_num(nu,change_num(str2));→change_opnd(*ps) ↗push_opnd(op,*ps)；↘procede(get_opnd(op),*ps) →pop_opnd(op);↘push_num(nu,caculate(op,nu)) ●caculate(op,nu)→b=pop_num(nu) →a=pop_num(nu) →pop_opnd(op)✓ main()函数：调用了一个函数start()，start()判断执行查看所有计算记录函数load()，或是清空以往的所有计算记录，或是退出程序，或是检查输入表达式语法make_str()并计算表达式result(op,nu)的操作。

课程设计课程名称数据结构题目名称利用栈求表达式的值专业班级2014级计算机科学与技术本学生姓名刘志，马健，王青星，杨文祥，王胜达学号51402011052,5140201104 2,51402011032,51402011 006,51402011046指导教师姚保峰二○一六年六月十五日目录1.设计目的: (1)2.设计要求: (2)3.设计方案: (3)4.设计内容: (4)4.1．需求分析 (4)4.2．概要设计 (4)4.3.详细设计 (7)4.4.调试分析与结果 (11)4.5：使用说明 (15)5.总结： (16)6.附录三：源代码 (18)1.设计目的:数据结构课程设计是计算机专业集中实践性环节之一，是学习完《数据结构》课程后进行的一次全面的综合练习。

其目的是：（1）要达到理论与实际应用相结合，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。

（2）在实践中认识为什么要学习数据结构，掌握数据结构、程序设计语言、程序设计技术之间的关系，是前面所学知识的综合和回顾。

2.设计要求:以字符序列的形式从键盘输入语法正确的、不含变量的整数（或实数）表达式，实现对算术四则混合运算表达式的求值。

当用户输入一个合法的算术表达式后，能够返回正确的结果。

能够计算的运算符包括：加、减、乘、除、括号，对于异常表达式能给出错误提示。

3.设计方案:任何一个表达式都是由操作符，运算符组成的。

我们分别用顺序栈来寄存表达式的操作数和运算符。

栈是限定于紧仅在表尾进行插入或删除操作的线性表。

顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素。

为了实现运算符优先算法。

可以使用两个栈。

一个称为OPF，用以寄存运算符，另一个称做OPS，用以寄存操作数或运算结果。

1.首先置操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素；2.依次读入表达式，若是操作符即进OPS栈，若是运算符则和OPF栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即OPF栈的栈顶元素和当前读入的字符均为”#”）。

《数据结构》课程设计报告专业计算机科学与技术班级（1）姓名王昕学号20101308003指导教师顾韵华起止时间2011.10~2011.12课程设计：利用栈求表达式的值一、任务描述建立试题库文件，随机产生n个题目；题目涉及加减乘除，带括号的整数混合运算；随时可以退出；保留历史分数，能回顾历史，给出与历史分数比较后的评价。

（假设这是一个可供小学生练习算术运算的小系统）要求：根据以上任务说明，设计程序完成功能。

二、问题分析1、功能分析分析设计课题的要求，要求编程实现以下功能：（1）建立试题库文件—即创建试题库函数（2）实现整数混合运算—即建立栈实现运算（3）查看历史分数—即建立函数查看2、数据对象分析由于其中涉及了能回顾历史成绩以及随机做题等问题，所以就考虑用到了文件的打开与关闭以及文件的读写功能。

由于此设计要实现多个功能，所以为了源代码清晰明了，所有的函数不是用的嵌套方式，而是对每个功能都用一个子程序来实现，然后通过对子程序的调用来达到设计的要求三、数据结构设计有关的定义如下：typedef struct shiti /*定义表达式*/{char a[20]; /*存放表达式*/long result; /*存放用户输入的答案*/}xuanti;typedef struct SqStack1 /*建立数字栈*/{int *base;int *top;int stacksize;}SqStack1;typedef struct SqStack2 /*建立运算符栈*/{char *base;char *top;int stacksize;}SqStack2;四、功能设计（一）主控菜单设计为实现程序的操作功能，首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。

程序运行后，给出以下项的内容和输入提示，如下：1.输入表达式2.表达式结果3.继续输入表达式4.显示结果（二）程序模块结构由课题要求可将程序划分为以下几个模块（即实现程序功能所需的函数）：1.写入函数WriteToFile()2.读出函数ReadFromFile()3.栈函数stack()（三）函数调用关系其中main()是主函数，它进行菜单驱动，根据选择项0~9用相应的函数。

⽤栈计算数学表达式的值⽤栈计算数学表达式的值计算⼀个简单数学表达式（+ - * / （））的结果，有的这些符号的计算，常常需要看优先级来决定先算哪部分，计算机就是这个原理两个概念：中缀表达式（infix Expression）：运算符写在两个操作数之间(运算符有⼀定的优先级，可以⽤圆括号改变运算顺序)前/后缀表达式（prefix/postfix Expression）:运算符写在两个表达式之前/之后（运算符没有优先级，没有括号，遇到运算符对它前⾯的两个操作数进⾏求值）如中缀表达式“6*（8+7）/5”，换成后缀表达式为“6 8 7 + * 5 /”编程思路：函数toPostfix(),⽤运算符栈来存运算符，从中缀表达式第⼀个字符开始，如果是数字，直接加到postfix，如果是运算符号，判断和栈顶的优先级，不⽐栈顶的符号优先级低则⼊栈，（注意：栈中的“（”优先级最低，），否则，要栈顶出栈，如果是左括号，直接⼊栈，如果是右括号，则出栈，直到栈顶为左括号为⽌。

函数toValue(),⽤操作数栈来存数字，从后缀表达式第⼀个字符开始，是数字，就⼊栈，是运算符号就⽤栈顶的两个数计算结果值，结果⼊栈。

下⾯是具体代码，可以帮助理解：元素存储，我选择⽤顺序表（SeqList<T>）1//Stack<T>接⼝2public interface Stack<T> {3public abstract boolean isEmpty();45public abstract void push(T x); // 元素x⼊栈67public abstract T peek(); // 返回栈顶元素89public abstract T pop(); // 出栈，返回出栈元素1011 }12//顺序栈，使⽤顺序表存储13public class SeqStack<T> implements Stack<T> {14private SeqList<T> list;1516public SeqStack(int length) {17this.list = new SeqList<T>(length); // 构造容量为length的空栈18 }1920public SeqStack() {21this(64); // 构造默认容量的空栈，调⽤上⼀个构造函数22 }2324public boolean isEmpty() {25return this.list.isEmpty();26 }2728public void push(T x) { // 顺序表表尾插⼊元素29 list.insert(x);30 }3132public T peek() {33return this.list.get(list.size() - 1);34 }3536public T pop() {37return list.remove(list.size() - 1);38 }39 }40//计算数学表达式41public class Calculate {42// 中缀表达式转化成后缀表达式,把运算符进⼊到运算符栈43public static StringBuffer toPostfix(String infix) {44 Stack<String> st = new SeqStack<String>(infix.length());45 StringBuffer sb = new StringBuffer(2 * infix.length());46int i = 0;47while (i < infix.length()) {48char ch = infix.charAt(i);49switch (ch) {50case '+':51case '-':52while (!st.isEmpty() && !st.peek().equals("("))53// 栈顶不是“（”，那么都不⽐"+-"低，都要出栈54 sb.append(st.pop());55 st.push(ch + "");56 i++;57break;58case '*':59case '/':60while (!st.isEmpty()61 && (st.peek().equals("*") || st.peek().equals("/")))62 sb.append(st.pop());63 st.push(ch + "");64 i++;65break;66case '(':67 st.push(ch + "");68 i++;69break;70case ')':71 String out = st.pop(); // 出栈，直到为"("72while (out != null && !out.equals("(")) {73 sb.append(out);74 out = st.pop();75 }76 i++;77break;7879default:80while (i < infix.length() && ch >= '0' && ch <= '9') {81 sb.append(ch);82 i++;83if (i < infix.length()) {84 ch = infix.charAt(i);85 }86 }87 sb.append(" ");88break;89 }9091 }9293while (!st.isEmpty())94// 剩下的出栈95 sb.append(st.pop());96return sb;97 }9899// 后缀表达式的计算结果，运算结果⼊栈100public static int toValue(StringBuffer postfix) {101 Stack<Integer> st = new SeqStack<Integer>(postfix.length()); 102int value = 0;103for (int i = 0; i < postfix.length(); i++) {104char ch = postfix.charAt(i);105if (ch >= '0' && ch <= '9') {106 value = 0; // ⼀定要先让value初始值为0107while (ch != ' ') {108 value = value * 10 + ch - '0'; // 字符转化为数值109 ch = postfix.charAt(++i); // 如果这个字符为多位数110 }111 st.push(value);112 } else {113if (ch != ' ') {114int y = st.pop(), x = st.pop(); // Integer⾃动转化为int类型115116switch (ch) {117case '+':118 value = x + y;119break;120case '-':121 value = x - y;122break;123case '*':124 value = x * y;125break;126case '/':127 value = x / y;128break;129130 }131132 st.push(value);133 }134 }135136 }137return st.pop(); // 结果就在栈顶138139 }140141 }。

利⽤栈实现算术表达式求值（Java语⾔描述）利⽤栈实现算术表达式求值(Java语⾔描述)算术表达式求值是栈的典型应⽤，⾃⼰写栈，实现Java栈算术表达式求值，涉及栈，编译原理⽅⾯的知识。

声明：部分代码参考⾃茫茫⼤海的专栏。

链栈的实现：package 算数表达式求值;public class Stack<T> {//节点类public class Node{public T data;public Node next;public Node(){}public Node(T data,Node next){this.data = data;this.next = next;}}//Nodepublic Node top = new Node();public int size;public Node oldNode;//⼊栈public void push(T element){top = new Node(element,top);size++;}//出栈public T pop(){oldNode = top;top = top.next;//oldNode = null;size--;return oldNode.data;}//返回栈顶对象的数据域，但不出栈public T peek(){return top.data;}//栈长public int length(){return size;}//判断栈是否为空public boolean isEmpty(){return size == 0;}}表达式求值的实现：package 算数表达式求值;import java.util.Scanner;//import java.util.Stack;public class Expression {//运算符之间的优先级,其顺序是+、-、*、/、（、），其中⼤于号表⽰优先级⾼//，⼩于号表⽰优先级低，等号表⽰优先级相同，感叹号表⽰没有优先关系public static final char[][] relation = {{'>','>','<','<','<','>','>'},{'>','>','<','<','<','>','>'},{'>','>','>','>','<','>','>'},{'>','>','>','>','<','>','>'},{'<','<','<','<','<','=','!'},{'>','>','>','>','!','>','>'},{'<','<','<','<','<','!','='}};public static void main(String[] args) {Scanner input = new Scanner(System.in);while(true){try{System.out.println("请输⼊要计算的表达式：");String exp = input.next();System.out.println(calc(exp + "#"));}catch(ArithmeticException e1){System.out.println("表达式中的分母不能为0");e1.printStackTrace();}}}/**** @param exp 要计算的表达式* @return 计算的结果*/private static int calc(String exp) {//操作数栈Stack<Integer> num = new Stack<Integer>();//操作符栈Stack<Character> op = new Stack<Character>();op.push('#');int i = 0;char ch = exp.charAt(i);boolean flag = false;//判断连续的⼏个字符是否是数字，若是，就处理成⼀个数字。

一、概述在计算机科学中，栈是一种非常重要的数据结构，它具有“先进后出”的特点，能够很好地辅助实现算法和表达式的求值。

在C语言中，我们可以借助栈这种数据结构来完成对运算表达式的求值，从而实现计算功能。

本文将介绍如何在C语言中利用栈完成运算表达式的求值。

二、栈的基本概念1. 栈的定义栈是一种线性结构，它具有两个基本的操作：入栈（push）和出栈（pop）。

栈的特点是只允许在栈顶进行操作，即每次只能操作最后一个插入到栈中的元素。

这种先进后出的结构使得栈非常适合用来处理递归、表达式求值等问题。

2. 栈的实现在C语言中，我们可以通过数组或链表来实现栈。

数组实现的栈叫做顺序栈，链表实现的栈叫做链式栈。

对于运算表达式的求值来说，我们可以选择数组来实现栈。

栈的结构可以定义如下：```c#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int top;} Stack;```这样我们就定义了一个包含数组和栈顶指针的栈结构类型。

三、运算表达式的求值1. 中缀表达式在数学中，我们通常使用中缀表达式来表示运算式，例如：1 + 2 * 3。

这种表达式的书写方式是运算符位于操作数之间。

在计算机中，中缀表达式不太方便进行求值，因此我们需要将中缀表达式转换为后缀表达式来进行计算。

2. 后缀表达式后缀表达式又称为逆波兰表达式，它的特点是运算符位于操作数之后，比如：1 2 3 * +。

后缀表达式的求值非常简单，只需要从左到右遍历表达式，遇到操作数就入栈，遇到运算符就弹出栈顶的两个操作数进行运算，然后将结果再入栈，直到表达式结束。

3. 栈完成后缀表达式的求值我们可以利用栈来完成后缀表达式的求值。

具体步骤如下：（1）创建一个空栈（2）从左到右遍历后缀表达式（3）如果遇到操作数，则入栈（4）如果遇到运算符，则弹出栈顶的两个操作数进行运算，然后将结果入栈（5）遍历结束后，栈中剩下的元素就是表达式的值四、示例代码下面是一个简单的示例代码，演示了如何利用栈完成后缀表达式的求值：```c#include <stdio.h>#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int top;} Stack;void initStack(Stack *s) {s->top = -1;}void push(Stack *s, int value) { if (s->top < MAX_SIZE - 1) { s->data[++s->top] = value; } else {printf("Stack is full\n");}}int pop(Stack *s) {if (s->top >= 0) {return s->data[s->top--]; } else {printf("Stack is empty\n"); return -1;}}int evaluatePostfix(char *exp) { Stack s;initStack(s);int i = 0;while (exp[i] != '\0') {if (isdigit(exp[i])) {push(s, exp[i] - '0');} else {int op2 = pop(s);int op1 = pop(s);switch (exp[i]) {case '+':push(s, op1 + op2);break;case '-':push(s, op1 - op2);break;case '*':push(s, op1 * op2);break;case '/':push(s, op1 / op2);break;default:printf("Invalid operator\n"); return -1;}}i++;}return pop(s);}int m本人n() {char exp[] = "12+3*";int result = evaluatePostfix(exp);printf("Result: d\n", result);return 0;}```五、总结本文介绍了利用栈来完成C语言中运算表达式的求值。