逆波兰表达式求值实报告湖大.docVIP

HUNAN UNIVERSITY 课程实习报告 题 目： 逆波兰表达式求值 学生姓名 范舜奕 学生学号 20100820608 专业班级 通信6班 指导老师 吴帆 完 成 日 期 2012.04. 07 实验二 逆波兰表达式求值 ★问题描述 选一个后缀表达式，利用堆栈来计算该表达式的值，同时要效验后缀表达式是否正确 基本要求 （1）从键盘中输入一个后缀表达式，该表达式包括加减乘除的操作符，一级正整数作为操作数等 （2）用堆栈来表示 ★输入输出格式 输入：在字符界面上输入一个后缀表达式，其中两相邻操作数之间利用空格隔开。以“#”表示结束。 输出：如果该后缀表达式正确，那么在字符界面上输出其结果，计算结果小数点后面保留两位有效数字。如果不正确，请在字符界面上输出表达式错误提示 测试用例 输入：2 3 * 1 -# 输出：5 设计思路 ◆为了测试需要，应以浮点数存储输入和输出，利用堆栈来实现算法。栈的抽象数据类型的定义如下： ADT Stack? { ?? 数据对象：D={a | a i ∈ElemSet, i=1,2,...,n, n≥0 } ?? 数据关系：R={a , a i | a i-1?,a i∈D, i=2,...,n} ?? 基本操作： (S) ????操作结果：} ADT LinkLiSt ◆本程序包含三个基本模块 （1）主程序模块： （2）线性表模块：实现的抽象数据类型 （3）元素结构单元模块：定义每个元素的结构 通过switch_case结构判断输入运算符的种类，转而执行不同的处理代码。#include stdio.h #include string.h #include malloc.h #include stdlib.h #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OK 1 #define TRUE 1 #define FALSE 0 #define ERROR 0 #define OVERFLOW -2 typedef float SElemtype; typedef int Status; typedef struct { SElemtype * base; SElemtype * top; int stacksize; } SqStack; Status InitStack(SqStack S) { S.base = (SElemtype *)malloc(STACK_INIT_SIZE*sizeof(SElemtype)); if (! S.base) exit(OVERFLOW); S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; } int StackLength(SqStack S) { return S.top - S.base; } Status Push(SqStack S, SElemtype e) { *S.top++ = e; return OK; } Status Pop(SqStack S, SElemtype e) { if (S.top == S.base) return ERROR; e = * -- S.top; return OK; } Status IsDigital(char ch) { if(ch=0ch=9) { return 1; //是数字字母 } return 0; //不是数字字母 } int EvalValue(char *ch, SqStack S) { int i=0; SElemtype result=0; char a; a=ch[i]; while(IsDigital(a)) { result=10*result+(int)(a-48); a=ch[++i]; } Push(S, result); return i; } void EvalExpr(char ch, SqStack S) { SElemtype oper1,oper2; i