《数据结构课程设计算术表达式的求解》由会员分享，可在线阅读，更多相关《数据结构课程设计算术表达式的求解（18页珍藏版）》请在金锄头文库上搜索。
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错误1136.3错误2136.4错误3137.收获及体会：15参考文献：15II1.前言1.1课题内容及要求题
2、目39：算术表达式的求解问题描述：给定一个算术表达式，通过程序求出最后的结果。基本要求：从键盘输入要求解的算术表达式；采用栈结构进行算术表达式的求解过程；能够判断算术表达式正确与否；对于错误表达式给出提示；对于正确的表达式给出最后的结果；1.2选题目的及意义进一步熟悉和使用栈的基本操作，如栈的初始化，进栈，出栈的特性。学习在实际生活中使用栈来解决问题。2.系统分析2.1问题描述要正确计算表达式的值，必须要正确的解释表达式。首先解释算术表达式的运算规则，分为以下三点：先乘除后加减；从左往右进行计算；有括号的，先算括号内的；2.2运算符的优先级分析：任何一个表达式都是由运算符，操作数和界限符组成的
3、。这里把运算符，界限符统称为算符。设两个操作符分别为op1和op2。为实现运算符的优先法则，优先关系会出现三种情况，op1的优先级高于op2的优先级，op1的优先级等于op2的优先级，op1的优先级小于op2的优先级。2.3错误提示分析：对于输入错误的，比如出现了表达式以外的非法字符，没有按照正确格式进行输入。系统会给出提示。3.系统概要设计3.1系统总体架构设计算术表达式的求解栈模块运算模块定义栈的结构初始化栈入栈出栈取栈顶的元素判断优先级判断是否为运算符进行基本运算函数运算函数3.2系统模块的设计为了更好的服务，结合用户的需求，有如下的模块设计：程序主要包括三个模块：主函数设计模块int
4、main()函数体栈模块：一些本程序需要的操作，如初始化栈，定义栈，出栈，入栈，取栈顶元素。运算模块：对一些优先级的定义，以及基本的算术运算。4.系统详细设计4.1数据的存储设计与描述：为实现运算符的优先算法，可以用两个栈：运算符栈OPTR，操作数栈OPND。四则运算表达式算法的基本思想是：首先置操作数栈OPND为空栈，表达式起始符“#”为OPTR栈的栈底元素。依次读入表达式中的每个字符，是操作数则进栈OPND，是运算符就和OPTR栈的栈顶元素比较后，依据相应的优先权进行操作，直至整个表达式求值完毕（标志是两个运算符都为“#”）。4.2详细的优先级关系: Op2Op1+-*/（）#+-*/（#
5、=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); /进行出栈操作ElemType getTop(SeqStack *s); /提取栈顶元素函数运算：int Advan(int
6、 t1,int t2); /判断符号的优先级int In(int c); /判断c是否为运算符 int Oprea(int a,int theta,int b); /进行四则运算 int EvaluteExpression(); /进行算术表达式求值5.程序实现/stack.h 中#ifndef _STACK_H#define _STACK_H#define StackSize 100#define MaxLength 100typedef int ElemType;typedef structElemType dataStackSize;int top; SeqStack;void Init
7、(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 void Init(SeqStack *s) /初始化? s-top=-1; int IsFull
8、(SeqStack *s) /判断栈是否已满 return 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+; /栈顶指针加1 s-datas-top=x; /栈顶为新插入的值，data是数组，s-top数字 ElemType Pop(SeqStack *s) /进行出栈操作 if(IsEmpty(s)printf(栈是空的);exit(1
9、); return s-data s-top-; /先删除栈顶的元素，然后指针减一 ElemType getTop(SeqStack *s) /提取栈顶元素 if(IsEmpty(s)printf(栈是空的);exit(1); return s-data s-top; /operstack.h 中#ifndef _OPERSTACK_H#define _OPERSTACK-Hint Advan(int t1,int t2); /判断符号的优先级int In(int c); /判断c是否为运算符 int Oprea(int a,int theta,int b); /进行四则运算 int Eval
10、uteExpression(); /进行算术表达式求值 #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符号是 *， /时 case /:if(t1=*|t1=/|t1=)f=;elsef=;break;case (: /若t2符号是（，此时应该优先级小继续输入，而不进行运算 if(t1=)printf(ERROR 括号不匹配n);exit(0);elsef=;break;
