后缀表达式求值

1、数据结构实验报告评分满分5分学号： 姓名：许明华 专业：计算机科学与技术知识范畴：栈与队列 完成日期：2017年4月03日实验题目：后缀表达式求值实验内容及要求：从键盘输入后缀表达式（运算符和操作数建议以字符串形式输入，空格作为分隔符），计算并输出后缀表达式的求值结果。 基本要求：实现 +, -, *, /四个二元运算符； 实现+, -两个一元运算符（即正、负号）； 操作数用整数表示。提高要求：输出对应的前缀表达式。每位同学可必须实现基本要求，可选择实现提高要求；程序可不处理表达式语法错误。实验目的：掌握堆栈在表达式求值中的应用。数据结构设计简要描述：序言：这是本学期第三个实验，这个实验比较的

2、基本要求是要我们求出一个已经按后缀表达式形式输入的值，除了之前的堆栈部分，新增了一部分就是判断操作数和运算符，并将操作数入栈，将运算符进行对应的操作数功能实现，并将结果入栈。数据结构简要设计： 本实验主要可分为两个大的模块，一个是堆栈操作，另外一个就是后缀表达式求值操作。堆栈操作：用结构体类型名来创建用于保存操作数的堆栈，并实现判断栈空、栈满、栈初始化、入栈以及退栈等操作；后缀表达式求值操作：用string类型定义一个字符串，并对其进行判断，是操作数就入栈，是运算符就进行运算，并保存结果。算法设计简要描述：后缀表达式求值算法：用string类型定义一个字符串，并用一个switch来实现运算符的

3、操作和操作数的入栈，再用一个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 fu

4、ll(Stack *s);/判断栈满int push(Stack *s,elemtype x);/入栈操作int pop(Stack *s,elemtype &x);/退栈操作int result(string s);/后缀表达式求值程序测试简要报告：见截图：1， 2， 源程序代码：#include#includeusing namespace std;typedef int elemtype;/整数型数据类型typedef struct elemtype *elem; int length; int top; Stack;/函数声明void InitStack(Stack *s);/栈的初始

5、化int EmptyStack(Stack *s);/判断栈空int full(Stack *s);/判断栈满int push(Stack *s,elemtype x);/入栈操作int pop(Stack *s,elemtype &x);/退栈操作int result(string s);/后缀表达式求值/函数具体实现/顺序存储的栈结构，以及其相应算法void InitStack(Stack *s) s-length = 100; s-elem = (elemtype *)malloc(sizeof(elemtype)*s-length); s-top = -1;/判断栈是否为空int Em

6、ptyStack(Stack *s) return s-top = -1;/判断栈满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) if(EmptyStack(s) return 0; x = s-elems-top-; return 1;/后缀表达式求值函数int result(string s) int Result;/定义一个

7、保存输出结果的值 Stack *p;/建栈 p = (Stack *)malloc(sizeof(Stack);/为新建的栈分配内存空间 InitStack(p);/初始化刚建的栈，这一步不进行的话，入栈将不能进行，之前这个问题将我难到了好久 int i = 0;/定义一个字符串下标，用来循环判断字符串中的内容 elemtype a,b,d;/定义三个elemtype类型变量，用来进行操作数的实现 while(1) if(is.length()-1) break; switch(si) case +:/加号则退两个，并相加将结果保存在栈中 pop(p,a); pop(p,b); d = a +

8、 b; push(p,d); break; case -:/加号则退两个，并相减将结果保存在栈中 pop(p,a); pop(p,b); d = b - a; push(p,d); break; 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; default:/是数字就转换为数字后入栈 d = si - 0; push(p,d); break; i+;/字符串自增一进