数据结构课程设计表达式翻译.doc

数据结构课程考核报告

表达式的翻译

学号：
姓名：
专业： 软件工程专业
班级： 15级云计算1班
指导教师：

南 阳 理 工 学 院 软 件 学 院
2016年12月

目录

1.需求分析-------------------------------------------------------------------3

1.1问题描述---------------------------------------------------------------3

1.2基本要求---------------------------------------------------------------3

2.系统设计-------------------------------------------------------------------3

3.程序流程图-----------------------------------------------------------------4

4.类关系图-------------------------------------------------------------------6

5. 实现代码------------------------------------------------------------------7

6.个人总结-------------------------------------------------------------------7

7.参考书目-------------------------------------------------------------------7

一．需求分析
1.1问题描述
编写完整程序，将中缀表达式翻译成后缀表达式。表达式由操作数 ( 变量 ) 、操作 ( 运算符 ) 以及小括弧 “ （ ” 和 “ ） ” 组成，其中：(1)操作包括算术运算、关系运算和逻辑运算三类；(2)操作数为单个字符或由字母和数字任意多个字符构成；(3)能够识别出简单的错误，如括弧不匹配。
1.2 基本要求
输入：中缀表达式，80个字符以内。
输出：运算结果
功能：将中缀表达式转化为后缀表达式

二．系统设计
根据题目要求，将中缀表达式转化为后缀表达式。问题的解决方案有两种，分别是利用栈结构实现算数表达式的四则运算或者利用二叉树把中缀表达式转化为前缀表达式，我选择栈结构与树结构相结合来实现算数表达式的转化。
算法思想：
①：运用栈和队列来将中缀转换为后缀，栈用来储存字符，队列用来存储后缀表达式。
②：输入字符串c，若是数字的话直接进入队列，若是符号，为‘*’‘/’‘（’，则线检查栈中的栈顶元素，前提是栈不为空，若栈不为空的话，栈顶元素为‘*’||‘/’，则先将栈中的元素入队，如果栈顶是‘+’‘-’这些优先级小的，则直接将c入栈。
③：如果c是优先级为“+”“-”的字符，先看一下栈是否为空，接着判断栈顶元素是否为“（”，若是，则继续将c进栈，否则的话，将栈中的元素全部出栈，直到栈空。
④：若c为“）”则将栈中所有符号弹栈并进入队列。
⑤：若c为“#”，则结束，并将栈中的剩余的符号全部入队列。
⑥：打印队列中的，出队打印。

开始
三． 程序流程图
输入一个字符串c

else if
C!=’#’

Ifc!=’.’||c<9||c>0

If(!c!=’.’||c<9||c>0)

若为数
存入数组,i=1

else if
将数组中第0个存到队列中

If(c'*'||c=’/’||c=’(’)

else if
If(c'+'||c=’-’)

If(c=’)’)
If栈空
栈顶出栈给c2

while栈空
栈顶出栈给e
else if
If(c2=’*’||c2=’/’)

栈顶出栈入队操作
If(e!=’(’
’)
栈顶出栈入队操作
栈顶元素出栈
c2进栈后c进栈
c2进队列
c入栈

else if
e==’(’

else if

while栈空
e==’#’
入栈

栈中剩余的出栈入队操作

结束

四． 类关系图
(1) .头文件：
#include<stdio.h>
#include<stdlib.h>
(2)
宏定义：
#define OK 1
#define ERROR 0
#define STACK_SIZE 20
#define STACK_INCREMENT 10
#define QUEUE_SIZE 20
(3) 栈的定义结构体
typedef int Status;
typedef char StackElemtype; //栈的类型
typedef struct Stack{
StackElemtype* base;
StackElemtype* top;
int stackSize;
}Stack;
(5)初始化栈：
Status StackInit(Stack* s)
(6)出栈：
Status Pop(Stack* s,StackElemtype* value)
(7)进栈：
Status Push(Stack* s,StackElemtype value)
(8)求栈的长度：
int StackLength(Stack s)
(9)定义队列的结构体：
typedef double QueueElemtype;
typedef char QueueOperatorValue;
typedef struct QueueNode{ //定义队列结构体
QueueElemtype data;
QueueOperatorValue operator;
struct QueueNode* next;
int flag;
}QueueNode,*QueueNodePtr;
typedef struct Queue{
QueueNodePtr front;
QueueNodePtr rear;
}Queue;
(10)初始化队列
Status QueueInit(Queue* q)
(11)队列的插入：
Status QueueInsert(Queue* q,QueueElemtype value)
(12)出队列
Status QueueInsert_operatorValue(Queue* q,QueueOperatorValue value)
(13)中缀转后缀函数
Status Infix2Postfix(Queue* q)
(14)打印后缀表达式
Status ShowQueue(Queue q)
(15)主函数
int main(){
Queue q;
QueueInit(&q);
Infix2Postfix(&q);
ShowQueue(q);
return 0;
}

五． 运行截图

六．实现代码
#include<stdio.h>
#include<stdlib.h>

#define OK 1
#define ERROR 0
#define STACK_SIZE 20
#define STACK_INCREMENT 10
#define QUEUE_SIZE 20

typedef int Status;

typedef char StackElemtype; //栈的类型
typedef struct Stack{
StackElemtype* base;
StackElemtype* top;
int stackSize;
}Stack;
Status StackInit(Stack* s){ //初始化栈
s->base = (StackElemtype*)malloc(sizeof(StackElemtype) * STACK_SIZE); //申请栈的空间
if( !s->base )
return ERROR;
s->top = s->base;
s->stackSize = STACK_SIZE;
return OK;
}
Status Pop(Stack* s,StackElemtype* value){ //出栈操作
if( s->base == s->top ){
printf("\nstack empty\n");
return ERROR;
}
*value = *(--(s->top));
return OK;
}
Status Push(Stack* s,StackElemtype value){ //进栈操作
if( s->top - s->base == s->stackSize){

s->base = (StackElemtype*)realloc(s->base,sizeof(StackElemtype) * (STACK_INCREMENT + STACK_SIZE));
if( !s->base )
return ERROR;
s->top = s->base + STACK_SIZE;
s->stackSize = STACK_SIZE + STACK_INCREMENT;
}
*(s->top) = value;
s->top++;
return OK;
}
int StackLength(Stack s){ //求栈的长度
return s.top - s.base;
}
typedef double QueueElemtype;
typedef char QueueOperatorValue;
typedef struct QueueNode{ //定义队列结构体
QueueElemtype data;
QueueOperatorValue operator;
struct QueueNode* next;
int flag;
}QueueNode,*QueueNodePtr;
typedef struct Queue{
QueueNodePtr front;
QueueNodePtr rear;
}Queue;

Status QueueInit(Queue* q){ //队列初始化
q->front = (QueueNodePtr)malloc(sizeof(QueueNode));
if( !q->front )
return ERROR;
q->rear = q->front;
q->rear->next = NULL;
return OK;
}
Status QueueInsert(Queue* q,QueueElemtype value){ //队列插入
QueueNodePtr new;
new = (QueueNodePtr)malloc(sizeof(QueueNode));
if( !new )
return ERROR;
new->data = value;
new->flag = 1;
new->next = NULL;
q->rear->next = new;
q->rear = new;
return OK;
}
Status QueueInsert_operatorValue(Queue* q,QueueOperatorValue value){
QueueNodePtr new;
new = (QueueNodePtr)malloc(sizeof(QueueNode));
if( !new )
return ERROR;
new->operator = value;
new->flag = 0;
new->next = NULL;
q->rear->next = new;
q->rear = new;
return OK;
}
//利用栈将中缀表达式转化为后缀表达式：
Status Infix2Postfix(Queue* q){

Stack s;
StackInit(&s);
char c,e;
char bufferDigit[10];
int i = 0;
double longDigit;
printf("\n");
printf("\n");
printf("\n");
printf(" <欢迎使用表达式翻译器> \n");
printf("\n");
printf(" ********* 请输入表达式 *********\n");
printf(" ********* 结束符号为'#' *********\n");
scanf("%c", &c);
while( '#' != c){
while( c <= '9' && c >= '0' || '.' == c ){
bufferDigit[i++] = c;
bufferDigit[i] = '\0';
scanf("%c", &c);
if(!((c <= '9' && c >= '0' ) || '.' == c )){
longDigit = atof(bufferDigit);
QueueInsert(q,longDigit);
i = 0;
}
}
if( '(' == c || '*' == c || '/' == c ){
if(c=='/'||c=='*'){
Pop(&s, &e);
if(e=='/'||e=='*'){

QueueInsert_operatorValue(q, e);

}
if(e=='+'||e=='-'){

Push(&s,e);

}
}
Push(&s, c);
}
else if( '+' == c || '-' == c ){
if( !StackLength(s) )
Push(&s, c);
else{
Pop(&s, &e);
while( '(' != e ){
QueueInsert_operatorValue(q, e);
if( StackLength(s) == 0 ){
break;
}else
Pop(&s, &e);
}
if( '(' == e )
Push(&s, e);
Push(&s, c);
}
}else if( ')' == c ){
Pop(&s, &e);
while( '(' != e ){
QueueInsert_operatorValue(q, e);
Pop(&s, &e);
}
}else if( '#' == c){
break;
}else{
printf("input ERROR!\n");
return ERROR;
}
scanf("%c", &c);
}
while(StackLength(s)){
Pop(&s, &e);
QueueInsert_operatorValue(q, e);
}
QueueInsert_operatorValue(q,'#');
return OK;
}
Status ShowQueue(Queue q){
printf("The Reverse Polish Notation is:");
if(q.front == q.rear){
printf("Queue Empty");
return ERROR;
}
QueueNodePtr p = q.front->next;
while(p != q.rear){
if(p->flag)
printf("%g ", p->data);
else
printf("%c ", p->operator);
p = p->next;
}
printf("\n");
return OK;
}
int main(){
Queue q;
QueueInit(&q);
Infix2Postfix(&q);
ShowQueue(q);
return 0;
}

七. 个人总结
这个课程设计为期一周，在每一次的课程设计都给我很大的收获，至少是能彻底的把思想给明白，首先，在写这个课程设计之前，一直都在想后缀的优点和他的功能，每一次电脑运算的时候，转换成后缀都不需要进行运算符的优先级比较，这是一回事，另外后缀运算能力明显提升，时间复杂度提升不少。在写的过程中有一点没有考虑进去，我的思路是在遇到乘号和除号的时候直接入栈，结果经过老师的验收把这个bug给找出来，经过仔细思考把代码给改正确了，所以说，如果直接把思想能够弄清的话，那么写代码是很轻松的。以后要把代码的思想牢牢掌握在脑中。这样才能提升自己的编程能力。

八.参考书目
[1] 谭浩强 C++程序设计（第三版）清华大学出版社
[2] 严蔚敏 数据结构（C语言版）清华大学出版社 1999
[3] 与所用编程环境相配套的C++相关的资料

目 录
第一章 总论 1
第一节 项目背景 1
第二节 项目概况 2
第二章 项目建设必要性 5
第三章 市场分析与建设规模 7
第一节 汽车市场需求分析 7
第二节 市场预测 12
第三节 项目产品市场分析 13
第四节 建设规模 16
第四章 场址选择 17
第一节 场址所在位置现状 17
第二节 场址建设条件 17
第五章 技术方案、设备方案、工程方案 22
第一节 技术方案 22
第二节 设备方案 28
第三节 工程方案 33
第六章 原材料、燃料供应 38
第七章 总图布置与公用辅助工程 39
第一节 总图布置 39
第二节 公用辅助工程 43
第八章 环境影响评价 52
第一节 环境保护设计依据 52
第二节 项目建设和生产对环境的影响 52
第三节 环境保护措施 54
第四节 环境影响评价 56
第九章 劳动安全卫生与消防 57
第一节 劳动安全卫生 57
第二节 消防 64
第十章 节能与节能措施 67
第一节 项目概况 67
第二节 项目综合能耗 69
第三节 节约及合理利用能源的主要措施 71
第十一章 项目实施进度与人力资源配置 76
第一节 建设工期 76
第一节 项目实施进度 76
第二节 生产组织与人员培训 79
第十二章 投资估算与资金筹措 82
第一节 建设投资估算 82
第二节 总投资估算 86
第三节 资金筹措 86
第十四章 财务效益分析 88
第一节 财务评价基础数据与参数选取 88
第二节 销售收入及销售税金估算 89
第三节 成本费用估算 89
第四节 财务评价 91
第五节 不确定性分析 93
第十三章 风险分析 95
第十四章 结论与建议 97
第一节 研究结论 97
第二节 建议 97