快捷導(dǎo)航

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之中綴樹(shù)轉(zhuǎn)后綴樹(shù)的實(shí)例

更新時(shí)間：2017年08月28日 15:29:53 作者：liuzhanchen1987

這篇文章主要介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之中綴樹(shù)轉(zhuǎn)后綴樹(shù)的實(shí)例的相關(guān)資料,需要的朋友可以參考下

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之中綴樹(shù)轉(zhuǎn)后綴樹(shù)的實(shí)例

對(duì)于一個(gè)中綴表達(dá)式 a+b*c*(d-e/f) 轉(zhuǎn)換成后綴是這樣的形式 abc*def/-+

后綴表達(dá)式是相當(dāng)有用處的,轉(zhuǎn)換成后綴表達(dá)式后求值會(huì)簡(jiǎn)單很多.那么該如何轉(zhuǎn)換呢?

網(wǎng)上關(guān)于這方面的資料一搜一大把,每本數(shù)據(jù)結(jié)構(gòu)的書(shū)中都會(huì)提及這個(gè)算法,在這個(gè)算法中,用到棧這個(gè)數(shù)據(jù)結(jié)構(gòu).

1,關(guān)鍵是比較運(yùn)算符的優(yōu)先級(jí),誰(shuí)的優(yōu)先級(jí)高,誰(shuí)就出現(xiàn)在前面上面的表達(dá)式中,有括號(hào)的時(shí)候括號(hào)優(yōu)先級(jí)最高,*/次之,+-最后. 在上面的表達(dá)式中+的優(yōu)先級(jí)不如*的高,因此,在后綴表達(dá)式中*出現(xiàn)在+前面,

2,遇到操作數(shù)的時(shí)候總是直接輸出,不做任何比較

3,遇到左括號(hào)總是直接入棧,遇到右括號(hào)的時(shí)候總是彈棧,一直彈到遇到一個(gè)左括號(hào)

4,遇到操作符的時(shí)候就先將這個(gè)操作符和它前面的操作符比較優(yōu)先級(jí),假如高于前面的優(yōu)先級(jí),先將它壓棧,假如低于或等于前面的操作符的優(yōu)先級(jí),就把前面的優(yōu)先級(jí)比它高的或相等的順序彈出來(lái), 一直彈到遇到優(yōu)先級(jí)比它還低的或者到了棧頂，然后該操作符再壓入棧。

知道以上四個(gè)規(guī)則就可以設(shè)計(jì)代碼實(shí)現(xiàn)了，

代碼如下：

#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]); 
      } 
      //如果非空要根據(jù)操作符的優(yōu)先級(jí)及其類別進(jìn)行判斷并分類入棧 
      else 
      { 
        char TopCh=ChStack.top(); 
        //如果是（則直接入棧 
        if(OpC[DevedeStr[i][0]]==-1) 
        { 
          ChStack.push(DevedeStr[i][0]); 
        } 
        //如果操作符優(yōu)先級(jí)大于棧中當(dāng)前操作符直接入棧 
        else if(OpC[TopCh]<OpC[DevedeStr[i][0]]) 
        { 
          ChStack.push(DevedeStr[i][0]); 
        } 
        //否則按操作符的類別有區(qū)別的處理 
        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]); 
          } 
        } 
      } 
    } 
    //如果輸入的字符串是數(shù)字 
    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。該文件的作用是輸入中綴字符串，輸出后綴字符串，其中中綴字符串不帶空格，而后綴字符串帶空格。頭文件中的另一個(gè)函數(shù)是將字符串分為字符串?dāng)?shù)組，該數(shù)組中存儲(chǔ)數(shù)字和運(yùn)算符。

#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: 
  //要計(jì)算的表達(dá)式 
  string m_expresion; 
  //將數(shù)字存儲(chǔ)到棧中 
  stack<int> m_num; 
 
public: 
  InterTreeComputer(string expression):m_expresion(expression) 
  {} 
  //判定某一操作符是否是運(yùn)算符 
  bool IsOperator(char ch)const; 
  //獲取要計(jì)算的兩個(gè)運(yùn)算數(shù) 
  void GetOperands(int &left,int &right); 
  //對(duì)獲取的兩個(gè)數(shù)按照符號(hào)ch進(jìn)行計(jì)算 
  int computer(int left,int right,char ch)const; 
  //獲取表達(dá)式 
  string GetPostoperation()const; 
  void SetPostoperator(); 
  //計(jì)算表達(dá)式并返回結(jié)果 
  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頭文件，該頭文件的作用是輸入后綴表達(dá)式并計(jì)算該表達(dá)式的值。

#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è)試文件對(duì)以上兩個(gè)頭文件進(jìn)行了測(cè)試。

以上就是數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之中綴樹(shù)轉(zhuǎn)后綴樹(shù)的實(shí)例，如有疑問(wèn)請(qǐng)留言或者到本站社區(qū)交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持，大家共同進(jìn)步！

您可能感興趣的文章: