表达式树的建立的问题
表达式树中建立的树的子树出现了问题 假设设 #a*b-c#这个表达式 以 # 结尾在程序中的两个cout<<"-------------------------------error------------------------------------"<< endl;之间的部分 所输出的部分不对，
求各位大神 能予以讲解下 最好是指出程序中哪个地方出错了，改过来，谢谢了。。。。
#include<iostream>
using namespace std;
//假设 只有二元运算符
//定义二叉树的存储结构
typedef struct node_Tree
{
char data;
node_Tree *lchild;//左孩子域
node_Tree *rchild;//右孩子域
}*pnode, node_Tree;
//创建 一个只有根结点的二叉树
int Creat_Tree(pnode &t,pnode tree1, pnode tree2, char ch)
{// t--根结点 ch--根结点的数据域的值
t = new node_Tree;
if(t == NULL)
{
cout<< "分配内存失败 返回 -1"<< endl;
return -1;
}
t->data = ch;
t->lchild = tree1;
t->rchild = tree2;
return 0;
}
//链栈的存储结构============开始======================
typedef struct noptr_stack//运算符栈结构
{
char data; //数据域
noptr_stack *next;//指针域
}node;
typedef struct ntree_stack
{
node_Tree data; //数据域
ntree_stack *next;//指针域
}node1;
//链栈的存储结构============结束======================
//栈的初始化--------------------------------------
noptr_stack *InitStack_OPTR(noptr_stack *str_optr)//运算符栈的初始化
{
str_optr = NULL;
return str_optr;
}
ntree_stack *InitStack_EXPT(ntree_stack *t)//操作数栈的初始化 (数据类型为 二叉树)
{
t = NULL;//将 t置为空
return t;//返回 t
}
//栈的初始化--------------------------------------
//获得 OPTR栈的 栈顶元素 （注意：不出栈）
char GetTop_OPTR(noptr_stack *str_optr)
{
return str_optr->data;//返回栈顶指针的数据域的值
}
//入栈1 (运算符栈)
noptr_stack *Push_noptr_stack(noptr_stack *str_optr, char ch)
{
//申请新的内存空间
noptr_stack *strNew = new noptr_stack;//
if(strNew == NULL)
{
cout<<"分配空间失败 返回 NULL"<< endl;
return NULL;
}
//将 要入栈的值 ch赋值 新的空间的数据域 并将新空间置为栈顶
strNew->data = ch;
strNew->next = str_optr;//将新空间 链在 栈顶
str_optr = strNew;//栈顶指针 向上移动一位 始终指向 栈的栈顶元素
return str_optr;//返回栈顶指针
}
//出栈1（运算符栈）
//通过返回 栈顶指针来实现 出栈后 对栈顶变动的保存
noptr_stack *Pop_noptr_stack(noptr_stack *str_optr, char &ch_out)
{
if(str_optr == NULL)
{
cout<<"OPTR运算符栈为空 无法出栈 返回 NULL"<< endl;
return NULL;
}
ch_out = str_optr->data; //传出栈顶 数据域的值
noptr_stack *tmp = str_optr;//临时变量 记录栈顶指针
str_optr = str_optr->next; //栈顶指针向下移动一位
delete tmp; //释放原来栈顶空间
return str_optr;//返回出栈后的栈顶空间
}
//返回栈顶元素2（不改变栈的任何信息） 输入栈的指针
node_Tree GetTop_EXPT(ntree_stack *t)//返回 node_Tree 类型
{
return t->data;
}
//入栈2（操作数入栈）将二叉树结点 入栈
ntree_stack *Push_ntree_stack(ntree_stack *t, node_Tree tnode)
{//将二叉树根结点 tnode 入栈
//申请新的空间
ntree_stack *nNew = new ntree_stack;
if(nNew == NULL)
{
cout<<"二叉树栈空间申请失败 返回 NULL"<< endl;
return NULL;
}
//为新空间赋值
nNew->data = tnode;//将 新的二叉树作为数据域的值 赋给新的栈结点的数据域
nNew->next = t;//将新结点链在 栈的顶部
t = nNew; //t始终指向栈的顶部
return t; //返回 栈顶指针
}
//出栈2（操作数）通过返回出栈后的栈顶指针 来实现对 栈顶变动的保存
ntree_stack *Pop_ntree_stack(ntree_stack *t, node_Tree &tnode)
{
if(t == NULL)
{
cout<<"操作数栈为空 无法再出栈 返回 NULL"<< endl;
return NULL;
}
tnode = t->data;//传出 栈顶的数据
//将栈顶指针向下移动一位 并释放原来的栈顶空间
ntree_stack *tmp = t;
t = t->next;//
delete tmp;
return t;//返回 出栈后的栈顶空间
}
//判断 ch是否是 运算符 如果不是运算符 返回 1
int In(char ch)
{
if(ch == '+' ||
ch == '-' ||
ch == '*' ||
ch == '/' ||
ch == '(' ||
ch == ')' ||
ch == '#')
return 0;//如果是运算符 则返回 0
return 1;//如果不是运算符 返回 1
}
//比较OPTR栈的栈顶元素与 ch 的优先级
int Preced(char s_optr_top, char ch)
{
cout<<"ch = "<< ch<< endl;
cout<<"s_optr_top = "<< s_optr_top<< endl;
int i_ch = 0;
int i_s_optr_top = 0;
switch (ch) //记录ch 字符的优先级 级别
{
case ')': //---优先级最高---
i_ch = 1;
break;
case '*':
i_ch = 2;
break;
case '/':
i_ch = 2;
break;
case '+':
i_ch = 3;
break;
case '-':
cout<<"ch == '-'"<< endl;
i_ch = 3;
break;
case '(':
i_ch = 4;
break;
case '#':
i_ch = 5; //---优先级最低---
break;
default:
break;
}
switch (s_optr_top)//记录 OPTR栈顶元素的优先级 级别
{
case ')': //---优先级最高---
i_s_optr_top = 1;
break;
case '*':
i_s_optr_top = 2;
break;
case '/':
i_s_optr_top = 2;
break;
case '+':
i_s_optr_top = 3;
break;
case '-':
i_s_optr_top = 3;
break;
case '(':
i_s_optr_top = 4;
break;
case '#': //---优先级最低---
cout<<"栈顶元素为 '#'"<< endl;
i_s_optr_top = 5;
break;
default:
break;
}
//比较 二者的优先级
if(i_s_optr_top == 4 && i_ch == 1)
return 2;
if(i_s_optr_top > i_ch) //OPTR栈顶元素的优先级 小于 ch的优先级
{
cout<<"OPTR栈顶元素的 优先级 小于 ch 的优先级 返回 0"<< endl;
return 0;
}
else
{
cout<<"栈顶元素的优先级 大于ch 的优先级返回 1"<< endl;
return 1;
}
}
int InitExpTree()
{//表达式树的创建方法
//定义变量 代表栈
noptr_stack *str_optr = NULL;//定义栈的变量
ntree_stack *t = NULL; //定义栈的变量
//初始化两个栈 用来存储 表达式中的 运算符 和 操作数
str_optr = InitStack_OPTR(str_optr);//运算符栈的初始化
t = InitStack_EXPT(t); //操作数栈的初始化
//将表达式起始符 ‘#’压入栈中
str_optr = Push_noptr_stack(str_optr, '#');
char ch;
cout<<"请输入第一个字符"<< endl;
cin>>ch;//从键盘上输入第一个字符
while (ch!='#' || GetTop_OPTR(str_optr)!='#')//表达式没有扫描完毕或 OPTR栈顶元素不为 '#'
{
if(In(ch) == 1) //ch不是运算符
{
cout<<"-----输入的 ch 不是运算符------"<< endl;
pnode pnew = NULL;
Creat_Tree(pnew, NULL, NULL, ch);//以 ch为根创建一棵只有根结点的二叉树
t = Push_ntree_stack(t, *pnew);//将二叉树根结点 pnew进入EXPT栈
cout<<"读入下一个字符"<< endl;
cin>> ch;//读入下一个字符
}
else//ch 是运算符
{
cout<<"-----输入的 ch 是运算符----===="<< endl;
char ch_out = NULL;
pnode tnew = NULL; //创建一个新的二叉树
char ch_zuokuohao;
node_Tree t1;
node_Tree t2;
switch (Preced(GetTop_OPTR(str_optr), ch)) //比较 OPTR栈定元素和 ch的优先级
{
case 0:
cout<< "栈顶元素的运算符优先级较小 运算符入栈"<< endl;
str_optr = Push_noptr_stack(str_optr, ch);//运算符入栈
cout<<"运算符入栈后 OPTR栈顶元素为："<< str_optr->data<< endl;
cout<<"请输入 ch: ";
cin>> ch;
break;
case 1:
cout<<"栈顶元素的优先级 大于 刚刚输入的ch运算符的优先级"<< endl;
ch_out = NULL;
str_optr = Pop_noptr_stack(str_optr, ch_out);//弹出 OPTR栈中的运算符
cout<<"运算符出栈完毕"<< endl;
t = Pop_ntree_stack(t, t1);//弹出 EXPT栈中的第一个操作符元素
cout<<"弹出第一个操作数栈顶元素为："<< t1.data<< endl;
t = Pop_ntree_stack(t, t2);//弹出 EXPT栈中的第二个操作符元素
cout<<"弹出第二个操作数栈顶元素为："<< t2.data<< endl;
tnew = NULL; //创建一个新的二叉树
//以 ch_out为根 t1--左子树 t2--右子树 创建一个二叉树
Creat_Tree(tnew, &t2, &t1, ch_out);
cout<<"-------------------------------error------------------------------------"<< endl;
cout<< tnew->data<< endl;
if(tnew->lchild)
cout<< tnew->lchild->data<< endl;
if(tnew->rchild)
cout<< tnew->rchild->data<< endl;
cout<<"--------------------------------error-----------------------------------"<< endl;
t = Push_ntree_stack(t, *tnew);//将新建的二叉树根结点 入栈
break;
case 2://相等时
//char ch_zuokuohao;
//弹出OPTR中的栈顶元素 '(' 且 ch 为 ')'
str_optr = Pop_noptr_stack(str_optr, ch_zuokuohao);
cin>> ch;
break;
default:
break;
}//switch
}//else
}//while
return 0;
}
int main()
{
InitExpTree();//建立 表达式树
return 0;
}
