C语言数据结构之中缀树转后缀树的实例

对于一个中缀表达式 a+b*c*(d-e/f) 转换成后缀是这样的形式 abc*def/-+

后缀表达式是相当有用处的,转换成后缀表达式后求值会简单很多.那么该如何转换呢?

网上关于这方面的资料一搜一大把,每本数据结构的书中都会提及这个算法,在这个算法中,用到 栈 这个数据结构.

1,关键是比较运算符的优先级,谁的优先级高,谁就出现在前面上面的表达式中,有括号的时候括号优先级最高,*/次之,+-最后. 在上面的表达式中+的优先级不如*的高,因此,在后缀表达式中*出现在+前面,

2,遇到操作数的时候总是直接输出,不做任何比较

3,遇到左括号总是直接入栈,遇到右括号的时候总是弹栈,一直弹到遇到一个左括号

4,遇到操作符的时候就先将这个操作符和它前面的操作符比较优先级,假如高于前面的优先级,先将它压栈,假如低于或等于前面的操作符的优先级,就把前面的优先级比它高的或相等的顺序弹出来, 一直弹到遇到优先级比它还低的或者到了栈顶 ，然后该操作符再压入栈。

知道以上四个规则就可以设计代码实现了，

代码如下：

#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。该文件的 作用是输入中缀字符串，输出后缀字符串，其中中缀字符串不带空格，而后缀字符串带空格。头文件中的另一个函数是将字符串分为字符串数组，该数组中存储数字和运算符。

#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头文件，该头文件的作用是输入后缀表达式并计算该表达式的值。

#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语言数据结构之中缀树转后缀树的实例，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持，大家共同进步！