背景

中缀表达式,运算符在操作数的中间,即一般的表达式;
后缀表达式,运算符在操作数的后面;
前缀表达式,运算符在操作数之前.

下面我们实现由一般的中缀表达式到后缀表达式的转换.

手算

举例说明: a+b*c+(d*e+f)*g

  • 将其按照先乘除后加减以及从左到右的原则添加上括号((a + (b * c)) + (((d * e) + f) * g)),熟练了该步可以省去,添加括号反而增加麻烦.
  • 根据括号由内向外将表达式转换为后缀形式a bc* + de* f+ g* +.

得到最终结果,但此法不适用于计算机.
但我们可以从中看出一些规律,这对设计计算机算法有所裨益.
例如:

  • 操作数之间的相对顺序并未改变.
  • 内层的运算符总是比外层的运算符先输出.
  • a+b*c中*要先运算;而a*b+c...中也是*先运算,但到+时意味着前面的运算已经影响不到后面的运算了(除非有括号),也就是说在没有括号参与的情况下,低运算级(+,-)前面的高运算级(+,-,*,/)可以输出了.
  • 接上条,在括号内部的运算总是优先的,于是我们可以将右括号)视为一个括号运算的结束,那么怎么找到与之对应的左括号呢?我们很自然的想到括号匹配问题中使用的栈.

基于以上几条我们可以设计一个适用于计算机的转换算法.

机算

算法思想:

1
2
3
1. 遇到操作数直接输出;  
2. 遇到左括号'('进栈,直到遇到右括号')'代表该括号内已经运算完毕, 直接一个个输出栈内元素直到匹配到'('或者栈空.  
3. 遇到运算符, 如果是 +,- 则其前面的 +,-,*,/ 已经运算完毕, 全部输出直到栈空或者遇到'('; 如果是 *,/ 则后面可能还有运算, 应该将其先入栈. 这里 +,-,*,/ 也可用优先级表示.

实际运算:

  1. 遇到a,输出.
    输出: a
    栈:
  2. 遇到+,入栈.
    输出: a
    栈: +
  3. 遇到b,输出.
    输出: ab
    栈: +
  4. 遇到*,优先级比栈顶元素高,入栈.
    输出: ab
    栈: +-
  5. 遇到c,输出.
    输出: abc
    栈: +*
  6. 遇到+,优先级比栈顶低,输出栈直到空或’(',最后当前运算符入栈.
    输出: abc*+
    栈: +
  7. 遇到(,入栈.
    输出: abc*+
    栈: +(
  8. 遇到d,输出.
    输出: abc*+d
    栈: +(
  9. 遇到*,栈顶’(',故入栈.
    输出: abc*+d
    栈: +(*
  10. 遇到e,输出.
    输出: abc*+de
    栈: +(*
  11. 遇到+,输出栈直到空或者’(',最后当前运算符入栈.
    输出: abc*+de*
    栈: +(+
  12. 遇到f,输出.
    输出: abc*+de*f
    栈: +(+
  13. 遇到),输出直到匹配到左括号,括号不输出.
    输出: abc*+de*f+
    栈: +
  14. 遇到*,优先级高,入栈.
    输出: abc*+de*f+
    栈: +*
  15. 遇到g,输出.
    输出: abc*+de*f+g
    栈: +*
  16. 遍历完,输出所有栈内元素.
    输出: abc*+de*f+g*+
    栈:

完成,结果为abc*+de*f+g*+

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define up(x) for(int i=0;i<x;i++)
#define rson mid+1,r,rt<<1|1
#define lson l,mid,rt<<1

const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433

int prior(char x){
if (x=='*'||x=='/')return -1;
else return -2;
}

int type_element(char x)
{
    if((x>='0' && x<='9')||(x>='a'&&x<='z')||(x>='A'&&x<='Z'))
    {
        return 1;
    }
    else if(x=='('||x=='{'||x=='[')
    {
        return 2;
    }
    else if(x==')'||x=='}'||x==']'){
        return 3;
    }
    else return prior(x);
}


bool pairElement(char x,char y){
    if((x=='('&&y==')')||(x=='{'&&y=='}')||(x=='['&&y==']'))return true;
    else return false;
}

void verdict(string str)
{
    stack<char> S;
    int lens = str.length();
    up(lens)
    {   int t = type_element(str[i]);
        if(t==1)printf("%c ",str[i]);
        else if(t==2)S.push(str[i]);
        else if(t==3){
            while(!S.empty()){
                char tmp=S.top();
                S.pop();
                if(type_element(tmp)!=2)printf("%c ",tmp);
                if(pairElement(tmp,str[i]))break;
            }
        }
        else {
            while(!S.empty()){
                char tmp=S.top();
                if(type_element(tmp)==2)break;
                if(prior(tmp)>=t){
                    S.pop();
                    printf("%c ",tmp);
                }
                else break;
            }
            S.push(str[i]);
        }
    }
    while(!S.empty())printf("%c ",S.top()),S.pop();

}


int main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(NULL);
    string str;
    cin>>str;
    verdict(str);
    return 0;
}

参考

🔗数据结构——中缀转后缀表达式🔗
🔗中缀表示法-Wikipedia🔗