数据结构课程设计-算术表达式的求解.doc

滨江学院 数据结构课程设计题 目 算术表达式的求解院 系 计算机系 专 业 学生姓名 学 号 指导教师 李燕 二一六 年 六 月十日目 录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课题内容及要求题目39：算术表达式的求解问题描述：给定一个算术表达式，通过程序求出最后的结果。基本要求：从键盘输入要求解的算术表达式；采用栈结构进行算术表达式的求解过程；能够判断算术表达式正确与否；对于错误表达式给出提示；对于正确的表达式给出最后的结果；1.2选题目的及意义进一步熟悉和使用栈的基本操作，如栈的初始化，进栈，出栈的特性。学习在实际生活中使用栈来解决问题。2.系统分析2.1问题描述要正确计算表达式的值，必须要正确的解释表达式。首先解释算术表达式的运算规则，分为以下三点：先乘除后加减；从左往右进行计算；有括号的，先算括号内的；2.2运算符的优先级分析：任何一个表达式都是由运算符，操作数和界限符组成的。这里把运算符，界限符统称为算符。设两个操作符分别为op1和op2。为实现运算符的优先法则，优先关系会出现三种情况，op1的优先级高于op2的优先级，op1的优先级等于op2的优先级，op1的优先级小于op2的优先级。2.3错误提示分析：对于输入错误的，比如出现了表达式以外的非法字符，没有按照正确格式进行输入。系统会给出提示。3.系统概要设计3.1系统总体架构设计算术表达式的求解栈模块运算模块定义栈的结构初始化栈入栈出栈取栈顶的元素判断优先级判断是否为运算符进行基本运算函数运算函数3.2系统模块的设计为了更好的服务，结合用户的需求，有如下的模块设计：程序主要包括三个模块：主函数设计模块int main()函数体栈模块：一些本程序需要的操作，如初始化栈，定义栈，出栈，入栈，取栈顶元素。运算模块：对一些优先级的定义，以及基本的算术运算。4.系统详细设计4.1数据的存储设计与描述：为实现运算符的优先算法，可以用两个栈：运算符栈optr，操作数栈opnd。四则运算表达式算法的基本思想是：首先置操作数栈opnd为空栈，表达式起始符“#”为optr栈的栈底元素。依次读入表达式中的每个字符，是操作数则进栈opnd，是运算符就和optr栈的栈顶元素比较后，依据相应的优先权进行操作，直至整个表达式求值完毕（标志是两个运算符都为“#”）。4.2详细的优先级关系: op2op1+-*/（）#+-*/（#=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 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(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(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); 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 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符号是 *， /时 case /:if(t1=*|t1=/|t1=)f=;elsef=;break;case (: /若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=; return f;int in(int c) /判断c是否为运算符 switch(c)case +:case -:case *:case /:case (:case ):case #:return 1;default :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 /:c=a/b;break;return c; int evaluteexpression() /进行算术表达式求值 seqstack optr,opnd; /构建两个栈，一个是放操作符，一个是放数据 int a,b,d,x,theta;char c; /存放键盘接收的字符 char z6; /存放整数串 int i;init(&optr); /初始化运算符栈 push(&optr,#); /#入栈，#是表达式结束的标志 init(&opnd); /初始化数据栈 c=getchar(); /从键盘读入下一个字符到c x=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); / 然后通过这两个数进行运算else 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; 6.程序测试6.1正确的结果6.2错误16.3错误26.