栈的表达式求值 数据结构(C语言)优秀课程设计

//算术表达式的求值//济南大学信息学院计算机数据结构课程设计/*【问题描述】表达式计算式实现程序设计语言的的基本问题之一，也是栈的应用的一个典型例子，设计一个程序，演示用运算符优先法对算术表达式的求值的过程。

*///main.cpp#include "iostream.h"#include "stdlib.h"#include "public.h"#include "stack.h"//using namespace std;LinkStack OPTR;//操作符栈int Allnum[100]={0}; //储存所有的运算数int NUM[100]={0};//操作数栈int n=0;void calcu(){int x1,x2,x;char p;//弹出一个运算符Pop(OPTR,p);//弹出两个操作数x2=NUM[n--];x1=NUM[n--];//进行一次运算switch(p) {case '+':x=x1+x2;break;case '-':x=x1-x2;break;case '*':x=x1*x2;break;case '/':x=x1/x2;//结果压入操作数栈NUM[++n]=x;}int EvaluateExpression(char *p){InitStack(OPTR);InitStack(OPND);int i=0;char temp;int num=0;while( *p!='\0' )switch(*p){case '+': case '-':while ( (GetTop(OPTR,temp))!=ERROR && (temp!='('))//执行先遇到的加、减运算calcu();//当前运算符进栈Push(OPTR,*p);//读下一个字符p++;break;case '*': case '/':if ( GetTop(OPTR,temp)==OK && (temp=='*') || (temp=='/')) //执行先遇到的乘、除运算calcu();//当前运算符进栈Push(OPTR,*p);//读下一个字符p++;break;case '('://左括号进栈Push(OPTR,*p);//读下一个字符p++;break;case ')':while ( GetTop(OPTR,temp)==OK && temp!='(' )//执行括号内的加、减、乘、除运算calcu();//弹出左括号char e;Pop(OPTR,e);//读下一个字符p++;break;default://把字符串转换成整数值//int num=strInt(p);num=0;do {num=10*num+*p-'0';p++;} while((*p>='0')&&(*p<='9'));//char strnum[10];//NumString(num,strnum);//将num转换为字符串strnum//操作数进栈NUM[++n]=num;//s1[++t1]=v;Allnum[i++]=num;};while ( GetTop(OPTR,temp)==OK )calcu();//返回结果//printf("%d \n",NUM[1]);return NUM[n];}//EvaluateExpressionvoid main(){char a[100];//="5+(9-2*3)^2+3*(2+1)"; //="5*(40+6)-39";5+(9-2*3)^2+3*(2+1)int i=0;start:cout<<"算数表达式:_" ;cin>>a;cout<<EvaluateExpression(a)<<endl;//system("pause");cout<<"----------------"<<endl;goto start;}//public.henum Status{OK,ERROR,}; //定义枚举类型int strInt(char *p){//把字符串转换成整数值int num=0;do {num=10*num+*p-'0';p++;} while((*p>='0')&&(*p<='9'));return num;}///////////数字转换字符串void convert(int abc,char a[],int &i_num){if( abc/10!=0 )convert(abc/10,a,i_num);a[i_num]=abc%10+'0';i_num++;}void NumString(int abc,char a[]){if(abc<0) abc=-abc;int i_num=0;convert(abc,a,i_num);a[i_num]='\0';}//////////////////stack.h//typedef char char;typedef struct SNode{char data; //数据域struct SNode *next; //指针域}SNode,*LinkStack; //定义链栈结点Status InitStack( LinkStack &S ){//将S初始化为一个空的链栈S=( LinkStack ) malloc ( sizeof( SNode ) );if( S==NULL ) return ERROR; //内存空间申请不成功S->next=NULL;return OK;}Status DestroyStack(LinkStack &S){//销毁栈SLinkStack p;while(S->next){p=S->next;S->next=p->next;free(p);}free(S);return OK;}Status StackIsEmpty(LinkStack S){//判断栈是否为空if (S->next==NULL) return OK;return ERROR;}Status Push(LinkStack &S, char e){//将数据元素e插入到栈S的栈顶LinkStack p;p=( LinkStack ) malloc ( sizeof( SNode ) );if( p==NULL ) return ERROR;p->data=e;p->next=NULL; //创建新结点p->next=S->next;S->next=p; //插入return OK;}Status Pop(LinkStack &S, char &e){//将栈S的栈顶元素出栈，并存放到e中LinkStack p;if( S->next==NULL ) return ERROR; //空队出错p=S->next; //记住要删除的结点S->next=p->next; //栈顶元素p出栈e=p->data;free(p); //释放存储空间return OK;}Status GetTop(LinkStack S, char &e){LinkStack p;//char e;if( S->next==NULL ) return ERROR; //空队出错p=S->next;e=p->data;return OK;}。

《数据结构》课程设计利用栈求表达式的值班级： 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设计内容.................................................................................... 错误!未指定书签。

2设计分析.................................................................................. 错误!未指定书签。

2.1后缀表达式设计 .................................................................. 错误!未指定书签。

2.2中缀到后缀的转换设计 ....................................................... 错误!未指定书签。

3设计实践 .................................................................................. 错误!未指定书签。

3.1实现要求 ............................................................................... 错误!未指定书签。

3.2中缀表达式求值 .................................................................. 错误!未指定书签。

3.3后缀表达式求值 .................................................................. 错误!未指定书签。

3.4 中缀表达式转换成后缀表达式 ......................................... 错误!未指定书签。

课程设计课程名称数据结构题目名称利用栈求表达式的值专业班级2014级网络工程(1)班学生姓名学号指导教师二○一六年六月十五日蚌埠学院计算机科学与技术系课程设计任务书蚌埠学院计算机科学与技术系本科课程设计成绩评定表目录1 概述 (6)1.1题目要求 (6)1.2输入要求 (6)1.3输出要求 (6)1.4实现要求 (7)2.需求分析 (8)2.1要求 (8)2.2任务描述 (8)2.3运行环境 (9)2.4开发工具 (9)3.总体设计 (10)3.1设计任务与目标 (10)3.2程序中的功能函数: (10)3.3方案设计与论证 (11)4算法说明 (12)4.1主要功能函数 (12)4.2函数间的调用关系 (13)4.4数据结构设计 (16)5 程序运行 (18)6 总结 (27)参考文献 (29)程序源代码 (30)1 概述栈是计算机中常用的一种数据结构，具有广泛的使用。

利用栈的性质及其操作原理编写一个使用栈计算表达式的程序有助于更好的掌握栈的使用规则和原理应用。

《数据结构课程设计》是理解和掌握数据结构的重要环节，主要任务是实现各种数据组织中的数据逻辑结构、存储结构以及有关操作的算法。

使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法。

另一方面，通过团队合作、文档编制、主页设计等环节对学生进行全方位的训练，最终达到培养学生的数据抽象能力和软件设计的能力。

通过全部过程培养和锻炼学生的钻研能力、动手能力、分析问题和解决问题的实际能力。

1.1题目要求(1)按照分析、设计、编码、调试、测试的软件过程完成这个应用程序。

(2)为各项操作功能设计一个菜单，应用程序运行后，先显示这个菜单，然后用户通过菜单项选择希望进行的操作项目。

1.2输入要求(1)应用程序运行后在屏幕上显示一个菜单。

用户可以根据需求，选定相应的操作项目。

进入每个操作后，根据应用程序的提示信息，从键盘输入相应的信息。

课程设计(论文)题目名称表达式求值问题课程名称数据结构课程设计学生姓名 XXX学号xxxxxxxxx系、专业信息工程系、信息工程类指导教师 xxxxxx2010年 1 月 3 日目录1 问题描述 (2)2 需求分析 (2)3 概要设计 (2)3．1抽象数据类型定义 (2)3．2模块划分 (3)4 详细设计 (4)4．1数据类型的定义 (4)4．2主要模块的算法描述 (4)5 测试分析 (7)5．1程序运行结果 (7)5．2程序调试与体会 (8)6 课程设计总结 (8)参考文献 (8)附录（源程序清单） (9)1 问题描述编写一个表达式求值程序，使输入一个四则运算表达式后，能够返回正确的结果。

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

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

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

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

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

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

3 概要设计3．1抽象数据类型定义设定栈抽象数据类型的定义采用两个栈的入栈与出栈的操作来进行“运算符和操作数的配对”。

程序中主要用到以下抽象数据类型：1）ADT Stack {数据对象：D＝{ ai | ai∈ElemSet, i=2,...,n,n≥0 }数据关系：R1＝{ <ai-1, ai >| ai-1, ai∈D, i=2,...,n }约定an端为栈顶，a1端为栈底。

利用栈实现表达式求值c语言要实现表达式求值，我们可以使用一个数据结构来保存操作的优先级和操作数。

在这个例子中，我们将使用栈。

下面是一个使用C语言实现的基本例子：```cinclude <>include <>include <>include <>define MAX_STACK_SIZE 100typedef enum {NUMBER,PLUS,MINUS,MUL,DIV} Token;typedef struct Stack {Token data[MAX_STACK_SIZE];int top;} Stack;void push(Stack stack, Token data) {if (stack->top == MAX_STACK_SIZE - 1) {printf("Stack is full\n");return;}stack->top++;stack->data[stack->top] = data;}Token pop(Stack stack) {if (stack->top == -1) {printf("Stack is empty\n");return NUMBER; // return some default value when stack is empty}Token data = stack->data[stack->top];stack->top--;return data;}bool isOperator(Token token) {return token == PLUS token == MINUS token == MUL token == DIV;}bool isLeftAssociative(Token token) {return token == PLUS token == MINUS;}bool isRightAssociative(Token token) {return token == MUL token == DIV;}Token getPriority(Token token) {if (token == PLUS token == MINUS) return 1; // + and - have higher priority than and /if (token == MUL token == DIV) return 2; // and / have higher priority than + and -return 0; // if token is not an operator, return 0 as default value }bool isOperatorPriorityHigher(Token op1, Token op2) {return getPriority(op1) > getPriority(op2); // higher priority means higher value of getPriority() function result}bool isOperatorPrioritySame(Token op1, Token op2) {return getPriority(op1) == getPriority(op2); // same priority means getPriority() function result is equal for both operators}void evaluateExpression() {Stack stack; // create a stack to store tokens (numbers and operators) in reverse order of their appearance in the expression string= -1; // initialize stack top to -1 to indicate an empty stackchar expression[] = "3+52"; // example expression stringchar token = strtok(expression, " "); // tokenize the expression stringwhile (token != NULL) {if (isdigit(token[0])) { // if token is a number, push it to the stack push(&stack, NUMBER); // push the number to the stackpush(&stack, (Token)(atoi(token))); // convert the string to an integer and push it to the stack} else if (isOperator(atoi(token))) { // if token is an operator, push it to the stackpush(&stack, (Token)(atoi(token))); // convert the string to an operator and push it to the stack}token = strtok(NULL, " "); // continue tokenizing the expression string}while ( != -1) {Token data = pop(&stack); // pop the topmost element from the stackif (isOperator(data)) { // if popped element is an operator, apply it to the top two elements of the stackToken op2 = pop(&stack); // pop the topmost element from the stackToken op1 = pop(&stack); // pop the next topmost element from the stackif (isLeftAssociative(data)) { // apply left associative operator push(&stack, op1); // push the operand on which the operator is applied first to the stackpush(&stack, op2); // push the second operand to the stackpush(&stack, data); // push the operator to the stack。

实验报告课程名称数据结构实验项目实验二--栈和队列实验系别___ _计算机学院 _ ______专业___ _计算机科学与技术___班级/学号__学生姓名 ____________实验日期成绩_______________________指导教师实验题目：实验二-----栈和队列实验一、实验目的1)掌握栈的顺序存储结构及队列的链式存储结构；2)验证栈的顺序存储结构的操作的实现；3)验证队列的链式存储结构的操作的实现；4)理解算法与程序的关系，能够将算法转换为对应程序。

二、实验内容1)建立一个顺序存储的空栈，并以此分别实现入栈、出栈、取栈顶元素；2)建立一个链式结构的空队列，并以此分别实现入队、出队、取队头等基本操作；3)尝试利用栈和队列的算法解决一些实际的应用问题。

设计与编码1)实验题目主要需求说明2)设计型题目：表达式求值（要求利用栈结构和运算符优先约定表，输入一个表达式，并计算求值）3)结合题目，说明利用栈或队列解决问题的基本算法描述4)程序源码#include<iostream>using namespace std;const int InitSize=100;const int IncreastSize=10;template<class datatype>class SqStack {private:datatype *base;datatype *top;int stacksize;public:SqStack();void DestroyStack();void ClearStack();int StackLength();bool IsEmpty();bool GetTop(datatype &e);bool Pop(datatype &e);bool Push(datatype e);};template<class datatype>SqStack<datatype>::SqStack(){base=new datatype[InitSize];if(!base)exit(1);top=base;stacksize=InitSize;}template<class datatype>void SqStack<datatype>::DestroyStack() {delete[] base;base=top=NULL;stacksize=0;}template<class datatype>void SqStack<datatype>::ClearStack() {top=base;}template<class datatype>int SqStack<datatype>::StackLength() {return top-base;}template<class datatype>bool SqStack<datatype>::IsEmpty() {if(top==base)return fasle;else return true;}template<class datatype>bool SqStack<datatype>::GetTop(datatype &e){if(top==base)return false;e=*(top-1);return true;}template<class datatype>bool SqStack<datatype>::Pop(datatype &e){if(top==base)return false;e=*(top-1);top--;return true;}template<class datatype>bool SqStack<datatype>::Push(datatype e){if(top-base>=stacksize){base=(datatype *)realloc( base , (stacksize+IncreastSize)*sizeof(int) ); if(!base)exit(1);top=base+stacksize;stacksize+=IncreastSize;}*(top)=e;top++;return true;}int com(char m,char t){if(t=='(') return -1;else if(t==')'){if(m=='+'||m=='-'||m=='*'||m=='/') return 1; else if(m=='(') return 0;else return -2;}else if(t=='*'||t=='/'){if(m=='+'||m=='-'||m=='#'||m=='(') return -1; else return 1;}else if(t=='+'||t=='-'){if(m=='#'||m=='(') return -1;else return 1;}else{if(m=='#')return 0;else if(m=='+'||m=='-'||m=='*'||m=='/') return 1; else return -2;}}void main(){SqStack <char> op;SqStack <double> re;char t,m;double result,flag=1;op.Push('#');t=getchar();while(true){if(t>='0'&&t<='9'){double s=0;s=s*10+t-'0';t=getchar();while(t>='0'&&t<='9' ){s=s*10+t-'0';t=getchar();}re.Push(s);}else if(t=='+'||t=='-'||t=='*'||t=='/'||t=='('||t==')'||t=='\n') { op.GetTop(m);while(com(m,t)==1 ){double x1,x2;op.Pop(m);if(re.Pop(x2)&&re.Pop(x1)){if(m=='+') re.Push(x1+x2);else if(m=='-') re.Push(x1-x2);else if(m=='*') re.Push(x1*x2);else if(m=='/') {if(x2!=0)re.Push(x1/x2); else flag=0;} }else flag=0;op.GetTop(m);}if(com(m,t)==-1)op.Push(t);else if(com(m,t)==0)op.Pop(m);else flag=0;if(!op.GetTop(m)) break;t=getchar();}else t=getchar();}if(re.GetTop(result)&&flag)cout<<result<<endl;else cout<<"Input error!\n";}5)运行结果三、总结与心得。

《数据结构》课程设计报告专业计算机科学与技术班级（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用相应的函数。