《数据结构与算法设计》实验2.doc

《数据结构与算法设计》
实验报告
——实验二

学院：自动化学院
班级：
学号：
姓名：

一、实验目的
按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。
二、实验内容
简单计算器。
请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。要求：
① 从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。
② 输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取整。
例如，输入：4+2*5= 输出：14
输入：(4+2)*(2-10)= 输出：-48

三、程序设计
概要设计
1、宏定义
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
2、基本函数：
（1）void InitStack_char(SqStack *S) //char型栈初始化
（2）void InitStack_int(sqStack *S) //int型栈初始化
（3）void Push_char(SqStack *S,char ch) //char型元素进栈
（4）void Push_int(sqStack *S,int num) //int型元素进栈
（5）char GetTop_char(SqStack *S) //取char型栈顶元素
（6）int GetTop_int(sqStack *S) //取int型栈顶元素
（7）Status In(char c) //判断是否为运算符，若是运算符则返回，否则返回
（8）char Precede(char a,char b) //判断两运算符的先后次序
（9）Status Pop_char(SqStack *S,char &x) //char型栈出栈
（10）Status Pop_int(sqStack *S,int &x) //int型栈出栈
（11）int Operate(int a,char theta,int b) //计算a和b运算结果
3、流程图

详细设计

数据类型
typedef struct node //构造char型栈
{
char ch;
struct node *next;
}node;
typedef struct
{
struct node *base;
struct node *top;
}SqStack;

typedef struct lnode //构造int型栈
{
int num;
struct lnode *next;
}lnode;
typedef struct
{
struct lnode *base;
struct lnode *top;
}sqStack;
操作部分
void InitStack_char(SqStack *S)
{
S->base = (node *)malloc(sizeof(node));
S->base->next=NULL;
S->top = S->base;
} //char型栈初始化

void InitStack_int(sqStack *S)
{
S->base = (lnode *)malloc(sizeof(lnode));
S->base->next=NULL;
S->top = S->base;
} //int型栈初始化

void Push_char(SqStack *S,char ch)
{
node *p;
p=(node*)malloc(sizeof(node));
p->ch=ch;
p->next=S->top;
S->top=p;
} //char型元素进栈

Status Push_int(sqStack *S,int num)
{
lnode *p;
p=(lnode*)malloc(sizeof(lnode));
p->num=num;
p->next=S->top;
S->top=p;
return OK;
} //int型元素进栈

char GetTop_char(SqStack *S)
{
return (S->top->ch);
} //取char型栈顶元素

int GetTop_int(sqStack *S)
{
return (S->top->num);
} //取int型栈顶元素

Status Pop_char(SqStack *S,char &x)
{
if(S->base == S->top)
return ERROR;
node *p;
p=S->top;
x=p->ch;
S->top=p->next;
free(p);
return OK;
} //char型栈出栈

Status Pop_int(sqStack *S,int &x)
{
if(S->base == S->top)
return ERROR;
lnode *p;
p=S->top;
x=p->num;
S->top=p->next;
free(p);
return OK;
} //int型栈出栈
计算功能
int Operate(int a,char theta,int b)
{
int i,z = 1;
switch(theta)
{
case '+':z = (a + b);break;
case '-':z = (a - b);break;
case '*':z = (a * b);break;
case '/':z = (a / b);break;
case '^':
for(i = 1;i<=b;i++)
z = z*a;
break;
}
return (z);
} //计算a和b运算结果

Status In(char c)
{
if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='='||c=='^')
return OK;
else
return ERROR;
} //判断是否为运算符

char Precede(char a,char b)
{
if(a=='+'||a=='-')
{
if(b=='+'||b=='-'||b==')'||b=='=')
return '>';
else
return '<';
}
if(a=='*'||a=='/')
{
if(b=='('||b=='^')
return '<';
else
return '>';
}
if(a=='(')
{
if(b==')')
return '=';
else
return '<';
}
if(a==')')
{
if(b!='(')
return '>';
}
if(a=='#')
{
if(b=='=')
return '=';
else
return '<';
}
if(a=='^')
return ('>');
} //判断两运算符的先后次序
主函数
int main() //主函数
{
char c,x,theta;
int a,b,c1; //定义变量
SqStack OPTR; //定义字符栈
sqStack OPNR; //定义整型栈
InitStack_char(&OPTR); //初始化
InitStack_int(&OPNR); //初始化
Push_char(&OPTR,'#'); //将字符型栈底设为#
c = getchar(); //从键盘输入得到字符
while(c!='='||GetTop_char(&OPTR)!='#') //判定是否执行循环
{
if(!In(c))
{
c1 = 0;
while(!In(c))
{
c1 = c1*10+c-'0';
c = getchar();
}
Push_int(&OPNR,c1);
} //当扫描字符不是运算符时，转化为整型数存入栈中
else
{
switch(Precede(GetTop_char(&OPTR),c)) //判定运算符的优先关系
{
case '<':
Push_char(&OPTR,c);c = getchar();break; //当前运算符优先级高，存入char栈
case '=':
Pop_char(&OPTR,c);c = getchar();break; //运算符次序相等，存入char栈
case '>': //当前运算符优先级低
Pop_char(&OPTR,theta);
Pop_int(&OPNR,b);
Pop_int(&OPNR,a);
Push_int(&OPNR, Operate(a,theta,b));//计算运算结果，并存入int栈
break; //继续循环
}
}
}
printf("%d\n",GetTop_int(&OPNR)); //计算完成，取出int栈顶元素，并输出
return 0;
}四、程序调试分析
编写程序的过程中遇到了很多的问题，最突出的两个问题就是整数和两位数的运算处理，一开始修改了主函数部分之后，原来可以执行一位数运算的程序出现了error，由于没有及时保存，并且之前的代码无法恢复，只得重新编写一次。第二次编写理清思路之后，在课本和网上资料的辅助下，终于成功的编出了程序并且可以完美执行。经验告诉了我在编程的时候一定要注意经常进行调试，只有学会调试才能处理好大程序的编写，否则极其容易出错。
五、用户使用说明
1.运行程序，
2.将整个表达式从键盘键入，以“=”结束，回车可得到结果。
六、程序运行结果
（1）输入：（11+3）*5= 输出：70
（2）输入：(31-13)/(9-3)= 输出：6

七、程序清单
#include<stdio.h>
#include<stdlib.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status;

typedef struct node //构造char型栈
{
char ch;
struct node *next;
}node;
typedef struct
{
struct node *base;
struct node *top;
}SqStack;

typedef struct lnode //构造int型栈
{
int num;
struct lnode *next;
}lnode;
typedef struct
{
struct lnode *base;
struct lnode *top;
}sqStack;

void InitStack_char(SqStack *S)
{
S->base = (node *)malloc(sizeof(node));
S->base->next=NULL;
S->top = S->base;
} //char型栈初始化

void InitStack_int(sqStack *S)
{
S->base = (lnode *)malloc(sizeof(lnode));
S->base->next=NULL;
S->top = S->base;
} //int型栈初始化

void Push_char(SqStack *S,char ch)
{
node *p;
p=(node*)malloc(sizeof(node));
p->ch=ch;
p->next=S->top;
S->top=p;
} //char型元素进栈

Status Push_int(sqStack *S,int num)
{
lnode *p;
p=(lnode*)malloc(sizeof(lnode));
p->num=num;
p->next=S->top;
S->top=p;
return OK;
} //int型元素进栈

char GetTop_char(SqStack *S)
{
return (S->top->ch);
} //取char型栈顶元素

int GetTop_int(sqStack *S)
{
return (S->top->num);
} //取int型栈顶元素

Status Pop_char(SqStack *S,char &x)
{
if(S->base == S->top)
return ERROR;
node *p;
p=S->top;
x=p->ch;
S->top=p->next;
free(p);
return OK;
} //char型栈出栈

Status Pop_int(sqStack *S,int &x)
{
if(S->base == S->top)
return ERROR;
lnode *p;
p=S->top;
x=p->num;
S->top=p->next;
free(p);
return OK;
} //int型栈出栈

int Operate(int a,char theta,int b)
{
int i,z = 1;
switch(theta)
{
case '+':z = (a + b);break;
case '-':z = (a - b);break;
case '*':z = (a * b);break;
case '/':z = (a / b);break;
case '^':
for(i = 1;i<=b;i++)
z = z*a;
break;
}
return (z);
} //计算a和b运算结果

Status In(char c)
{
if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='='||c=='^')
return OK;
else
return ERROR;
} //判断是否为运算符

char Precede(char a,char b)
{
if(a=='+'||a=='-')
{
if(b=='+'||b=='-'||b==')'||b=='=')
return '>';
else
return '<';
}
if(a=='*'||a=='/')
{
if(b=='('||b=='^')
return '<';
else
return '>';
}
if(a=='(')
{
if(b==')')
return '=';
else
return '<';
}
if(a==')')
{
if(b!='(')
return '>';
}
if(a=='#')
{
if(b=='=')
return '=';
else
return '<';
}
if(a=='^')
return ('>');
} //判断两运算符的先后次序
int main() //主函数
{
char c,x,theta;
int a,b,c1; //定义变量
SqStack OPTR; //定义字符栈
sqStack OPNR; //定义整型栈
InitStack_char(&OPTR); //初始化
InitStack_int(&OPNR); //初始化
Push_char(&OPTR,'#'); //将字符型栈底设为#
c = getchar(); //从键盘输入得到字符
while(c!='='||GetTop_char(&OPTR)!='#') //判定是否执行循环
{
if(!In(c))
{
c1 = 0;
while(!In(c))
{
c1 = c1*10+c-'0';
c = getchar();
}
Push_int(&OPNR,c1);
} //当扫描字符不是运算符时，转化为整型数存入栈中
else
{
switch(Precede(GetTop_char(&OPTR),c)) //判定运算符的优先关系
{
case '<':
Push_char(&OPTR,c);c = getchar();break; //当前运算符优先级高，存入char栈
case '=':
Pop_char(&OPTR,c);c = getchar();break; //运算符次序相等，存入char栈
case '>': //当前运算符优先级低
Pop_char(&OPTR,theta);
Pop_int(&OPNR,b);
Pop_int(&OPNR,a);
Push_int(&OPNR, Operate(a,theta,b));//计算运算结果，并存入int栈
break; //继续循环
}
}
}
printf("%d\n",GetTop_int(&OPNR)); //计算完成，取出int栈顶元素，并输出
return 0;
}其中专业理论知识内容包括：保安理论知识、消防业务知识、职业道德、法律常识、保安礼仪、救护知识。作技能训练内容包括：岗位操作指引、勤务技能、消防技能、军事技能。
二．培训的及要求培训目的
安全生产目标责任书
为了进一步落实安全生产责任制，做到“责、权、利”相结合，根据我公司2015年度安全生产目标的内容，现与财务部签订如下安全生产目标：
一、目标值：
1、全年人身死亡事故为零，重伤事故为零，轻伤人数为零。
2、现金安全保管，不发生盗窃事故。
3、每月足额提取安全生产费用，保障安全生产投入资金的到位。
4、安全培训合格率为100%。
二、本单位安全工作上必须做到以下内容：
1、对本单位的安全生产负直接领导责任，必须模范遵守公司的各项安全管理制度，不发布与公司安全管理制度相抵触的指令，严格履行本人的安全职责，确保安全责任制在本单位全面落实，并全力支持安全工作。
2、保证公司各项安全管理制度和管理办法在本单位内全面实施，并自觉接受公司安全部门的监督和管理。
3、在确保安全的前提下组织生产，始终把安全工作放在首位，当“安全与交货期、质量”发生矛盾时，坚持安全第一的原则。
4、参加生产碰头会时，首先汇报本单位的安全生产情况和安全问题落实情况；在安排本单位生产任务时，必须安排安全工作内容，并写入记录。
5、在公司及政府的安全检查中杜绝各类违章现象。
6、组织本部门积极参加安全检查，做到有检查、有整改，记录全。
7、以身作则，不违章指挥、不违章操作。对发现的各类违章现象负有查禁的责任，同时要予以查处。
8、虚心接受员工提出的问题，杜绝不接受或盲目指挥；
9、发生事故，应立即报告主管领导，按照“四不放过”的原则召开事故分析会，提出整改措施和对责任者的处理意见，并填写事故登记表，严禁隐瞒不报或降低对责任者的处罚标准。
10、必须按规定对单位员工进行培训和新员工上岗教育；
11、严格执行公司安全生产十六项禁令，保证本单位所有人员不违章作业。
三、 安全奖惩：
1、对于全年实现安全目标的按照公司生产现场管理规定和工作说明书进行考核奖励；对于未实现安全目标的按照公司规定进行处罚。
2、每月接受主管领导指派人员对安全生产责任状的落