南京信息工程大学滨江学院数据结构课程设计

1、滨江学院数据结构课程设计题目 算术表达式的求解院系计算机系专业学生姓名学号指导教师李燕二一六年 六 月十日目录1.前言.11.1课题内容及要求 .11.2选题目的及意义 .12.系统分析 .22.1问题描述 .22.2运算符的优先级分析： .22.3错误提示分析： .23.系统概要设计 .33.1系统总体架构设计 .33.2系统模块的设计 .34.系统详细设计 .44.1数据的存储设计与描述： .44.2详细的优先级关系 : .44.3具体的操作集合： .45.程序实现 .66.程序测试 .136.1正确的结果 .136.2错误 1.136.3错误 2.136.4错误 3.137.收获及体会：

2、 .15I参考文献：15II1. 前言1.1 课题内容及要求题目 39：算术表达式的求解问题描述：给定一个算术表达式，通过程序求出最后的结果。基本要求：从键盘输入要求解的算术表达式；采用栈结构进行算术表达式的求解过程；能够判断算术表达式正确与否；对于错误表达式给出提示；对于正确的表达式给出最后的结果；1.2 选题目的及意义进一步熟悉和使用栈的基本操作，如栈的初始化，进栈，出栈的特性。学习在实际生活中使用栈来解决问题。12. 系统分析2.1 问题描述要正确计算表达式的值，必须要正确的解释表达式。首先解释算术表达式的运算规则，分为以下三点：先乘除后加减；从左往右进行计算；有括号的，先算括号内的；2

3、.2 运算符的优先级分析：任何一个表达式都是由运算符，操作数和界限符组成的。这里把运算符，界限符统称为算符。设两个操作符分别为op1和 op2。为实现运算符的优先法则，优先关系会出现三种情况，op1的优先级高于 op2的优先级， op1的优先级等于 op2的优先级， op1的优先级小于op2的优先级。2.3 错误提示分析：对于输入错误的，比如出现了表达式以外的非法字符，没有按照正确格式进行输入。系统会给出提示。23. 系统概要设计3.1 系统总体架构设计算术表达式的求解栈运模算块模块定初入出取判判进运义始栈栈栈断断行算栈化顶优是基函的栈的先否本数结元级为运构素运算算函符数3.2 系统模块的设计

4、为了更好的服务，结合用户的需求，有如下的模块设计：程序主要包括三个模块：主函数设计模块int main()函数体栈模块：一些本程序需要的操作，如初始化栈，定义栈，出栈，入栈，取栈顶元素。运算模块：对一些优先级的定义，以及基本的算术运算。34. 系统详细设计4.1 数据的存储设计与描述：为实现运算符的优先算法，可以用两个栈：运算符栈OPTR，操作数栈 OPND。四则运算表达式算法的基本思想是：首先置操作数栈 OPND为空栈，表达式起始符“ #”为 OPTR栈的栈底元素。依次读入表达式中的每个字符， 是操作数则进栈 OPND，是运算符就和 OPTR栈的栈顶元素比较后，依据相应的优先权进行操作， 直

5、至整个表达式求值完毕 （标志是两个运算符都为 “ #”）。4.2 详细的优先级关系 :Op2+-*/（）#Op1+-*/（#=4.3 具体的操作集合：栈的设计：typedef structElemType dataStackSize;int top; SeqStack;void Init(SeqStack *s);/初始化栈int IsFull(SeqStack *s);/判断栈是否已满int IsEmpty(SeqStack *s);/判断栈是否是空void Push(SeqStack *s,ElemType x);/进行入栈操栈ElemType Pop(SeqStack *s);/进行出栈

6、操作4ElemType getTop(SeqStack *s);/提取栈顶元素函数运算：int Advan(int t1,int t2);/判断符号的优先级int In(int c);/判断 c是否为运算符int Oprea(int a,int theta,int b); /进行四则运算int EvaluteExpression();/进行算术表达式求值55. 程序实现/stack.h中#ifndef _STACK_H#define _STACK_H#define StackSize 100#define MaxLength 100typedef int ElemType;typedef st

7、ructElemType dataStackSize;int top; SeqStack;void Init(SeqStack *s);/初始化栈int IsFull(SeqStack *s);/判断栈是否已满int IsEmpty(SeqStack *s);/判断栈是否是空void Push(SeqStack *s,ElemType x); /进行入栈操栈ElemType Pop(SeqStack *s);/进行出栈操作ElemType getTop(SeqStack *s); /提取栈顶元素#endif/stack.c中#include stack.h#include #include v

8、oid Init(SeqStack *s)/初始化 ?s-top=-1;int IsFull(SeqStack *s)/判断栈是否已满6return s-top=StackSize-1;int IsEmpty(SeqStack *s)/判断栈是否是空return s-top=-1;void Push(SeqStack *s,ElemType x)/进行入栈操栈if(IsFull(s)printf(栈已经溢出。 );exit(1);s-top+;/栈顶指针加 1s-datas-top=x;/栈顶为新插入的值，data 是数组， s-top 数字ElemType Pop(SeqStack *s)/

9、进行出栈操作if(IsEmpty(s)printf(栈是空的 );exit(1);return s-data s-top-;/先删除栈顶的元素，然后指针减一ElemType getTop(SeqStack *s)/提取栈顶元素if(IsEmpty(s)printf(栈是空的 );exit(1);return s-data s-top;7/operstack.h中#ifndef _OPERSTACK_H#define _OPERSTACK-Hint Advan(int t1,int t2);/判断符号的优先级int In(int c);/判断 c是否为运算符int Oprea(int a,int

10、 theta,int b);/进行四则运算int EvaluteExpression();/进行算术表达式求值#endif/operstack.c中#include stack.h#include #include #include operstack.hint Advan(int t1,int t2)/判断符号的优先级int f;switch(t2)case +:/若 t2 符号是“ +”“ - ”case -:if(t1=(|t1=#)f=;break;case *:/若 t2 符号是* ， / 时8case /:if(t1=*|t1=/|t1=)f=;elsef=;break;case

11、(: / 若 t2 符号是（，此时应该优先级小继续输入，而不进行运算 if(t1=)printf(ERROR括号不匹配 n);exit(0);elsef=;break;case #:/若 t2 取出时是 #，表示已经要计算最后一个表达式了switch(t1)case #:f=;break;case (:printf(ERROR缺少右括号 n);exit(0);default:f=;9return f;int In(int c)/判断 c是否为运算符switch(c)case +:case -:case *:case /:case (:case ):case #:return 1;default

12、 :return 0;int Oprea(int a,int theta,int b)/进行四则运算int c;switch(theta)case +:c=a+b;break;case -:c=a-b;break;case *:c=a*b;break;case /:10c=a/b;break;return c;int EvaluteExpression()/进行算术表达式求值SeqStack OPTR,OPND;/构建两个栈，一个是放操作符，一个是放数据int a,b,d,x,theta;char c;/存放键盘接收的字符char z6;/存放整数串int i;Init(&OPTR);/初始化

13、运算符栈Push(&OPTR,#);/#入栈， #是表达式结束的标志Init(&OPND);/初始化数据栈c=getchar();/从键盘读入下一个字符到cx=getTop(&OPTR);/x赋值为运算符栈顶元素while(c!=#|x!=#)/当读入两个字符都为#时，则停止，返回最后的/结果 X的值，否则继续进行运算if(In(c)/是运算符switch(Advan(x,c)case :theta=Pop(&OPTR);/优先级高， 此时进行运算 , 从操/ 作栈中取出一个运算符b=Pop(&OPND);/从数据栈中取出两个数a=Pop(&OPND);Push(&OPND,Oprea(a,theta,b); /然后通过这两个数进行运算11else if(c=0&c=0&c=9);zi=0;/整数串结束d=atoi(z);/将字符串转化为整数放入d中Push(&OPND,d);/一个整数入到数据栈中else/两者以外显然不可能，出错printf(ERROR出现了非法的字符，表达式不符合格式n);exit(0);x=getTop(&OPTR);x=getTop(&OPND);return x;126. 程序测试6.1 正确的结果6.2 错误 16.3 错误 26.4