杂度。
在转换的函数中,有个 while循环,这里的复杂度是 n,而在这个循环里,还存在 while循环,故其时间复杂度是 n 的平方。
在计算函数中,其复杂度也是 n 的平方。
故可知本程序的时间复杂度是 n平方。
经验和体会:这个程序我一直是很简单的,因为我很久之前就在一直考虑这个问题,但是没有去实现过,以为很简单,可是当真正写起来的时候,发现有点困难。
开始的时候用书山的那种方法,可是发现那种方法不适合我,不是有多难,就是我的大脑反应不过来。
后来想到用后缀表达式,这样处理起来就方便多了,思路也清晰了很多。
在不断的错误中改错,在调试中发现程序中的逻辑错误并改正错误。
终于这个程序完成了,心中不免有中自豪感。
五:用户使用说明 本程序用vc++6.0编的,在DOS界面下运行的。
运行时,程序有个欢迎的界面,并提示输入表达式,在输入时要注意的是,本程序能处理的数据长度最长为6位。
另外,输入0时,结束本程序;如输入的表达式有错误的符号时,程序提示输入错误;当输入正确时,按回车键,即可得到计算结果。
六:测试结果 经过人工计算,可知以上结果是正确的。
参考文献: 1 王昆仑,李红. 数据结构与算法. 北京:中国铁道出版社,2006 年 5 月。
2 郑莉 ,董渊,张瑞丰 c语言程序设计 北京:清华大学出版社,2004七:附录(源程序代码)include quotiostreamquotinclude quotmath.hquotinclude quotstringquotinclude quotstdlib.hquotinclude quotwindows.hquotdefine derror 1234567define Maxlen 400using namespace stdstruct char dataMaxlen int top optr //定义运算符栈,并定义全局变量struct double dataMaxlen int top opnd //定义操作数栈,并定义全局变量void main char p400q400 double kvoid meun //声明菜单函数int changechar p char q //声明转换函数double jisuanchar q //声明计算函数meunfor //循环执行 cout ltltquot请输入:quot cingtgtp if strcmppquot0quot0 return if changepq1 kjisuanq ifkderror coutltltquotquot else coutltltquot计算结果为:quotltltkltltendl systemquotpausequot //控制输出格式systemquotclsquotmeunvoid meunsystemquotcolor 0aquot coutltltquottt quotltltendl coutltltquot 欢迎使用本计算器quotltltendl coutltltquottt quotltltendlcoutltltendlcoutltltquot按 0 结束本程序quotltltendlint changechar p char q //将算术表达式 p 转换成表达式后缀表达式 q int i0 //i 作为 q 的下标 int dh1 //dh1 表示是负号 optr.top-1 //初始化运算符栈 while p0 //p 表达式未扫描完时循环 switchp //判断各种情况并做相应的处理 case : optr.topoptr.dataoptr.topp dh1pbreak case : while optr.dataoptr.top qioptr.dataoptr.top optr.top-- i optr.top-- p dh0 break case : case -: if dh1 // -是正负号 if p- optr.topoptr.dataoptr.top p break while optr.top-1 ampamp optr.dataoptr.top qioptr.dataoptr.top optr.top-- i optr.topoptr.dataoptr.topp p dh0 break case : case /: while optr.dataoptr.top optr.dataoptr.top/ optr.dataoptr.tops qioptr.dataoptr.top optr.top-- i optr.topoptr.dataoptr.topp p dh0 break case : while optr.dataoptr.top qioptr.dataoptr.top optr.top--i optr.topoptr.dataoptr.topppdh0break case : while optr.dataoptr.top qioptr.dataoptr.top optr.top--i optr.topoptr.dataoptr.topppdh0break case : p break //消除空格 case s: case S: ifp1i p1Iampampp2n p2N optr.topoptr.dataoptr.tops p3 dh0 break elseifp1qp1Qampampp2r p2Rampampp3t p3T optr.topoptr.dataoptr.topq p4dh0 break else coutltltendlltltquot有错误符号quotltltendl return derror case c: case C: ifp1o p1Oampampp2s p2S optr.topoptr.dataoptr.topc p3 dh0 break else coutltltendlltltquot有错误符号quotltltendl return derror case T: case t:ifp1a p1Aampampp2n p2N optr.topoptr.dataoptr.topt p3dh0 break else coutltltendlltltquot有错误符号quotltltendl return derror case e: case E:ifp1x p1Xampampp2p p2P optr.topoptr.dataoptr.tope p3dh0 break else coutltltendlltltquot有错误符号quotltltendl return derror case a: case A: ifp1b p1Bampampp2s p2S optr.topoptr.dataoptr.topa p3dh0 break else coutltltendlltltquot有错误符号quotltltendl return derror default: while pgt0 ampamp plt9 //判断是否为数字 qipi p if p. qi. i p while pgt0 ampamp plt9 qipi p qi i dh0//用标识一个数值串结束 while optr.top-1 //此时 p 扫描完毕栈不空时循环 qioptr.dataoptr.top i optr.top-- qi0 //给 q 表达式添加结束标识 return 1double jisuanchar q //计算后缀表达式的值 double dx opnd.top-1 //初始化操作数栈 while q0 //q 字符串未扫描完时循环 switch q //判断各种情况,并做相应的运算并入栈 case :opnd.dataopnd.top-1opnd.dataopnd.top-1opnd.dataopnd.top opnd.top--break case -:opnd.dataopnd.top-1opnd.dataopnd.top-1-opnd.dataopnd.top opnd.top--break case :opnd.dataopnd.top-1opnd.dataopnd.top-1opnd.dataopnd.top opnd.top--break case /: if opnd.dataopnd.top0 opnd.dataopnd.top-1opnd.dataopnd.top-1/opnd.dataopnd.top else coutltltendlltltquot除数不能为零quotltltendl return derror opnd.top--break case :opnd.dataopnd.top-1powopnd.dataopnd.top-1opnd.dataopnd.top opnd.top--break case :opnd.dataopnd.top-1fmodopnd.dataopnd.top-1opnd.dataopnd.top opnd.top--break case :opnd.dataopnd.top-opnd.dataopnd.topbreak case s:opnd.dataopnd.topsinopnd.dataopnd.topbreak case c:opnd.dataopnd.topcosopnd.dataopnd.topbreak case q:ifopnd.dataopnd.topgt0 opnd.dataopnd.topsqrtopnd.dataopnd.top else coutltltendlltltquot开方内的数不能小于零quotltltendl return derror .
上一篇:
【精品】野火stm32
下一篇:
临床前药物安全性评价中毒性病理学新技术的应用