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

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

# C语言数据结构之中缀树转后缀树  # 数据结构  # 中缀树转后缀树  # C语言数据结构实现银行模拟  # C语言数据结构旋转链表的实现  # C语言数据结构 快速排序实例详解  # C语言数据结构实现链表去重的实例  # C语言 数据结构链表的实例（十九种操作）  # C语言数据结构之栈简单操作  # C语言数据结构之双向循环链表的实例  # C语言数据结构之循环链表的简单实例  # C语言数据结构算法之实现快速傅立叶变换  # C语言中数据结构之链式基数排序  # 头文件  # 出现在  # 运算符  # 直接入  # 转换成  # 在这个  # 是这样  # 如有  # 就把  # 希望能  # 弹出  # 可以直接  # 不做  # 该如何  # 书中  # 在上面  # 谁的  # 将它  # 谢谢大家 

相关文章： 如何在Mac上搭建Golang开发环境_使用Homebrew安装和管理Go版本  简历在线制作网站免费版,如何创建个人简历？  免费制作小说封面的网站有哪些,怎么接网站批量的封面单？  独立制作一个网站多少钱,建立网站需要花多少钱？  深圳防火门网站制作公司,深圳中天明防火门怎么编码？  建站之星如何快速更换网站模板？  长沙企业网站制作哪家好,长沙水业集团官方网站？  如何用PHP快速搭建高效网站？分步指南  如何基于云服务器快速搭建网站及云盘系统？  广州顶尖建站服务：企业官网建设与SEO优化一体化方案  如何通过宝塔面板实现本地网站访问？  大连网站制作公司哪家好一点,大连买房网站哪个好？  番禺网站制作公司哪家值得合作,番禺图书馆新馆开放了吗？  建站之星安装后如何自定义网站颜色与字体？  哪家制作企业网站好,开办像阿里巴巴那样的网络公司和网站要怎么做？  建站中国必看指南：CMS建站系统+手机网站搭建核心技巧解析  早安海报制作网站推荐大全,企业早安海报怎么每天更换？  如何登录建站主机？访问步骤全解析  建站之星如何取消后台验证码生成？  建站之星如何配置系统实现高效建站？  如何在腾讯云服务器上快速搭建个人网站？  标准网站视频模板制作软件,现在有哪个网站的视频编辑素材最齐全的，背景音乐、音效等？  如何制作网站标识牌,动态网站如何制作（教程）？  大同网页,大同瑞慈医院官网？  建站之星导航配置指南：自助建站与SEO优化全解析  制作旅游网站html,怎样注册旅游网站？  网站专业制作公司有哪些,做一个公司网站要多少钱？  广州商城建站系统开发成本与周期如何控制？  建站之星如何助力网站排名飙升？揭秘高效技巧  建站之星代理商如何保障技术支持与售后服务？  视频网站app制作软件,有什么好的视频聊天网站或者软件？  如何通过多用户协作模板快速搭建高效企业网站？  制作充值网站的软件,做人力招聘为什么要自己交端口钱？  在线教育网站制作平台,山西立德教育官网？  外贸公司网站制作哪家好,maersk船公司官网？  油猴 教程,油猴搜脚本为什么会网页无法显示？  网页制作模板网站推荐,网页设计海报之类的素材哪里好？  西安大型网站制作公司,西安招聘网站最好的是哪个？  官网网站制作腾讯审核要多久,联想路由器newifi官网  已有域名建站全流程解析：网站搭建步骤与建站工具选择  如何在阿里云虚拟机上搭建网站？步骤解析与避坑指南  c# 在高并发场景下，委托和接口调用的性能对比  SAX解析器是什么，它与DOM在处理大型XML文件时有何不同？  武清网站制作公司,天津武清个人营业执照注销查询系统网站？  TestNG的testng.xml配置文件怎么写  黑客如何利用漏洞与弱口令入侵网站服务器？  如何续费美橙建站之星域名及服务？  C#怎么使用委托和事件 C# delegate与event编程方法  网站制作大概要多少钱一个,做一个平台网站大概多少钱？  ,柠檬视频怎样兑换vip？