如何将一个表达式转换成二叉树理解
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define MAXNUM 1000
typedef int DataType;
struct BinTreeNode;
typedef struct BinTreeNode*PBinTreeNode;
struct BinTreeNode
{
DataType info;
PBinTreeNode llink;
PBinTreeNode rlink;
};
typedef struct BinTreeNode*BinTree;
typedef BinTree*PBinTree;
int extoBinTree(PBinTree pbtree,const char *ex,int n)
/*从中缀表达式ex(长度为n)创建二叉树。若是一个合法的表达式，则返回TRUE，且算法结束时*pbtree存放二叉树的根节点的地址；否则返回FALSE*/
{
char c;
int index,i,bracket;
int have_bracket=FALSE; /*记录表达式中是否包含括号*/
int num,state_int,nint;
int tag1,tag2;
if(ex[0]==' '||ex[0]==''||ex[0]=='
')
return extoBinTree(pbtree,ex+1,n-1);/*忽略掉左边的若干空字符*/
if(ex[n-1]==' '||ex[0]==''||ex[0]=='
')
return extoBinTree(pbtree,ex,n-1);/*忽略掉右边的若干空字符*/
if(ex[0]=='('&&ex[n-1]==')')
return extoBinTree(pbtree,ex+1,n-2);/*忽略掉左右的成对括号*/
bracket=0;
index=n;
for(i=n-1;i>=0;i--)/*从后向前搜索，寻找到第一个不在括号中的优先级最低的运算符*/
{
c=ex[i];
if(c==')')/*进入一层括号*/
{
have_bracket=TRUE;
bracket++;
}
if(c=='(') bracket--;/*出一层括号*/
if(bracket<0)/*左右括号不相匹配，表达式非法*/
{
*pbtree=NULL;
return FALSE;
}
if(bracket>0) continue;/*若当前位置在某层括号中，直接搜索下个位置*/
if(c=='+'||c=='-')
if(index==n||ex[index]=='*'||ex[index]=='/')
index=i;
if(c=='*'||c=='/')
if(index==n)
index=i;
}
if(bracket!=0) return FALSE;/*左右括号不相匹配，表达式非法*/
if(index==n)/*说明这是一个只含一个数字和若干空字符的表达式，相应地创建一棵只含一个根节点的二叉树*/
{
if(have_bracket==TRUE)
{
*pbtree=NULL;
return FALSE;
}/*不应含有括号*/
nint=0;/*nint记录表达式中含有的整数个数*/
state_int=FALSE;/*state_int记录当前读入的字符是否是数字字符*/
num=0;
for(i=0;i<n;i++)
{
c=ex[i];
switch(c)
{
case'0':case'1':case'2':case'3':case'4':
case'5':case'6':case'7':case'8':case'9':
if(state_int==FALSE)
{
num=c-'0';
state_int=TRUE;
nint++;
}
else
{
num=num*10+c-'0';
}
break;
case' ':case'':case'
':
state_int=FALSE;
break;
default: /*出现了非法字符*/
*pbtree=NULL;
return FALSE;
}
}
if(nint!=1)
{
*pbtree=NULL;
return FALSE;
}
*pbtree=(BinTree)malloc(sizeof(struct BinTreeNode));
(*pbtree)->info=num;
(*pbtree)->llink=NULL;
(*pbtree)->rlink=NULL;
return TRUE; /*成功创建了一棵只含一个根节点的二叉树*/
}
*pbtree=(BinTree)malloc(sizeof(struct BinTreeNode));
(*pbtree)->info=ex[index];
tag1 =extoBinTree(&(*pbtree)->llink,ex,index);/*递归调用本算法创建左子数*/
tag2 =extoBinTree(&(*pbtree)->rlink,ex+index+1,n-index-1);/*递归调用本算法创建右子数*/
if(tag1==TRUE&&tag2==TRUE) return TRUE;
return FALSE;
}
int cal(BinTree btree,int*presult)/*计算二叉树btree所代表的表达式的值。若是一个合法的表达式，则返回TRUE，且算法结束时*presult中存放计算结果；否则，返回FALSE.*/
{
int result1,result2;
if(btree==NULL) return FALSE; /*空树，无法计算*/
if(btree->llink==NULL&&btree->rlink==NULL) /*只有一个节点，直接计算*/
{
*presult=btree->info;
return TRUE;
}
if(btree->llink==NULL||btree->rlink==NULL) /*只有左子树或只有右子树，无法计算*/
return FALSE;
switch(btree->info)
{
case'+':
if(cal(btree->llink,&result1)==FALSE) return FALSE;
if(cal(btree->rlink,&result2)==FALSE) return FALSE;
*presult=result1+result2;
return TRUE;
case'-':
if(cal(btree->llink,&result1)==FALSE) return FALSE;
if(cal(btree->rlink,&result2)==FALSE) return FALSE;
*presult=result1-result2;
return TRUE;
case'*':
if(cal(btree->llink,&result1)==FALSE) return FALSE;
if(cal(btree->rlink,&result2)==FALSE) return FALSE;
*presult=result1*result2;
return TRUE;
case'/':
if(cal(btree->llink,&result1)==FALSE) return FALSE;
if(cal(btree->rlink,&result2)==FALSE) return FALSE;
*presult=result1/result2;
return TRUE;
default:
return FALSE;
}
}
void delete_BTree(PBinTree ptree)
{
BinTree temp=(*ptree);
if(temp==NULL) return;
delete_BTree(&(temp->llink));
delete_BTree(&(temp->rlink));
free(temp);
}
void getline(char *line,int limit)/*从标准输入中读入一行，作为字符串line*/
{
char c;
int i=0;
while(i<limit-1&&(c=getchar())!=EOF&&c!='
')
line[i++]=c;
line[i]='\0';
}
int main()
{
char c,ex[MAXNUM];
int result,flag=TRUE;
BinTree btree;
while(flag==TRUE)
{
printf("Please input the expression:");
getline(ex,MAXNUM);/*读入中缀表达式*/
if(extoBinTree(&btree,ex,strlen(ex))==FALSE)
{
printf("Wrong input!
");
delete_BTree(&btree);
printf("
Continue?(y/n)");
scanf("%c",&c);
if(c=='n'||c=='N') flag=FALSE;
while(getchar()!='
');
printf("
");
continue;
}
if(cal(btree,&result)==TRUE) printf("Result:%d
",result);
else printf("Wrong input!
");
delete_BTree(&btree);
printf("
Continue?(y/n)");
scanf("%c",&c);
if(c=='n'||c=='N') flag=FALSE;
while(getchar()!='
');
printf("
");
}
}
学过，忘记了很多了，给你找了个相关的页面：
http://topic.csdn.net/t/20050428/17/3974054.html
表达式生成树的特点为:
a. 叶子节点都是操作数；
b. 非叶子节点都是运算符；
c. 树根的运算符优先级低；
步骤如下
找到表达式中优先级最低的运算符作为树根（注意括号会提升内部的优先级），并将原表达式分解成左右两个表达式;
分别对左右表达式做步骤1, 左边生成的树为树根的左子树，右边生成的树为树根的右子树；
重复步骤1,2， 直到分解的表达式里没有运算符（只剩下数字）为止；
－
/ \
* d
/ \
a +
/ \
b c
怎样将数学表达式转化为计算机可以识别的形式
1、电脑上面的的分数形式通常是使用“\/”来表示。如4\/5，则称为五分之四。键盘上就是按小键盘的“\/”符号，输入相应数字即可。2、数学上常见的几分之几的形式，通常是在WPS软件中使用才可体现出来。以WPS表格为例。新建一个空白表格进入。3、点击菜单栏上方的插入选项。4、再选择公式的选项。就会...
逆波兰表达式怎么转换
4. 构建逆波兰表达式：当整个中缀表达式处理完毕，栈中剩余的元素就是转换后的逆波兰表达式。从栈底到栈顶依次取出元素并输出，即得到逆波兰表达式。在这个过程中要确保正确处理优先级较高的操作符。有时需要将中间计算结果也放入输出中以确保顺序正确。通过以上步骤，我们可以将中缀表达式转换为逆波兰表达式。
后缀表达式表达式之间的转换
计算机实现后缀表达式转换的算法是基于扫描中缀表达式的。首先，从左到右遍历，遇到数字时，直接将其加入后缀表达式。当遇到运算符时，根据其类型处理：如果是左括号'('，入栈。 如果是右括号')'，从栈顶开始取出运算符，直到遇到左括号，同时将这些运算符添加到后缀表达式中，然后删除左括号。 对于除...
如何将与或表达式转换成与非与非表达式
F= （（AB'+A'B）'）' =（（A'+B）(A+B'）)' 这是或-与非。其实记住“与”就是相乘，“或”就是相加，“非”就是取反，“与或”因为与在前面，所以先“与”再“或”，其他以此类推。简介 用逻辑运算符将关系表达式或逻辑量连接起来的有意义的式子称为逻辑表达式。逻辑表达式的值是一...
C语言中可以用什么将一个表达式的值转换成所需的类型
在能转换的域里，用“强制转换”办法就可以实现。比如double x=(double)e;将表达式e的值强制为double类型。
如何将一个表达式转换成二叉树理解
树根的运算符优先级低；步骤如下 找到表达式中优先级最低的运算符作为树根（注意括号会提升内部的优先级），并将原表达式分解成左右两个表达式;分别对左右表达式做步骤1, 左边生成的树为树根的左子树，右边生成的树为树根的右子树；重复步骤1,2， 直到分解的表达式里没有运算符（只剩下数字）为止；...
如何将与或型的数学表达式转换为或与式的数学表达式?
将与或式转换为或与型的基本方法是：利用对偶规则求出与或式的对偶式，将对偶式展开，化简；最后将对偶式进行对偶变换，即可得到或与型逻辑式。这里请注意，与或式进行对偶变换，得到或与式，展开就得到与或式，再一次对偶就得到或与式。
如何把算术表达式转化为后缀表达式
这里我给出一个中缀表达式：a+b*c-(d+e)第一步：按照运算符的优先级对所有的运算单位加括号：式子变成拉：((a+(b*c))-(d+e))第二步：转换前缀与后缀表达式 前缀：把运算符号移动到对应的括号前面 则变成拉：-( +(a *(bc)) +(de))把括号去掉：-+a*bc+de 前缀式子出现 后缀：把...
怎样将一个表达式中的字符串转换为整形?
先执行a-=a*a，即a=a-a*a 3-3*3=-6，a=-6 再执行a+=a，即a=a+a -6+(-6)=-12 a=-12 a的值是-12
逆波兰表达式怎么转换
逆波兰表达式的转换方法是：语法分析、创建栈、弹出。1、语法分析：这个过程主要是对输入的中缀表达式进行深入的语法检查，确保其符合我们预设的规则。我们会仔细检查表达式中的每一项，包括运算符和操作数，以确保它们都符合我们的规范。这包括检查每个运算符是否正确，以及运算符之间的优先级和结合性是否得到...
鄞景雅森：[答案] 表达式生成树的特点为: a. 叶子节点都是操作数; b. 非叶子节点都是运算符; c. 树根的运算符优先级低;步骤如下找到表达式中优先级最低的运算符作为树根(注意括...
武功县19812936717： 如何将将算术表达式转化成二叉树 - ？
鄞景雅森：[答案] 将操作数作为二叉树的叶子结点,操作符作为二叉树的非叶子结点先序遍历则得到前缀式中序遍历则得到中缀式后序遍历则得到后缀式//以(a+b)/c-d+e*f进行演示 + (-...
武功县19812936717： 如何将将算术表达式转化成二叉树 - ？
鄞景雅森： b吧,你按照运算顺序,是先d/e,然后c+,然后b*,a+,所以顺序就是/ + * +
武功县19812936717： 把逻辑表达式转成前缀二叉树 ,c++ 或C 源代码 - ？
鄞景雅森： 思路:前缀二叉树表达式就是一个栈,括号的含义就是出栈入栈,所有数据顺序入栈,遇到右括号时开始出栈,直到碰到左括号,中间一段表达式就是作为树节点,其中=> and or等表达式都是非叶节点.伪代码如下:主函数 for (i=0;i<s.size();i+...
武功县19812936717： 表达式 a*(b+c) - d 的后缀表达式?请一步一步的说! - ？
鄞景雅森：[答案] 表达式 a*(b+c)-d是中缀表达式,转化成二叉树后,它是中序遍历的结果 二叉树如下图: ______(-)_________ _____/___\________ ____(*)__(d)______ ____/__\__________ __(a)__(+)________ ______/___\_______ ____(b)___(c)____...
武功县19812936717： 前缀中缀后缀表达式的转换,能帮一下吗? - ？
鄞景雅森： 思路的话其实很简单,就是构建一棵二叉树,根节点和中间节点为运算符,叶子结点为运算数字.如 a + b*c, 构建为二叉树的话,就如下图:+ a *b c 对于该二叉树,使用不同的遍历方式就可以得到不同的表达式了.遍历的代码很简单就不多...
武功县19812936717： 请教一个将算术表达式转换成二叉树的问题 - ？
鄞景雅森： 只含有+-*/的中缀表达式到表达式树的转换过程:当扫描的是运算数时,先检查当前的表达式树是否存在,如果不存在,则表示扫描到的第一个运算数,将它作为根节点,如果树存在则将此运算数作为前一个运算符的右儿子.如果扫描到的是+或-,它一定是目前已知的最后的运算符,于是将它作为根节点,原来的树作为它的左子树,如果扫描到的是*或/,则与根节点比较,如果根节点是*或/,则根节点应该先执行,于是将当前运算符作为根结点,原来的树作为左子树,如果根结点是+或-,则当前运算符应该优先执行,于是将它作为右子树的根,原来的右子树作为它的左子树.
武功县19812936717： c语言中缀表达式转换成二叉树,后续周游计算表达式的值 - ？
鄞景雅森： #include<stdio.h>#include<stdlib.h>#include<string.h>#define TRUE 1#define FALSE 0#define MAXNUM 1000 typedef int DataType; struct BinTreeNode; typedef struct BinTreeNode*PBinTreeNode; struct BinTreeNode { DataType info; ...
武功县19812936717： 按给定的表达式建立相应的二叉树 - ？
鄞景雅森： #include <stdio.h> #include <malloc.h> typedef struct node{ int data; struct node *lchild,*rchild; }*treetp,tree; treetp create (treetp t,int c); void print1(treetp); void print2(treetp); void print3(treetp); int number=0; void main() {treetp t=0,r;r=create (t,0); ...
