把中缀表达式转换为表达式树

//简单起见，每个运算数节点存储的为小写英文字母
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
struct BinTreeNode{
char Element;
struct BinTreeNode* Left;
struct BinTreeNode* Right;
};
struct BinTreeNode* CreateNode(char ch)
{
struct BinTreeNode* temp;
temp=(struct BinTreeNode*)malloc(sizeof(struct BinTreeNode));
temp->Left=NULL;
temp->Right=NULL;
temp->Element=ch;
return temp;
}
void PreTrversal(struct BinTreeNode* ExpTree)
{
if(ExpTree==NULL)
return;
printf("%c ",ExpTree->Element);
if(ExpTree->Left!=NULL)
PreTrversal(ExpTree->Left);
if(ExpTree->Right!=NULL)
PreTrversal(ExpTree->Right);
return;
}
int main()
{
char data[100];
struct BinTreeNode* stack1[100];//存运算数
struct BinTreeNode* stack2[100];//存运算符
int top1=-1;
int top2=-1;
gets(data);
for(int i=0;data[i]!='';i++){
if(data[i]=='('){
struct BinTreeNode* temp;
temp=CreateNode(data[i]);
stack2[++top2]=temp;
}
else if(data[i]==')'){
while(stack2[top2]->Element!='('){
struct BinTreeNode* temp=stack2[top2];
struct BinTreeNode* t1=stack1[top1--];
struct BinTreeNode* t2=stack1[top1--];
temp->Left=t2;
temp->Right=t1;
stack1[++top1]=temp;
top2--;
}
top2--;
}
else if(strchr("+-*/",data[i])!=NULL){
if(data[i]=='+'||data[i]=='-'){
while(top2>=0&&stack2[top2]->Element!='('){
struct BinTreeNode* temp=stack2[top2];
struct BinTreeNode* t1=stack1[top1--];
struct BinTreeNode* t2=stack1[top1--];
temp->Left=t2;
temp->Right=t1;
stack1[++top1]=temp;
top2--;
}
}
else if(data[i]=='*'||data[i]=='/'){
while(top2>=0&&stack2[top2]->Element!='('&&stack2[top2]->Element!='+'&&stack2[top2]->Element!='-'){
struct BinTreeNode* temp=stack2[top2];
struct BinTreeNode* t1=stack1[top1--];
struct BinTreeNode* t2=stack1[top1--];
temp->Left=t2;
temp->Right=t1;
stack1[++top1]=temp;
top2--;
}
}
struct BinTreeNode* temp=CreateNode(data[i]);
stack2[++top2]=temp;
}
else{
struct BinTreeNode* temp=CreateNode(data[i]);
stack1[++top1]=temp;
}
}
while(top2>=0){//处理栈中剩余的运算符
struct BinTreeNode* temp=stack2[top2];
struct BinTreeNode* t1=stack1[top1--];
struct BinTreeNode* t2=stack1[top1--];
temp->Left=t2;
temp->Right=t1;
stack1[++top1]=temp;
top2--;
}
struct BinTreeNode* ExpTree=stack1[top1];
//为了验证，先序遍历一遍
PreTrversal(ExpTree);
return 0;
}

最后

以上就是认真紫菜最近收集整理的关于把中缀表达式转换为表达式树的全部内容，更多相关把中缀表达式转换为表达式树内容请搜索靠谱客的其他文章。