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

(0)

相关推荐

  • C语言数据结构旋转链表的实现

    C语言数据结构旋转链表的实现 实例: 给出链表1->2->3->4->5->null和k=2 返回4->5->1->2->3->null 分析: 感觉很直观,直接把分割点找出来就行,记得k可能大于len,要取模 代码: /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x

  • C语言中数据结构之链式基数排序

    C语言中数据结构之链式基数排序 实现效果图: 实例代码: #include<stdio.h> #include<string.h> #include<stdlib.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status; typedef int ElemType; #define MAX_NUM_OF_KEY 8 //关

  • C语言数据结构之双向循环链表的实例

    数据结构之双向循环链表 实例代码: #include <stdlib.h> #include <stdio.h> #include <malloc.h> typedef struct Node{ struct Node *pNext; int data; struct Node *prior; } NODE,*PNODE; PNODE CreatList(); void TreNode(PNODE pHead); bool isEmpty(PNODE pHead); i

  • C语言数据结构实现银行模拟

    C语言数据结构实现银行模拟 实现代码: #include <stdio.h> #include <stdlib.h> #include <windows.h> #define MAX_WIN 20 #define MAX_STAY 100 typedef struct customer *link; struct customer { int stay; link next; }; link GUY(int stay, link next) { link c = mal

  • C语言数据结构实现链表去重的实例

    C语言数据结构实现链表去重的实例 题目及分析 链表去重 时间限制 300 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 给定一个带整数键值的单链表L,本题要求你编写程序,删除那些键值的绝对值有重复的结点.即对任意键值K,只有键值或其绝对值等于K的第一个结点可以被保留.同时,所有被删除的结点必须被保存在另外一个链表中.例如:另L为21→-15→-15→-7→15,则你必须输出去重后的链表21→-15→-7.以及被删除的链表-15→15. 输入格式: 输入

  • C语言数据结构算法之实现快速傅立叶变换

    C语言数据结构算法之实现快速傅立叶变换 本实例将实现二维快速傅立叶变换,同时也将借此实例学习用c语言实现矩阵的基本操作.复数的基本掾作,复习所学过的动态内存分配.文件操作.结构指针的函数调用等内容. 很久以来,傅立叶变换一直是许多领域,如线性系统.光学.概率论.量子物理.天线.数字图像处理和信号分析等的一个基本分析工具,但是即便使用计算速度惊人的计算机计算离散傅立叶变换所花费的时间也常常是难以接受的,因此导致了快速傅立叶变换(FFT)的产生. 本实例将对一个二维数组进行正.反快速傅立叶变换.正傅

  • C语言数据结构 快速排序实例详解

    C语言数据结构 快速排序实例详解 一.快速排序简介 快速排序采用分治的思想,第一趟先将一串数字分为两部分,第一部分的数值都比第二部分要小,然后按照这种方法,依次对两边的数据进行排序. 二.代码实现 #include <stdio.h> /* 将两个数据交换 */ void swap(int* Ina , int* Inb) { int temp = *Ina; *Ina = *Inb; *Inb = temp; } /* 进行一趟的快速排序,把一个序列分为两个部分 */ int getPart

  • C语言 数据结构链表的实例(十九种操作)

    C语言 数据结构链表的实例(十九种操作) #include <stdio.h> #include <string.h> #include <stdlib.h> /*************************************************************************************/ /* 第一版博主 原文地址 http://www.cnblogs.com/renyuan/archive/2013/05/21/30915

  • C语言数据结构之循环链表的简单实例

     C语言数据结构之循环链表的简单实例 实例代码: # include <stdio.h> # include <stdlib.h> typedef struct node //定义链表中结点的结构 { int code; struct node *next; }NODE,*LinkList; /*错误信息输出函数*/ void Error(char *message) { fprintf(stderr,"Error:%s/n",message); exit(1)

  • C语言数据结构之栈简单操作

    C语言数据结构之栈简单操作 实验: 编写一个程序实现顺序栈的各种基本运算,并在此基础上设计一个主程序,完成如下功能: (1)初始化顺序栈 (2)插入元素 (3)删除栈顶元素 (4)取栈顶元素 (5)遍历顺序栈 (6)置空顺序栈 分析: 栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表. 对于顺序栈,入栈时,首先判断栈是否为满,栈满的条件为:p->top= =MAXNUM-1,栈满时,不能入栈; 否则出现空间溢出,引起错误,这种现象称为上溢. 出栈和读栈顶元素操作,先判栈是否为空,为空时不能操作

随机推荐