溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹了怎么在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進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
