后缀表达式求值

1 / 9 数据结构实验报告 学号：2015111898 姓名：许明华 专业：计算机科学与技术 知识范畴：栈与队列 完成日期：2017 年 4 月 03 日 实验题目：后缀表达式求值 实验内容及要求： 从键盘输入后缀表达式（运算符和操作数建议以字符串形式输入，空格作为分隔符） ，计 算并输出后缀表达式的求值结果。 基本要求：实现 +, -, *, /四个二元运算符； 实现+, -两个一元运算符（即正、负号） ； 操作数用整数表示。 提高要求：输出对应的前缀表达式。 每位同学可必须实现基本要求，可选择实现提高要求；程序可不处理表达式语法错误。 实验目的：掌握堆栈在表达式求值中的应用。 数据结构设计简要描述： 序言： 这是本学期第三个实验，这个实验比较的基本要求是要我们求出一个已经按后缀表达式 形式输入的值，除了之前的堆栈部分，新增了一部分就是判断操作数和运算符，并将操作数 入栈，将运算符进行对应的操作数功能实现，并将结果入栈。 数据结构简要设计： 本实验主要可分为两个大的模块，一个是堆栈操作，另外一个就是后缀表达式求值操作。 堆栈操作：用结构体类型名来创建用于保存操作数的堆栈，并实现判断栈空、栈满、栈初始 化、入栈以及退栈等操作；后缀表达式求值操作：用 string 类型定义一个字符串，并对其进 行判断，是操作数就入栈，是运算符就进行运算，并保存结果。 算法设计简要描述： 后缀表达式求值算法：用 string 类型定义一个字符串，并用一个 switch 来实现运算符 评分 满分5 分 2 / 9 的操作和操作数的入栈，再用一个 while 来进行循环遍历整个字符串，直到字符串的末尾为 止。最后将算得最终结果退栈，并打印到屏幕上即可。 输入/输出设计简要描述： 输入：从键盘上输入一个已经排好序的后缀表达式，如 12-82-74-/* 输出：屏幕上将输出后缀表达式的值，如上面表达式的值为 6 编程语言说明： 1，编程软件，Code Blocks 16.0； 2，代码均用 C+语言实现； 3，输入输出采用 C+语言的 cout 和 cin 函数； 4，程序注释采用 C/C+规范； 主要函数说明： void InitStack(Stack *s);/栈的初始化 int EmptyStack(Stack *s);/判断栈空 int full(Stack *s);/判断栈满 int push(Stack *s,elemtype x);/入栈操作 int pop(Stack *s,elemtype /退栈操作 int result(string s);/后缀表达式求值 程序测试简要报告： 见截图： 1， 3 / 9 2， 源程序代码： #include #include using namespace std; typedef int elemtype;/整数型数据类型 typedef struct elemtype *elem; int length; int top; Stack; 4 / 9 /函数声明 void InitStack(Stack *s);/栈的初始化 int EmptyStack(Stack *s);/判断栈空 int full(Stack *s);/判断栈满 int push(Stack *s,elemtype x);/入栈操作 int pop(Stack *s,elemtype /退栈操作 int result(string s);/后缀表达式求值 /函数具体实现 /顺序存储的栈结构，以及其相应算法 void InitStack(Stack *s) s-length = 100; s-elem = (elemtype *)malloc(sizeof(elemtype)*s-length); s-top = -1; /判断栈是否为空 int EmptyStack(Stack *s) return s-top = -1; /判断栈满 5 / 9 int full(Stack *s) return s-top=s-length-1; /入栈 int push(Stack *s,elemtype x) if(full(s) return 0; s-elem+s-top = x; return 1; /退栈 int pop(Stack *s,elemtype x = s-elems-top-; 6 / 9 return 1; /后缀表达式求值函数 int result(string s) int Result;/定义一个保存输出结果的值 Stack *p;/建栈 p = (Stack *)malloc(sizeof(Stack);/为新建的栈分配内存空间 InitStack(p);/初始化刚建的栈，这一步不进行的话，入栈将不能进行，之前这个问题 将我难到了好久 int i = 0;/定义一个字符串下标，用来循环判断字符串中的内容 elemtype a,b,d;/定义三个 elemtype 类型变量，用来进行操作数的实现 while(1) if(is.length()-1) break; 7 / 9 switch(si) case +:/加号则退两个，并相加将结果保存在栈中 pop(p,a); pop(p,b); d = a + b; push(p,d); break; case -:/加号则退两个，并相减将结果保存在栈中 pop(p,a); pop(p,b); d = b - a; push(p,d); break; case *:/加号则退两个，并相乘将结果保存在栈中 pop(p,a); 8 / 9 pop(p,b); d = a*b; push(p,d); break; case /:/加号则退两个，并相除结果保存在栈中 pop(p,a); pop(p,b); d = b/a; push(p,d); break; default:/是数字就转