数据结构算术表达式求解.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

II

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] 李文书．数据结构与算法应用实践教程．北京大学出版社．2012.02
[2] 戴文华 赵君喆．数据结构项目实训．人民邮电出版社．2012.09
[3] 李业丽 程晓锦 齐亚莉．数据结构实验教程（基于c语言）．清华大学出版社．2014.04

目 录
第一章 总论 1
1.1项目名称与承办单位 1
1.2研究工作的依据、内容及范围 1
1.3编制原则 3
1.4项目概况 3
1.5技术经济指标 5
1.6结论 6
第二章 项目背景及建设必要性 8
2.1项目背景 8
2.2建设的必要性 9
第三章 建设条件 11
3.1项目区概况 11
3.2建设地点选择 错误！未定义书签。
3.3项目建设条件优劣势分析 错误！未定义书签。
第四章 市场分析与销售方案 13
4.1市场分析 13
4.2营销策略、方案、模式 14
第五章 建设方案 15
5.1建设规模和产品方案 15
5.2建设规划和布局 15
5.3运输 18
5.4建设标准 18
5.5公用工程 20
5.6工艺技术方案 21
5.7设备方案 21
5.8节能减排措施 24
第六章 环境影响评价 25
6.1环境影响 25
6.2环境保护与治理措施 26
6.3评价与审批 28
第七章 项目组织与管理 29
7.1组织机构与职能划分 29
7.2劳动定员 29
7.3经营管理措施 30
7.4技术培训 30
第八章 劳动、安全、卫生与消防 31
8.1编制依据及采用的标准 31
8.2安全卫生防护原则 31
8.3自然灾害危害因素分析及防范措施 32
8.4生产过程中产生的危害因素分析及防范措施 32
8.5消防编制依据及采用的标准 34
8.6消防设计原则 35
8.7火灾隐患分析 35
8.8总平面消防设计 35
8.9消防给水设计 36
8.10建筑防火 36
8.11火灾检测报警系统 37
8.12预期效果 37
第九章 项目实施进度 38
9.1实施进度计划 38
9.2项目实施建议 38
第十章 项目招投标方案 40
10.1招标原则 40
10.2项目招标范围 40
10.3投标、开标、评标和中标程序 40
10.4评标委员会的人员组成和资格要求 42
第十一章 投资估算和资金筹措 43
11.1投资估算 43
11.2资金筹措及使用计划 45
第十二章 财务评价 47
12.1费用与效益估算 47
12.2财务分析 48
12.3不确定性分析 49
12.5财务评价结论 50
第十三章 建设合理性分析 51
13.1产业政策符合性分析 51
13.2清洁生产符合性分析 51
13.3规划符合性分析 51
13.4项目建设环保政策符合性分析 51
13.5环境承载性分析 51
13.6结论 52
第十四章 结论与建议 53

19