《数据结构与算法设计》
实验报告
——实验二
学院：自动化学院
班级：
学号：
：
一、实验目的
按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。
二、实验容
简单计算器。
请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。要求：
①从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。
②输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取
整。
例如，输入：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);