C语言数据结构之中缀树转后缀树的实例
对于一个中缀表达式 a+b*c*(d-e/f) 转换成后缀是这样的形式 abc*def/-+
后缀表达式是相当有用处的,转换成后缀表达式后求值会简单很多.那么该如何转换呢?
网上关于这方面的资料一搜一大把,每本数据结构的书中都会提及这个算法,在这个算法中,用到 栈 这个数据结构.
1,关键是比较运算符的优先级,谁的优先级高,谁就出现在前面上面的表达式中,有括号的时候括号优先级最高,*/次之,+-最后. 在上面的表达式中+的优先级不如*的高,因此,在后缀表达式中*出现在+前面,
2,遇到操作数的时候总是直接输出,不做任何比较
3,遇到左括号总是直接入栈,遇到右括号的时候总是弹栈,一直弹到遇到一个左括号
4,遇到操作符的时候就先将这个操作符和它前面的操作符比较优先级,假如高于前面的优先级,先将它压栈,假如低于或等于前面的操作符的优先级,就把前面的优先级比它高的或相等的顺序弹出来, 一直弹到遇到优先级比它还低的或者到了栈顶 ，然后该操作符再压入栈。
知道以上四个规则就可以设计代码实现了，
代码如下：
|
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
|
#include<iostream> #include<string> #include<stack> #include<map> using namespace std; void InerStringDevide(string InerStr,string DeviStr[],int &num) { int count,i; int numbe=InerStr.size(); for(i=0;i<numbe;i++) DeviStr[i][0]='\0'; count=0; for(i=0;i<numbe;) { if(InerStr[i]=='+'||InerStr[i]=='-'||InerStr[i]=='*'|| InerStr[i]=='/'||InerStr[i]=='%'||InerStr[i]=='^' ||InerStr[i]=='('||InerStr[i]==')') { DeviStr[count].push_back(InerStr[i]); count++; i++; } else { while(InerStr[i]!='+'&&InerStr[i]!='-'&&InerStr[i]!='*'&& InerStr[i]!='/'&&InerStr[i]!='%'&&InerStr[i]!='^' &&InerStr[i]!='('&&InerStr[i]!=')') { DeviStr[count].push_back(InerStr[i]); i++; if(i>=numbe) break; } count++; } } num=count; } void InerTreeToPostTree(string InerStr,string &PostStr) { PostStr[0]='\0'; map<char,int>OpC; typedef map<char,int>::value_type ValType; OpC.insert(ValType('+',1)); OpC.insert(ValType('-',1)); OpC.insert(ValType('*',2)); OpC.insert(ValType('/',2)); OpC.insert(ValType('%',2)); OpC.insert(ValType('^',3)); OpC.insert(ValType('(',-1)); OpC.insert(ValType(')',0)); int num,i,j,StrNum; num=InerStr.size(); string *DevedeStr=new string[num]; InerStringDevide(InerStr,DevedeStr,StrNum); stack<char> ChStack; int count=0; for(int i=0;i<StrNum;i++) { //如果输入的字符串是操作符 if(DevedeStr[i][0]=='+'||DevedeStr[i][0]=='-'||DevedeStr[i][0]=='*'|| DevedeStr[i][0]=='/'||DevedeStr[i][0]=='%'||DevedeStr[i][0]=='^' ||DevedeStr[i][0]=='('||DevedeStr[i][0]==')') { //如果操作符栈中为空可以直接将操作符入栈 if(ChStack.empty()) { ChStack.push(DevedeStr[i][0]); } //如果非空要根据操作符的优先级及其类别进行判断并分类入栈 else { char TopCh=ChStack.top(); //如果是（则直接入栈 if(OpC[DevedeStr[i][0]]==-1) { ChStack.push(DevedeStr[i][0]); } //如果操作符优先级大于栈中当前操作符直接入栈 else if(OpC[TopCh]<OpC[DevedeStr[i][0]]) { ChStack.push(DevedeStr[i][0]); } //否则按操作符的类别有区别的处理 else { //如果遇到）则操作符出栈并入字符串 if(OpC[DevedeStr[i][0]]==0) { TopCh=ChStack.top(); while(OpC[TopCh]!=-1) { if(!PostStr.empty()) { PostStr.push_back(' '); } PostStr.push_back(TopCh); ChStack.pop(); TopCh=ChStack.top(); } ChStack.pop(); TopCh=ChStack.top(); } else { while(OpC[TopCh]>=OpC[DevedeStr[i][0]]&&OpC[TopCh]!=-1) { if(!PostStr.empty()) { PostStr.push_back(' '); } PostStr.push_back(TopCh); ChStack.pop(); if(!ChStack.empty()) TopCh=ChStack.top(); else break; } ChStack.push(DevedeStr[i][0]); } } } } //如果输入的字符串是数字 else { int DevideSize=DevedeStr[i].size(); if(!PostStr.empty()) { PostStr.push_back(' '); } for(int j=0;j<DevideSize;j++) { PostStr.push_back(DevedeStr[i][j]); } } } while(!ChStack.empty()) { if(!PostStr.empty()) { PostStr.push_back(' '); } PostStr.push_back(ChStack.top()); ChStack.pop(); } } |
以上为头文件InerTreeToPostTree.h。该文件的 作用是输入中缀字符串，输出后缀字符串，其中中缀字符串不带空格，而后缀字符串带空格。头文件中的另一个函数是将字符串分为字符串数组，该数组中存储数字和运算符。
|
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
#include<iostream> #include<stack> #include<string> using namespace std; void StringDevide(string str,int &num,string st1[]) { for(int i=0;i<100;i++) st1[i][0]='\0'; int n=str.size(); int j=0,count=0; for(int i=0;i<n;i++) { if(str[i]!=' ') { st1[count].push_back(str[i]); } else { count++; } } num=count+1; } void StringToNum(string str,int &num) { num=0; int n=str.size(); for(int i=0;i<n;i++) { num=num*10; num+=str[i]-'0'; } } class InterTreeComputer { private: //要计算的表达式 string m_expresion; //将数字存储到栈中 stack<int> m_num; public: InterTreeComputer(string expression):m_expresion(expression) {} //判定某一操作符是否是运算符 bool IsOperator(char ch)const; //获取要计算的两个运算数 void GetOperands(int &left,int &right); //对获取的两个数按照符号ch进行计算 int computer(int left,int right,char ch)const; //获取表达式 string GetPostoperation()const; void SetPostoperator(); //计算表达式并返回结果 int Evaluate(); }; bool InterTreeComputer::IsOperator(char ch)const{ switch(ch) { case '+': case '-': case '*': case '/': case '%': case '^': return 1; default: return 0; } } void InterTreeComputer::GetOperands(int &left,int &right) { if(m_num.empty()) { cout<<"num stack is empty!"; return ; } right=m_num.top(); m_num.pop(); if(m_num.empty()) { cout<<"the expression is wrong!"<<endl; return ; } left=m_num.top(); m_num.pop(); } int InterTreeComputer::computer(int left,int right,char ch)const{ switch(ch) { case '+': return left+right; break; case '-': return left-right; break; case '*': return left*right; break; case '/': if(right==0) { cout<<"the expression is wrong"<<endl; return -1; } return left/right; break; case '%': return left%right; break; case '^': if(left==0&&right==0) { cout<<"the expression is wrong"<<endl; return -1; } int value=1; while(right>0) { value*=left; right--; } return value; break; } } string InterTreeComputer::GetPostoperation()const{ return m_expresion; } void InterTreeComputer::SetPostoperator() {} int InterTreeComputer::Evaluate() { string *str=new string[100]; int num; StringDevide(m_expresion,num,str); for(int i=0;i<num;i++) { if(str[i][0]=='+'||str[i][0]=='-'||str[i][0]=='*'||str[i][0]=='/' ||str[i][0]=='%'||str[i][0]=='^') { char ch=str[i][0]; int left,right; GetOperands(left,right); int number=computer(left,right,ch); m_num.push(number); } else { int numb=0; StringToNum(str[i],numb); m_num.push(numb); } } return m_num.top(); } |
以上代码为InerTreeComputer.h头文件，该头文件的作用是输入后缀表达式并计算该表达式的值。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include<iostream> using namespace std; #include<string> #include<stack> #include"InterTreeComputer.h" #include"InerTreeToPostTree.h" int main() { string str="3*(4-2^5)+6"; string st1="2 3 ^ 1 +"; string st2="2 2 3 ^ ^ 4 /"; string StrRe; InerTreeToPostTree(str,StrRe); InterTreeComputer Comp(StrRe); cout<<Comp.GetPostoperation()<<endl; cout<<Comp.Evaluate()<<endl; return 0; } |
测试文件对以上两个头文件进行了测试。
以上就是数据结构C语言数据结构之中缀树转后缀树的实例，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持，大家共同进步！
原文链接：http://blog.csdn.net/liuzhanchen1987/article/details/7387480
