南京信息综合重点工程大学滨江学院数据结构优秀课程设计.doc

滨江学院

数据结构课程设计

题 目 算术表示式求解
院 系 计算机系
专 业
学生姓名
学 号
指导老师 李燕

二Ｏ一六 年 六 月十日

目 录
1.序言 1
1.1课题内容及要求 1
1.2选题目标及意义 1
2.系统分析 2
2.1问题描述 2
2.2运算符优先级分析： 2
2.3错误提醒分析： 2
3.系统概要设计 3
3.1系统总体架构设计 3
3.2系统模块设计 3
4.系统具体设计 4
4.1数据存放设计和描述： 4
4.2具体优先级关系: 4
4.3具体操作集合： 4
5.程序实现 6
6.程序测试 13
6.1正确结果 13
6.2错误1 13
6.3错误2 13
6.4错误3 13
7.收获及体会： 15
参考文件： 15

1.序言
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具体优先级关系:
Op2
Op1
+
-
*
/
（
）
#
+
>
>
<
<
<
>
>
-
>
>
<
<
<
>
>
*
>
>
>
>
<
>
>
/
>
>
>
>
<
>
>
（
<
<
<
<
<
=

）
>
>
>
>

>
>
#
<
<
<
<
<

=

4.3具体操作集合：
栈设计：
typedef struct{
ElemType data[StackSize];
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 100

typedef int ElemType;
typedef struct{
ElemType data[StackSize];
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 <stdio.h>
#include <stdlib.h>
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->data[s->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-H

int 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 <stdio.h>
#include <stdlib.h>
#include "operstack.h"

int Advan(int t1,int t2) //判定符号优先级
{
int f;
switch(t2)
{
case '+': //若t2符号是“+”“-”
case '-':
if(t1=='('||t1=='#')
f='<';
else
f='>';
break;

case '*': //若t2符号是 *， /时
case '/':
if(t1=='*'||t1=='/'||t1==')')
f='>';
else
f='<';
break;
case '(': //若t2符号是（，此时应该优先级小继续输入，而不进行运算
if(t1==')'){
printf("ERROR 括号不匹配\n");
exit(0);
}
else
f='<';
break;
case ')': //若t2符号是），此时一个括号已经完整，应该进行运算
switch(t1)
{
case '(':f='=';
break;
case '#':printf("ERROR 缺乏左括号\n");
exit(0);
default:f='>';
}
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 z[6]; //存放整数串
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 '<':Push(&OPTR,c); //优先级低 ，继续进行输入
c=getchar();
break;
case '=':x=Pop(&OPTR); //脱括号并计算下一个值
c=getchar();
break;
case '>':theta=Pop(&OPTR); //优先级高，此时进行运算,从操 //作栈中取出一个运算符
b=Pop(&OPND); //从数据栈中取出两个数
a=Pop(&OPND);
Push(&OPND,Oprea(a,theta,b)); // 然后经过这两个数进行运算 }

}else if(c>='0'&&c<='9'){ //是数字
i=0;
do{
z[i]=c;
i++;
c=getchar();
}while(c>='0'&&c<='9');
z[i]=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错误1

6.3错误2

6.4错误3

7.收获及体会：
该程序经过调试已经能够运行，而且能够正确输出答案和错误提醒。
经过此次数据结构课程设计，能够愈加深刻体会栈特点，更熟悉栈相关操作，和怎样利用栈相关知识处理生活中实际问题。

参考文件：
[1] 李文书．数据结构和算法应用实践教程．北京大学出版社．.02
[2] 戴文华 赵君喆．数据结构项目实训．人民邮电出版社．.09
[3] 李业丽 程晓锦 齐亚莉．数据结构试验教程（基于c语言）．清华大学出版社．.04