中缀转前缀
思想：
用两个栈实现，规则如下：
(1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
(2) 从右至左扫描中缀表达式；
(3) 遇到操作数时，将其压入S2；
(4) 遇到运算符时，比较其与S1栈顶运算符的优先级：
(4-1) 如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈；
(4-2) 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1；
(4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
(5) 遇到括号时：
(5-1) 如果是右括号“)”，则直接压入S1；
(5-2) 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃；
(6) 重复步骤(2)至(5)，直到表达式的最左边；
(7) 将S1中剩余的运算符依次弹出并压入S2；
(8) 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。
代码如下：
#include<iostream>#include<stack>#include<string.h>using namespace std;int pri(char a){switch(a){case '+':return 1;case '-':return 1;case '*':return 2;case '/':return 2;}}int main(){char express[100];stack<char> S1,S2;cout<<"输入表达式： ";cin>>express; cout<<"您输入了："<<express<<endl;char c;for(int i=strlen(express)-1;i>=0;i--){c=express[i];if(c>='a' && c<='z')S1.push(c);else if(c==')'||S2.empty()==1||S2.top()==')'){S2.push(c);}else if(c=='('){while(S2.top()!=')'){S1.push(S2.top());S2.pop();} S2.pop();}else{while(S2.empty()==0 && pri(c) < pri(S2.top())){S1.push(S2.top());S2.pop();}S2.push(c);} } while(S2.empty()!=1){S1.push(S2.top());S2.pop();}cout<<"输出";while(S1.empty()!=1){cout<<S1.top();S1.pop();}return 0;}
还可以用map ：
map<char,int> m;
m[’+’] = 1;
m[’-’] = 1;
m[’*’] = 2;
m[’/’] = 2;
m[c] < m[symbol.top()]
中缀转后缀
思想1：建树
#include <iostream>#include <string>#include <string.h>#include <math.h>#include <stdlib.h>using namespace std;string s[105];int n=0;struct node{string v;node *l;node *r;};void dfs(node *T){if(T==NULL)return ;dfs(T->l);dfs(T->r);//cout<<T->v;s[n++]=T->v;}void f(string str,node *&T){if(T==NULL){T=new node;T->l=T->r=NULL;}int op=9999,ex=0,idx=-1;for(int i=str.length()-1; i>=0; i--){if(str[i]==')')ex+=2;else if(str[i]=='(')ex-=2;else if(str[i]=='+'||str[i]=='-'){if(ex+1<op){op=ex+1;idx=i;}}else if(str[i]=='*'||str[i]=='/'){if(ex+2<op){op=ex+2;idx=i;}}}if(idx==-1){int idx1,idx2;for(idx1=0; idx1<str.length(); idx1++)if(str[idx1]!='(')break;for(idx2=str.length()-1; idx2>=0; idx2--)if(str[idx2]!=')')break;T->v=str.substr(idx1,idx2-idx1+1);return ;}T->v=str[idx];//A+Bf(str.substr(0,idx),T->l);f(str.substr(idx+1,str.length()-idx-1),T->r);}//12.23double si(string s)//string转double{int i;double sum1=0,sum2=0;int st=-1;//小数点的位置for(i=0; i<s.length(); i++){if(s[i]=='.'){st=i;break;}}if(st==-1){sum1=atof(s.c_str());return sum1;}else{string t1=s.substr(0,st);string t2=s.substr(st+1,s.length()-st-1);sum1=atof(t1.c_str());sum2=atof(t2.c_str());return (sum1+sum2/pow(10,s.length()-st-1));}}int main(){double a[105];int i,num=0;memset(a,0,sizeof(a));node *root=NULL;string str;getline(cin,str);f(str,root);dfs(root);cout<<"后缀表达式："<<endl;for(i=0; i<n; i++)cout<<s[i];cout<<endl;cout<<"结果为："<<endl;for(i=0; i<n; i++){if(s[i][0]>='0'&&s[i][0]<='9'){a[num++]=si(s[i]);}else if(s[i][0]=='+'){double t1=a[num-2];double t2=a[num-1];a[num-1]=0;a[num-2]=0;num-=2;a[num++]=t1+t2;}else if(s[i][0]=='-'){double t1=a[num-2];double t2=a[num-1];a[num-1]=0;a[num-2]=0;num-=2;a[num++]=t1-t2;}else if(s[i][0]=='*'){double t1=a[num-2];double t2=a[num-1];a[num-1]=0;a[num-2]=0;num-=2;a[num++]=t1*t2;}else if(s[i][0]=='/'){double t1=a[num-2];double t2=a[num-1];a[num-1]=0;a[num-2]=0;num-=2;a[num++]=t1/t2;}}cout<<a[0]<<endl;return 0;}
思想2：用栈
中缀表达式转为后缀表达式也有一定的规则，这个规则是根据操作符的运算优先级来定的，还是上面那个中缀表达式为：“4.991.06+5.99+6.991.06”，转为后缀表达式的规则为：
（1）这里定义一个操作符栈stack来保存遇到的操作符，还需要定义string作为后缀表达式输出返回；（2）首先需要对输入的中缀表达式进行“切片”处理，所谓切片，即对所输入的中缀表达式进行元素分割，这里的每个元素要么是一个操作符（“+-*/()”），要么是一个操作数（“.0123456789”），把这些元素存储到一个vector<string>Inputvec中；（3）然后依次遍历Inputvec中元素，根据其是操作数还是操作符来进行不同的“处理”。这里的处理规则为：如果是操作数，则直接保存到输出string中；如果是操作符如果操作符栈为空，则把操作符入栈；否则，则比较当前运算符与栈顶操作符优先等级；如果当前操作符优先等级高，则当前操作符入栈；否则，弹出栈顶操作符到输出string中；
中缀表达式转后缀表达式C++实现代码如下：
//设置操作符优先级，这里考虑到括号（"("、")"）匹配，定义设置左括号"("的优先级最高，且只有在遇到右括号时才弹出左括号int priority(const string str) {const char *op = str.c_str();switch(*op) {case ')':return 0; case '+': case '-': return 1; case '*': case '/': return 2; case '(':return 3;default : return -1; } } /*********************中缀表达式转为后缀表达式**************************/string InfixToPostfi(const string &str){string operatorstr = "*-/+()";//用于string搜索string numbers = "0123456789.";//对输入的中缀表达式中每个元素进行切片，每个元素存储到vector<string>Inputstrvector<string> Inputvec; //存储切片结果for(unsigned int i=0; i<str.size(); ){string::size_type operatorindex = str.find_first_of(operatorstr,i);//搜索str中从i开始的第一个操作符if(operatorindex != string::npos){//如果从i开始搜索到了操作符if(operatorindex == i){//如果是两个连续的操作符，即这种形式的表达式 a*(b+c)+d;string tempstr = str.substr(operatorindex,1);Inputvec.push_back(tempstr);i = i+1;}else{Inputvec.push_back(str.substr(i,operatorindex-i));Inputvec.push_back(str.substr(operatorindex,1));i = operatorindex+1;}}else{//如果从i开始搜索到了操作符，即输入的中缀表达式以操作数结尾，不是以操作符结尾（其实一个表达式以操作符结尾的情况只可能是以右括号")"结尾，这里就是为防止这种特殊情况）Inputvec.push_back(str.substr(i,str.size()-i));i = str.size();}}//遍历切片结果vector中每个元素stack<string> operatorstack;//创建空栈，用来存储操作符vector<string> PostfiOutvec;//存储中缀输出，这里是存储到vectorfor(int i=0; i<Inputvec.size(); i++){//如果当前元素是操作符if(Inputvec[i].find_first_of(operatorstr) != string::npos){if(operatorstack.empty()){operatorstack.push(Inputvec[i]);//如果操作符栈空，则直接入栈}else{if(Inputvec[i] == ")")//如果当前操作符是右括号{while(operatorstack.top() != "("){PostfiOutvec.push_back(operatorstack.top());//将栈顶操作符输出operatorstack.pop(); //删除栈顶元素}operatorstack.pop(); //删除栈顶元素（这里是删除左括号"("）}else{int curpri = priority(Inputvec[i]);//获取操作符的优先级//比较当前操作符与栈顶元素优先级，如果小于或等于栈顶元素优先级则弹出栈顶元素，否则当前操作符入栈while(!operatorstack.empty()){string top = operatorstack.top();//返回栈顶元素int toppor = priority(top);//栈顶元素优先级if((curpri <= toppor) && top!="(") //左括号优先级最大，但是它只有遇到右括号才输出{PostfiOutvec.push_back(top);operatorstack.pop(); //删除栈顶元素}elsebreak;}operatorstack.push(Inputvec[i]);}}}//如果当前元素是操作数，直接输出else{PostfiOutvec.push_back(Inputvec[i]);}}while(!operatorstack.empty()){PostfiOutvec.push_back(operatorstack.top());//输出操作符栈中的其他操作符operatorstack.pop();}//在输出中插入空格vector<string>::const_iterator itr=PostfiOutvec.begin()+1;while(itr!=PostfiOutvec.end()){itr = PostfiOutvec.insert(itr," ");//这里一定要返回insert之后的指针，因为改变容器的操作会使迭代器失效itr+=2;}PostfiOutvec.push_back(" ");//添加最后一个空格//vector输出为string，作为后缀表达式结果返回string result;for(int i=0; i<PostfiOutvec.size(); i++){result.append(PostfiOutvec[i]);}return result;}
后缀表达式求值
思想：
后缀表达式的求值规则为：从左到右扫描后缀表达式，如果遇到一个操作数，将其压入栈中，如果遇到一个操作符，则从栈中弹出两个操作数，计算结果，然后把结果入栈，直到遍历完后缀表达式，则计算完成，此时的栈顶元素即为计算结果。
代码如下：
/*********************后缀表达式求值（直接利用C++STL提供的Stack实现）**************************/double postfixExpression(const string &str){stack<double> mystack; //栈空间string s = ".0123456789+-*/";string empty = " ";string numbers = ".0123456789";string c = "+-*/";double firstnum;double secondnum;double sum;for(unsigned int i=0; i<str.size(); ){string::size_type start = str.find_first_of(s,i);//查找第一个数字或算术符号string::size_type end = str.find_first_of(empty,i); //查找第一个空格string tempstr = str.substr(start, end-start);//取出这一个元素//判断元素if(tempstr == "+" || tempstr == "-" || tempstr == "*" || tempstr == "/"){secondnum = mystack.top(); //取当前栈顶元素，由于栈的先进后出特性，当前栈顶元素其实是二元操作符中右侧的操作数，如表达式3-2的后缀表达式为“3 2 -”，这里secondnum取得数就是2mystack.pop();firstnum = mystack.top();mystack.pop();if(tempstr == "+"){sum = firstnum + secondnum;mystack.push(sum);}if(tempstr == "-"){sum = firstnum - secondnum;mystack.push(sum);}if(tempstr == "*"){sum = firstnum * secondnum;mystack.push(sum);}if(tempstr == "/"){sum = firstnum / secondnum;mystack.push(sum);}}else{double num = stod(tempstr);mystack.push(num);}//控制迭代i = end + 1;}return mystack.top();}
