湖南大学数据结构试验2逆波兰问题.docVIP

HUNAN UNIVERSITY 课程实习报告 题 目： 逆波兰问题 学生姓名 刘乐 学生学号 20080820208 专业班级 通信工程2班 指导老师 朱宁波 完 成 日 期 2010年4月1日一、需求分析 本程序要求采用堆栈方法计算表达式的值，同时验证后缀报答是是否正确。 从键盘输入一个后缀表达式，该表示包括加减乘除等操作，以及正整数作为操作数等。 用堆栈来实现。 测试数据 二、概要设计 抽象数据类型 为实现上述程序的功能，应以字符存储用户的输入，以及计算出的结果。 算法的基本思想 根据题目要求，设计一个堆栈，对输入的字符串即后缀表达式中的数字字符逐个入栈，遇到运算符则出栈对栈顶元素和第二个元素进行运算，栈顶指向运算结果。其中除数不可以为0。直到表达式运算完输出结果。 定义如下线性表ADT Stack { 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ ai-1 ,ai |ai-1 ,ai∈D, i=2,...,n } 约定an端为栈顶，a1端为栈底 }ADT Stack 基本操作：InitStack (S) (构造空栈 ) DestroyStack(S)(销毁栈结构) ClearStack (S) (栈清空) StackLength(S) (求栈长) StackEmpty (S)(判空) GetTop (S, e) (求栈顶元素) Push (S, e) (入栈) Pop (S, e) (出栈) StackTraverse (S, visit( ))(遍历栈) 本程序包含三个基本模块 （1）模块：（2）模块： （3）模块：float comp() { int x; i = 0; top = -1; ch = exp[i]; while (ch != #) //以#判断表达式结束 { switch(ch) { case +: stack[top-1]=stack[top-1]+stack[top]; top--; break; case -: stack[top-1]=stack[top-1]-stack[top]; top--; break; case *: stack[top-1]=stack[top-1]*stack[top]; top--; break; case /: if(stack[top] == 0) { printf(除数错误!\n); exit(0);//switch语句判断输入为运算符时则运算栈顶元素和第二个元素，特别的对除数不等于0做出出错处理、。 } else { stack[top-1]=stack[top-1]/stack[top]; top--; break; } default: if (ch = 0 ch = 9) { x=0; while (ch!= ) { x=x*10+ ch - 0; i++; ch=exp[i]; } top++; stack[top]=x; }对0-9数字通过阿斯科码实现与字符的对应转化计算表达式结果。