—-想了解C语言数据结构之中缀树转后缀树的实例分享的全部内容且更多的C语言教程关注<计算机技术网(www.ctvol.com)!!>
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]=' '; 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(); } }
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/488446.html