四则运算c 实现.doc

- 1- 一、需求分析 1. 利用二叉树后序遍历来实现表达式的转换, 同时可以使用实验 3 的结果来求解后缀表达式的值。 2. 输入输出格式: 输入:在字符界面上输入一个中缀表达式,回车表示结束。输出: 如果该中缀表达式正确, 那么在字符界面上输出其后缀表达式, 其中后缀表达式中两相邻操作数之间利用空格隔开;如果不正确,在字符界面上输出表达式错误提示。二、概要设计抽象数据类型为实现上述程序的功能, 前序遍历输入, 以后序遍历输出。算法的基本思想用一个字符串储存输入的二项式, 一次读取各个字符。如果遇见数据, 累乘后存入后序遍历的数组当中(将字符型转换为整数类型) ;如果遇见前括号,存入运算符栈中;如果遇见后括号, 将前括号及前括号之后的运算符全部弹出; 如果遇见加减号, 在运算符栈为空或下一个为括号运算符时, 运算符入栈, 否则, 将栈顶元素存入后序遍历的数组中, 再运算符入栈; 如果遇见乘除号, 在运算符栈为空或下一个为括号运算符时及栈内第一个元素为乘号或除号时,运算符入栈,否则,将栈顶元素存入后序遍历的数组中,再运算符入栈。程序的流程程序由三个模块组成: (1) 输入模块: 输入正确的四则运算表达式。(2) 计算模块:利用栈实现四则运算。(3) 输出模块:屏幕上显示后序遍历的结果。三、详细设计物理数据类型 1、用数组存储输入的表达式和输出的表达式。 2、用栈存储操作算法的具体步骤求逆序遍历的算法- 2- postexp[j]=data[top_p]; j++; top_p--; postexp[j]='\0'; cout<<postexp<<endl; 结束 postexp[j]=ch; j++; ch=exp[i]; i++; i--; postexp[j]='#';j++; top_p!=-1 switch postexp[j]=data[top_p]; j++; top_p--; top_p--; break; postexp[j]=data[top_p]; j++; top_p--; ttop_p++; data[top_p]=ch; break; postexp[j]=data[top_p]; j++; top_p--; ttop_p++; data[top_p]=ch; break; ch>='0'&&ch<='9' top_p++; data[top_p]=ch; break; data[top_p] !='(' (top_p!=-1)&&(data[top_p]!='(')& &(data[top_p]=='*'||data[top_p]=='/ ') (top_p!=-1)&&(dat a[top_p]!='(') 遇“!”开始输入中序表达式如: 输入: 5*(3+2)! - 3- 算法的时空分析后序遍历的时间代价为Θ(n) 空间代价为一个数组. 输入和输出的格式输入: 请输入中序表达式: xxx#(# 结束符) 输出: 输出的后缀是: 五、测试结果输入: 5*(3+2)! 输出: 5#3#2#+* The result is:25 六、用户使用说明(可选) 1、“!”结束符 2 、输入的包括符号请不要超过十位七、实验心得(可选) 1: 这次试验的优点是在不断地调试和运行之后终于实现了这个代码, 完成了 c++ 创建栈的全部过程