中缀表达式是一个通用的算术或逻辑公式表示方法， 操作符是以中缀形式处于操作数的中间，是人们常用的算术表示方法。
后缀表达式指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行(不再考虑运算符的优先规则)。
中缀表达式转后缀表达式 A+(B-C)*D+E/F 的转换为例
第一种：基于堆栈的算法
下面简述转换方法：
1、遇到操作数，直接输出。
2、如果不是操作数，分为以下几种情况
（1）如果是左括号'('，则入栈。（特别注意左括号'('入栈后优先级为最小。）
（2）如果操作符栈为空，则入栈。
（3）如果当前操作符优先级大于栈顶操作符，则入栈。
（4）如果当前操作符优先级小或等于栈顶操作符，则操作符栈出栈（且输出），直到当前操作符优先级大于栈顶操作符，或者操作符栈为空，或者遇到 左括号'('为止，入栈当前操作符。
（5）如果是右括号')'，则操作符栈一直出栈（且输出），直到遇到 左括号'('，并出栈左括号'('。
（6）如果当前字符串读入完毕，且操作符栈非空，则操作符栈一直出栈（且输出），直到操作符栈为空。
1. //C语言 代码 2. #include <stdio.h> 3. #include <string.h> 4. typedef struct node{//建立栈模拟结构体 5. char s[310];int top;//s存储符号 top为栈顶指针 6. }Stack; 7. int weight(char ch){//运算符优先级 flag确定'('来源 8. if(ch=='+'||ch=='-') return 1; 9. if(ch=='*'||ch=='/'||ch=='^') return 2; 10. if(ch=='(') return 0; 11. } 12. void transform(char str[]){ 13. Stack a;//新建栈a 14. a.top=-1;//初始化栈指针 15. int i,f=0,m=strlen(str); 16. for(i=0;i<m;i++){//遍历整个字符串 17. if(str[i]>='A'&&str[i]<='Z')//1.读取字符串是数字直接弹出 18. printf("%c",str[i]); 19. else { 20. if(a.top==-1||str[i]=='('){//2.读取是操作符 如栈为空 直接入栈 21. a.s[++a.top]=str[i];continue; 22. } 23. else if(str[i]==')'){//3.读取是操作符 是')'且栈不为空 弹出栈顶元素直到找到'('为止 24. while(a.top!=-1&&a.s[a.top]!='(') 25. printf("%c",a.s[a.top--]); 26. --a.top;continue;//弹出'(' 27. } 28. //4.读取是操作符 字符串字符大于栈顶字符的优先级 直接入栈 29. else if(weight(str[i])>weight(a.s[a.top])){ 30. a.s[++a.top]=str[i];continue; 31. } 32. //5.读取是操作符 栈不为空 且 字符串字符<=栈顶字符的优先级 33. //重复弹出栈定字符 直到 栈为空 或者 字符串字符>栈顶字符的优先级 或者碰到'(' 34. while(a.top!=-1&&weight(str[i])<=weight(a.s[a.top])&&a.top!='('){ 35. printf("%c",a.s[a.top]);--a.top;f=1; 36. } 37. if(f==1){//将新读取字符加入栈顶 38. a.s[++a.top]=str[i];f=0; 39. } 40. } 41. } 42. //6.字符串读取结束，如果栈不为空重复弹出栈顶字符 直到栈空 43. while(a.top!=-1) printf("%c",a.s[a.top--]); 44. } 45. int main(int argc, char *argv[]) 46. { 47. char str[310]; 48. gets(str); 49. transform(str); 50. return 0; 51. } 52. 53. //输入：A+B*C+(D*E+F)*G 54. //输出：ABC*+DE*F+G*+ 55. 56. //输入：A+((B+C)*D)–E 57. //输出：ABC+D*+E- 58. 59. //输入：A+(B-C)*D+E/F 60. //输出：ABC-D*+EF/+ 61. 62. //输入：A+(B+C)*(D^E+F*G)/(H) 63. //输出：ABC+DE^FG*+*H/+
第二种：括号法 A+B*C+(D*E+F)*G
1)先按照运算符的优先级对中缀表达式加括号，变成( ( A+(B*C) ) + ( ((D*E)+F) *G ) )
2)将运算符移到括号的后面，变成((A(BC)*)+(((DE)*F)+G)*)+
3)去掉括号，得到ABC*+DE*F+G*+
A+((B+C)*D)–E
((A+((B+C)*D))–E)
((A((BC)+D)*)+E)–
ABC+D*+E-
A+(B-C)*D+E/F
((A+((B-C)*D))+(E/F))
((A((BC)-D)*)+(EF)/)+
ABC-D*+EF/+
A+(B+C)*(D^E+F*G)/(H)
(A+((B+C)*((D^E)+(F*G))/(H)))
(A((BC)+((DE)^(FG)*)+*(H))/)+
ABC+DE^FG*+*H/+
第三种：利用语法树
步骤如下
1. 找到表达式中优先级最低的运算符作为树根（注意括号会提升内部的优先级）,并将原表达式分解成左右两个表达式;
2. 分别对左右表达式做步骤: 左边生成的树为树根的左子树,右边生成的树为树根的右子树；
3. 重复步骤1,2, 直到分解的表达式里没有运算符（只剩下数字）为止；
1、将A+B*C+(D*E+F)*G式子转化为二叉树
2、通过后序遍历将其写出来，即可得到结果：ABC*+DE*F+G*+
在这里补充一点，如何将表达式变成二叉树：
表达式生成树的特点为:
a. 叶子节点都是操作数；
b. 非叶子节点都是运算符；
c. 树根的运算符优先级低；
注意一点：在遇到像本式中a后面的+号和c后面的+的优先级问题，在正常计算时a后面的+会先使用所以他的优先级比c后面的+优先级高。所以能得到上面的二叉树。
例如：将A+((B+C)*E)-F式子转化为二叉树，通过后序遍历可得到结果：ABC+E*+F-
例如：将A+(B-C)*D+E/F式子转化为二叉树，通过后序遍历可得到结果：ABC-D*+EF/+
例如：将A+(B+C)*(D^E+F*G)/(H)式子转化为二叉树，通过后序遍历可得到结果：ABC+DE^FG*+*H/+
输入中缀表达式计算表达式的结果
【输入样例】1+(3+2)*(7^2+6*9)/(2) 【输出样例】258
1. //C++代码 注意测试点课能有 +-*/^()0~9 以外的字符 2. #include <iostream> 3. #include <cstdio> 4. #include <cstring> 5. #include <string> 6. #include <stack> 7. #include <cmath> 8. #include <cstdlib> 9. #include <vector> 10. using namespace std; 11. int get_fast(string op)//运算符的优先级 12. { 13. int ans=-1; 14. switch(op[0]){ 15. case '+':case '-': ans=1;break; 16. case '*':case '/': ans=2;break; 17. case '^': ans=3;break; 18. } 19. return ans; 20. } 21. vector<string> scaner(string s)//将字符串解析到vector 22. { 23. vector<string> ans; 24. string ops="+-*/^()"; 25. string t=""; 26. for(int i=0;i<s.size();i++){ 27. if(s[i]>='0'&&s[i]<='9') t+=s[i]; 28. else if(ops.find(s[i])!=string::npos) {//注意有特殊字符 29. if(t.size()>0)ans.push_back(t); 30. t=s[i]; 31. ans.push_back(t); 32. t=""; 33. } 34. } 35. if(t.size())ans.push_back(t);//将最后一个数字放入vector 36. //for(int i=0;i<ans.size();i++)cout<<ans[i]; 37. //cout<<endl; 38. return ans; 39. } 40. vector<string> infix_suffix(vector<string> exp)//中缀表达式转后缀表达式 41. { 42. vector<string> ans; 43. stack<string> st; 44. string ops="+-*/^"; 45. for(int i=0;i<exp.size();i++){ 46. if(exp[i]=="(")//1、"("直接进栈 47. st.push(exp[i]); 48. else if(exp[i]==")"){//2、")"在找到"("之前连续出栈运算符 49. while(st.top()!="("){ 50. ans.push_back(st.top()); 51. st.pop(); 52. } 53. st.pop();//弹出"(" 54. } 55. else if(ops.find(exp[i])!=string::npos){//3、确定是运算符 56. while(st.size()&&get_fast(exp[i])<=get_fast(st.top())){ 57. ans.push_back(st.top()); 58. st.pop();//如果栈顶的运算符优先级大于等于当前运算符 栈顶的运算符被连续弹出 59. } 60. st.push(exp[i]);//当前运算符进栈 61. } 62. else ans.push_back(exp[i]);//4、数字直接进栈 63. 64. } 65. while(st.size()) {ans.push_back(st.top());st.pop();}//5、栈内剩余运算符被连续弹出 66. //for(int i=0;i<ans.size();i++)cout<<ans[i]<<endl; 67. return ans; 68. } 69. int suffix_calc(vector<string> exp)//后缀表达式计算结果 70. { 71. stack<int> num; 72. string ops="+-*/^"; 73. for(int i=0;i<exp.size();i++){ 74. if(ops.find(exp[i])!=string::npos){//是运算符，弹出两个数字运算并入栈 75. int a=num.top();num.pop(); 76. int b=num.top();num.pop(); 77. if(exp[i]=="+") num.push(b+a); 78. else if(exp[i]=="-") num.push(b-a); 79. else if(exp[i]=="*") num.push(b*a); 80. else if(exp[i]=="/") num.push(b/a); 81. else if(exp[i]=="^") num.push(pow(b*1.0,a)); 82. } 83. else {//字符串是数字，转换成整数并入栈 84. num.push(atoi(exp[i].c_str())); 85. } 86. } 87. //cout<<num.top()<<endl; 88. return num.top(); 89. } 90. int main(int argc, char *argv[]) 91. { 92. string st; 93. getline(cin,st);//读取字符串 94. vector<string> vs=scaner(st);//将字符串解析到vector 95. vs=infix_suffix(vs);//中缀表达式转后缀表达式 96. cout<<suffix_calc(vs)<<endl;//输出后缀表达式计算结果 97. return 0; 98. }
