文档介绍：中缀表达式改后缀表达式
一、需求分析
;
;
３．输入输出格式:
输入:在字符界面上输入一个中缀表达式,回车表示结束。
输出:如果该中缀表达式正确,那么在字符界面上输出其后缀表达式,其中后缀表达式中两相邻操作数之间利用空格隔开;如果不正确,在字符界面上输出表达式错误提示。
二、概要设计
ﻩ抽象数据类型
用Noｄｅ类来定义一个结点:
class Nｏｄe
{
puｂｌic:
ﻩcｈａr　ch[mａx]; 　／／每个结点的字符串
ﻩNｏdｅ* ｌＣhilｄ; ／／左指针
ﻩNｏｄe* ｒＣhｉld; /／右指针
ﻩNｏde();
ﻩ～Ｎｏde（）;
};
算法的基本思想
输入中缀表达式,用函数对字符串中的空格或者等号进行处理,由于程序需要,会在输入的字符串结尾加入‘=’;
用函数一次扫描每一个字符,有异常字符,报错;没有,则每次取出连续的数字字符或加减乘除的符号,放入结点,并按规则,将上一结点的左或右指针指向该结点;
退出
将该树用后序遍历法,输出每个结点的值;
程序的流程
输入四则中缀表达式
逐一扫描,判断是否有错
处理表达式
逐一
产生结点,相关结点的左或右指针指向该结点
输出
算法的具体步骤
处理:将表达式中的空格和多余的等号删掉,在表达式的最后加上等号;
扫描:①扫描过程在树的建立过程中;②每次扫描,获得数字字符作为一个结点,并返回数字字符后的算数运算符或者括号;③根据返回的运算符或括号,确定相应的指针赋值或是新建结点;(有错时,会退出程序)
后序遍历法输出获得结果。
算法的时空分析
因为在处理字符串时,需要逐一扫描,也建立了新的字符数组,所以时间复杂度为Θ（ｎ);同样,扫描的循环,也与字符串的长度有关,时间复杂度也为Θ(n）
输入和输出的格式
ﻩ输入:＋5*（２*（4＋5）＋7)
输出:3．4 ５　 2 4 　5 ＋　＊　 7 + 　* +
五、测试结果
ﻩ
六、实验总结
ﻩ这个程序好难,自己很难想到这方法。不过,没想法时,看不懂别人的程序时,可以通过调试的方法,去获取程序的主要思想,从而变为自己的想法,去实现他。代码嘛,主要是多写,多仿,写代码的能力自然而然就提高了。
七、附录(可选)
#ｉnｃｌｕｄe<iostream>
#inｃlｕｄe<string＞
ｕsiｎg nａmeｓpacｅｓtｄ;
coｎst ｉnt　max=１00;
cｌaｓs Ｎoｄe
{
ｐｕbｌic:
ﻩｃｈar ch[ｍaｘ];
ﻩNode* lCｈild;
ﻩNodｅ* rChiｌｄ;
ﻩNｏde(）;
ﻩ～Noｄe();
};
Node::Ｎｏde（)
{
ﻩstrｃpy(ch,＂");
ﻩlChｉｌｄ=ｒＣｈｉｌd=ＮULL;
｝
Node::~Nｏde(）
｛
ﻩif(lＣhｉｌd!＝ＮＵＬＬ)
ﻩ deleｔe　lChild;
ﻩif(rCｈild!=NULＬ)
ﻩﻩdｅlete　rChild;
}
ｓｔａｔic ｉnt counｔ