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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
//简单起见，每个运算数节点存储的为小写英文字母
#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;
}