这篇文章主要介绍了怎么在C语言中将中缀树转换成后缀树，此处通过实例代码给大家介绍的非常详细，对大家的学习或工作具有一定的参考价值，需要的朋友可以参考下：
C语言是一门面向过程的、抽象化的通用程序设计语言，广泛应用于底层开发，使用C语言可以以简易的方式编译、处理低级存储器。
代码如下：
#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语言中将中缀树转换成后缀树的内容请搜索亿速云以前的文章或继续浏览下面的相关文章希望大家以后多多支持亿速云！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
