中缀表达式转后缀

admin

输入一个常见的中缀表达式，把它转成后缀表达式，简单起见，表达式中只含有大写字母和运算符+ - *  / ^等
比如输入（A+B*C）/D
输出 ABC*+D/

admin

这是堆栈应用的一个典型题目，因为四则远算的优先度的问题，先算括号里面的，再算乘除，最后算加减，所以我们不能简单粗暴的直接读入表达式，将运算符放在字母的后面，必须考虑优先度。而这个优先度的比较一般的做法是使用堆栈：在字符串中读到运算符的时候（它还在堆栈外面）将它与栈内栈顶的运算符比较优先度，
若小于，按照运算规则，弹出栈内栈顶的运算符，
或者等于，按照从左到右的规则也应该是弹出栈内栈顶的运算符，(有些运算相同级别可不是自左向右的呢，比如乘方，但是我们这里先不考虑)
若小于，则进入堆栈等待。
当然还有很多的细节，比如括号的处理，表达式开始和结尾的处理等


基本做法是：
1、在运算符栈的顶部先放入符号@，当@被弹出的时候表示计算结束；
2、读入字符，若是字母，则压入到字母栈；（其实是没有必要的，直接输出也可以）
3、若是运算符，则比较它与运算符栈栈顶的运算符的优先度，若<=，则弹出字母栈的两个字母进行运算，若>，则进栈等待，
    这里要特殊处理左右括号，对于左括号，无条件入栈，但是假设他的优先度最低，任何后面进去的符号都比他高，要进栈去等待处理，右括号的话，则依次弹出字母栈和算符栈里面的，直到碰到左括号为止。所以堆栈里面是不会有右括号的。
4、字符串处理完毕，将所有栈里面的数据依次弹出。

技巧：
做一个运算符优先度表，假设@符号优先度低为0,左括号优先度为1，+-的优先度为2，*/为3，^为4。这里还有个隐患（^是右结合，所以可能还需要两个有限度表，栈内的和栈外的）

admin

完整的程序如下，使用了c++内置的stack

1. ///中缀表达式转后缀表达式
   
2. #include <bits/stdc++.h>
   
3. using namespace std;
   
4. string sm,sp;
   
5. stack <char> ss;
   
6. int i,top;
   
7. char ch;
   
8. int p(char ch)   ///运算符优先度
   
9. {
   
10.         int  i;
    
11.         if (ch=='^') i=4;
    
12.         else if ((ch=='*') || (ch=='/')) i=3;
    
13.         else if ((ch=='+') || (ch=='-')) i=2;
    
14.         else if (ch=='(')  i=1;
    
15.         else if (ch=='@') i=1;
    
16.         return i;
    
17. }
    
18. 
    
19. 
    
20. int main()
    
21. {
    
22. 
    
23.         ss.push('@');// 放一个@在里面做标记
    
24.         sp="";
    
25.         cin>>sm;
    
26.         for (i=0; i<=sm.size()-1; i++)
    
27.                 {
    
28.                         ch=sm[i];
    
29.                         if (ch>='A' && ch<='Z') sp=sp+ch;   ///不是运算符直接输出
    
30.                         else if ((ch=='+')||(ch=='-')||(ch=='*')||(ch=='/')||(ch=='^'))
    
31.                                 {
    
32.                                         while (p(ch)<=p(ss.top()))  ///不高于栈顶运算符的优先度则栈顶元素弹出
    
33.                                                 {
    
34.                                                         sp=sp+ss.top();
    
35.                                                         ss.pop();
    
36.                                                 }
    
37.                                         ss.push(ch);   ///否则入栈
    
38.                                 }
    
39.                         else if (ch=='(')   ///左括号无条件入栈
    
40.                                 ss.push(ch);
    
41.                         else if (ch=')')  ///右括号的处理
    
42.                                 {
    
43.                                         while (ss.top()!='(')
    
44.                                                 {
    
45.                                                         sp=sp+ss.top();
    
46.                                                         ss.pop();
    
47.                                                 }
    
48.                                         ss.pop();/// 左括号也弹出去
    
49.                                 }
    
50.                 }
    
51.         while (ss.top()!='@')  /// 最后的依次弹出
    
52.                 {
    
53.                         sp=sp+ss.top();
    
54.                         ss.pop();
    
55.                 }
    
56.         cout<<sp;
    
57. }
    
58. /*
    
59. A
    
60. A+B
    
61. A+B*C
    
62. (A+B*C+D/(E-F))*(W+T+X)-(R+V*(I+(J-K)*L)-M)
    
63. */

复制代码