中缀树转后缀树

对于一个中缀表达式 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]='';
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]='';
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]='';
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;
}

测试文件对以上两个头文件进行了测试。

最后

以上就是魔幻彩虹为你收集整理的中缀树转后缀树的全部内容，希望文章能够帮你解决中缀树转后缀树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。