四则运算表达式求值栈+二叉树c++版文档格式.docx
《四则运算表达式求值栈+二叉树c++版文档格式.docx》由会员分享，可在线阅读，更多相关《四则运算表达式求值栈+二叉树c++版文档格式.docx（18页珍藏版）》请在冰点文库上搜索。
3、中缀表达式存入到二叉树的过程中，要注意处理的顺序，如‘+’、‘-’号的优先级比‘*’、‘/’号的低，当遇到‘*’、‘/’号时，要判断树以上的节点中是否有‘+’、‘-’号，有的话要与其交换位置。
遇到‘〔’时要反复创建二叉树的结点，构建子二叉树，考虑到括号要处理的步骤可能会较多，可以考虑用递归。
遇到‘〕’时那么直接完毕此子二叉树的建立。
此外二叉树中叶子结点存储操作数，非叶子结点存储操作码。
4、对创建好的二叉树进展后序遍历，即可得到相应的后缀表达式，实现方法可以用递归的方式，由于后面还要计算表达式的值，故便利的过程中要将结点中得到的数据存入新的字符数组中。
程序的流程
程序由三个模块组成：
（1）输入模块：
完成一个中缀表达式的输入，存入字符串数组array[Max]中。
（2）计算模块：
设计一个建立二叉树的函数，Node*crtTree（Node*root），传入根结点指针，返回根结点指针，该函数的实现还要反复使用另一个函数chargetOp（Node*temp），其将数字字符存入一个结点，并返回数字字符的后一个符号。
voiddeal（）函数功能是对字符数组进展处理。
voidoutput（Node*root）;
函数功能是获得处理后的字符串，也就是中缀表达式转化为的后缀表达式。
（3）输出模块：
如果该中缀表达式正确，那么在字符界面上输出其后缀表达式和表达式的值；
三、详细设计
物理数据类型
题目要求输入的四那么运算表达式运算符只有加减乘除，操作数有整数和小数，为了能够存储，采用C语言中的字符串数组。
charch[Max];
算法的时空分析
算法的运行时间主要消耗在二叉树的建立过程中。
可以发现，每当遇到一个运算符或操作数时，都要调用一次函数chargetOp（Node*temp），来将其存入二叉树的结点中，其中也会遇到递归的情况，但耗时可以忽略。
所以假设输入的字符串中字符个数为N，那么算法的时间复杂度为O（N）。
输入和输出的格式
输入
本程序可以将输入的四那么运算表达式〔中缀表达式〕转换为后缀表达式//提示
请输入四那么运算表达式：
//提示
等待输入
输出
//提示
后缀表达式为：
//输出结果的位置
表达式的值为：
四、调试分析
本次实验的难点主要是在建立二叉树的问题上。
关于如何把中缀表达式存入二叉树中，我参考了网上的一些方法，成功实现了目标，但是却遇到了一个问题，那就是不能处理小数，甚至两位或两位以上的整数。
因为如果采用字符数组来存储操作数，运算符合一位整数还可以处理，但对于两位数就就会出问题，最后我改良采用字符串数组来存储操作数，成功解决了问题。
另外在处理输入的非法表达式问题中，我也费了很大功夫，但总体问题不大。
五、测试结果
六、用户使用说明〔可选〕
1、本程序的运行环境为DOS操作系统
2、运行程序时
提示输入四那么运算表达式
本程序可以将中缀表达式转化为后缀表达式，并计算结果
后缀表达式为：
七、附录〔可选〕
程序源代码〔c++〕
1、利用二叉树后序遍历来实现表达式的转换：
#include<
iostream>
string>
stack>
iomanip>
constintMax=100;
usingnamespacestd;
classNode{
public:
charch[Max];
//考虑到数值有时会是两位数，所以使用字符串数组
Node*lChild;
Node*rChild;
Node（）{
strcpy（ch,"
"
）;
lChild=rChild=NULL;
}
~Node（）{
if（lChild!
=NULL）
deletelChild;
if（rChild!
deleterChild;
};
staticintcount=0;
staticchararray[Max];
//保存原始的中缀表达式
staticcharstr[2*Max];
//保存后序遍历出来的字符串，为表达式求值提供方便
staticintk=0;
chargetOp（Node*temp）;
//temp指针保存每个结点，返回的是运算符
Node*crtTree（Node*root）;
//传入根结点指针，返回根结点指针
//获得处理后的字符串
boolisError（char）;
//判断字符是否有问题
voiddeal（）;
//对字符数组进展处理
doublevalue（string）;
//计算后缀表达式，得到其结果。
intmain（）{
Node*root=NULL;
cout<
<
输入中缀表达式：
;
cin.getline（array,40）;
deal（）;
root=crtTree（root）;
输出后缀表达式：
output（root）;
str<
endl;
输出后缀表达式的值：
if（value（str）!
=0）
fixed<
setprecision
（2）<
value（str）<
else
AWrongInput!
return0;
}
//将数字字符存入一个结点，并返回数字字符的后一个符号
chargetOp（Node*temp）{
inti=0;
if（isError（array[count]））
exit（0）;
while（array[count]<
='
9'
&
array[count]>
0'
||array[count]=='
.'
）{
temp->
ch[i]=array[count];
i++;
count++;
}
ch[i]='
\0'
returnarray[count-1];
//传入根结点指针，返回根结点指针
Node*crtTree（Node*root）{
Node*p,*q;
charop;
if（root==NULL）{
root=newNode;
p=newNode;
op=getOp（root）;
while（op!
q=newNode;
q->
ch[0]=op;
ch[1]='
switch（op）
{
case'
+'
:
-'
lChild=root;
root=q;
op=getOp（p）;
root->
rChild=p;
break;
*'
/'
if（root->
ch[0]=='
||root->
strcpy（p->
ch,root->
ch）;
p->
rChild=q;
root=p;
}else{
}break;
（'
p=root;
while（p->
rChild）
p=p->
rChild;
if（p->
lChild==NULL）{
lChild=crtTree（p->
lChild）;
//递归创建括号里的指针
op=array[count];
}else{
rChild=crtTree（p->
rChild）;
）'
returnroot;
//传入根结点，后序遍历,赋值给另一个字符数组〔主要是为了给后序的计算表达式值提供方便〕
voidoutput（Node*root）{
intn;
if（root）{
output（root->
n=0;
while（root->
ch[n]!
）
str[k++]=root->
ch[n++];
str[k++]='
'
boolisError（charch）{//判断每个字符是否有错
if（ch!
ch!
!
（ch<
ch>
）&
）{
cout<
"
字符错误！
returntrue;
returnfalse;
voiddeal（）{//对字符数组进展处理
inti=0,n=0;
while（array[i]）{
if（array[i]=='
||array[i]=='
array[n++]=array[i++];
array[n++]='
array[n]='
doublevalue（strings2）{//计算后缀表达式，得到其结果。
stack<
double>
s;
doublex,y;
inti=0;
while（i<
s2.length（））{
if（s2[i]=='
switch（s2[i]）
if（s.size（）>
=2）{
x=s.top（）;
s.pop（）;
x+=s.top（）;
x=s.top（）-x;
x*=s.top（）;
if（s.top（）==0）return0;
else{
x=s.top（）/x;
default:
x=0;
while（'
<
=s2[i]&
s2[i]<
='
x=x*10+s2[i]-'
doublek=10.0;
y=0;
y+=（（s2[i]-'
）/k）;
k*=10;
x+=y;
if（x!
s.push（x）;
if（s.size（）==1）
returns.top（）;
2、利用堆栈来实现中缀表达式转换为后缀表达式。
#include<
intcmp（charch）{//运算符优先级
switch（ch）
return1;
return2;
voidchange（string&
s1,string&
s2）{//中缀表达式转变后缀表达式
char>
s.push（'
#'
s1.length（））{//分成四个级别来检验中缀表达式//s1.length（）是为了s1的长度，不包括\0
if（s1[i]=='
）//级别一
s.push（s1[i++]）;
elseif（s1[i]=='
）{//级别二
while（s.top（）!
）{
s2+=s.top（）;
s2+='
}elseif（s1[i]=='
||s1[i]=='
）{//级别三
while（cmp（s.top（））>
=cmp（s1[i]））{
s.push（s1[i]）;
else{//级别四
=s1[i]&
s1[i]<
s2+=s1[i++];
while（s.top（）!
）{//最后一步
doublevalue（string&
s2）{//计算后缀表达式，得到其结果。
double>
s2.length（）-1）{//由于s2的最后一位是空格，影响判断，所以用s2.length（）-1
switch（s2[i]）
=2）{x=s.top（）;
elsereturn0;
=2）{x=s.top（）;
strings1,s2;
输入〔中缀表达式〕：
cin>
>
s1;
s2="
change（s1,s2）;
if（value（s2））{
输出1〔后缀表达式〕：
s2<
输出2〔表达式的值〕：
value（s2）<
Awronginput!
升级会员 