四则运算表达式求值栈+二叉树c++版文档格式.docx
- 文档编号:2965755
- 上传时间:2023-05-01
- 格式:DOCX
- 页数:18
- 大小:35.48KB
四则运算表达式求值栈+二叉树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!
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 四则运算 表达式 求值 二叉 c+