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語言數據結構之中綴樹轉后綴樹的實例，如有疑問請留言或者到本站社區交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持，大家共同進步！
新聞熱點
疑難解答
圖片精選
