实验五中缀表达式转化为后缀表达式算法(昆工版本).doc

昆明理工大学信息工程与自动化学院学生实验报告
( 2013 — 2014 学年第三学期)
课程名称:数据结构开课实验室:信自楼444 2013年11月12日
年级、专业、班
计科122班
学号
201210405204
姓名
邹华宇
成绩
实验项目名称
中缀表达式转化为后缀表达式算法及后缀表达式计算算法的实现
指导教师
胡守成
教师评语
教师签名:
年月日
注:报告内容按实验须知中七点要求进行。
一、实验目的和要求
结合堆栈入栈出栈的特点解决实际问题。输入一个含+、-、*、/、正整数和圆括号的合法的中缀表示的算术表达式,输出转化得到的后缀表达式,计算该表达式的运算结果。
调用直接计
算的函数
返回计算结果
后缀表达
式的计算
调用函数得到
后缀表达式
无错
调用容错函数
存在错误
报错并结束
得到用户输入
的中缀表达式
二、算法思想
三、所用仪器、材料(设备名称、型号、规格等)
联想计算机一台
Microsoft Visual c++
四、程序源代码
#include<> /*导入需要用到的各种包*/
#include<>
#include<>
typedef struct /*定义结构体用来存储操作符*/
{
char op; /*存储字符*/
int level; /*存储优先级*/
}OpNode;
typedef struct
{
OpNode op[100];
int top;
int size; /*表示栈内元素的个数*/
} stack; /*定义符号栈*/
void init(stack *st) /*初始化栈*/
{
st->size=0;
st->top=0;
}
OpNode pop(stack *a) /* 出栈*/
{
if (a->size==0) /*如果栈为空结束操作*/
{
exit(-1);
}
a->size--;
return a->op[--(a->top)]; /*取出栈顶元素*/
}
void push(stack *a,OpNode op) /*入栈函数*/
{
a->size++;
a->op[(a->top)++]=op;
}
OpNode top(stack *a) /*观察栈顶函数*/
{
if (a->size==0) /*如果栈为空结束操作*/
{
printf("stack is empty\n");
exit(-1);
}
return a->op[(a->top)-1]; /*只得到栈顶的值而不出栈*/
}
typedef struct /*定义数值栈*/
{
double num[100];
int top; /*栈顶指针*/
int size;
} numstack;
void init2(numstack *st) /*初始化数值栈*/
{
st->size=0;
st->top=0;
}
double pop2(numstack *a) /*数值栈出栈*/
{
if (a->size==0) /*出栈前的判空*/
{
exit(-1);
}
a->size--;
return a->num[--(a->top)]; /*得到栈顶的值*/
}
void push2(numstack *a,double num) /*入栈*/
{
a->size++;
a->num[(a->top)++]=num;
}
void main() /*主函数*/
{ char ch='y';
void change (char str[],char exp[]); /*声明要用到的各个函数*/
double CalResult(char exp[]); /*声明后缀表达式的计算函数*/
double Directcalresult(char str[]);
int check(char str[],char chestr[100]);
char str[100],exp[100],chestr[100]; /*str存储原算术表达式,exp存储对应的后缀表达式,chestr存储容错字符'^'*/
do{
printf("算术表达式为:\n");
gets(str);
if(check(str,chestr)) /*调用容错函数*/
{ printf("表达式错在:\n");
printf("%s