前往 算竞题解 分类 || 前往 算竞模板 分类

花絮 - 为什么写这篇题解

今天是 23 年 10 月 7 日，数据结构课上讲栈，其中讲到了后缀表达式，但我惊奇的发现我竟然不会处理这个问题。

想起来这个问题我其实在去年 10 月遇到，那是刚刚大一开学，然后当时学了很久都没有学会，最后使用 python 的 eval 函数水过去了。之后 … 就把这件事忘了，现在回想起来，这个问题确实有很高深的东西。

听完老师讲完这节课，课后找了这道题，然后写了这篇题解。

后面我会讲到，后缀表达式实质上就是对树的后序遍历，而这棵树则是一棵笛卡尔树（一种索引满足二叉搜索树性质、值满足堆性质、唯一确定的树），但在代码实现中我们之所以看不到任何树的影子，是因为笛卡尔树的建树过程通常使用单调栈维护，而这棵笛卡尔树的后序遍历可以同时完成。这一个小小的栈，不仅是单调栈，还是笛卡尔树。

原题链接

洛谷 P1449 后缀表达式

洛谷 P1175 表达式的转换

简明题意

我们平常使用的算数表达式都是中缀表达式，而在计算机中对表达式求值都是先将其转换为后缀表达式，然后对后缀表达式只需从左往右求值即可。现在你需要编写程序模拟这个过程。该题中表达式仅包含 + - * / ^ 五种运算，另外还有括号。

举例中缀表达式 8-(3+2*6)/5+4 的后缀表达式为 8 3 2 6 * + 5 / - 4 +。其每步计算过程为：

1
2
3
4
5
6
8 3 2 6 * + 5 / - 4 +
8 3 12 + 5 / - 4 +
8 15 5 / - 4 +
8 3 - 4 +
5 4 +
9

需要特别注意的是，+ - * / 都是向左结合的，而 ^ 是向右结合的。例如：1-2+3 = (1-2)+3 = 2 后缀为 1 2 - 3 +，2^2^3 = 2^(2^3) = 256 后缀为 2 2 3 ^ ^ 。

解题思路

已知后缀表达式求值

已知后缀表达式求值的最好解决方案就是使用栈，但是这道题不用，因为题目的输出规模是 n2n^2 的，我们可以使用 O(n2)O(n^2) 的解法处理这个问题，同时这样做方便输出，这里不赘述这种做法，可以直接参考后面的代码。

这里介绍使用栈的 O(n)O(n) 解法，上面已经给了链接 洛谷 P1449 后缀表达式，但这里不给出代码。

当从左往右遍历后缀表达式，只需将所有数依次压栈；当遇到运算符时，从栈中弹出两数，执行对应运算后将结果重新压栈。这样保证了所有运算符计算的都是其前面最近的两个数，满足后缀表达式的意义。

已知中缀表达式求后缀表达式

已知中缀表达式求后缀表达式相对于前者难理解很多，这对于初学者事实上并不友好。数据结构课上很少听老师讲课，但这个知识点认真听了，其实并没有提出中缀表达式转后缀表达式为什么这么做。

事实上，想要理解后缀表达式，最好需要有 笛卡尔树、单调栈（笛卡尔树 的前置） 的前置知识。

依然以上面的中缀表达式 8-(3+2*6)/5+4 为例，其后缀表达式为 8 3 2 6 * + 5 / - 4 +，我们现在更加直观的将其描绘为树的形式。可以看到这棵树的中序遍历就是 8 - 3 + 2 * 6 / 5 + 4 （括号消失了），后序遍历就是 8 3 2 6 * + 5 / - 4 +。

我们定义在该树中优先系数的概念，数值具有最高优先级 ∞\infty，括号定义为追加优先系数。这句话的意思是，如果 + 的优先系数为 11，括号的附加优先系数为 XX（大于其他所有运算符），则在括号中的 + 具有优先系数 X+1X+1，这里将其表示 (+)。类似地， (((*))) 具有优先系数 3X+23X+2。

按照这样的规定，这棵树的索引满足二叉搜索树性质（即树的中序遍历与原表达式一致），优先系数满足堆的性质，这是一棵笛卡尔树。

如果学习过笛卡尔树的都知道，笛卡尔树的建树过程即维护一个单调栈，而其单调栈的弹出顺序即为该树的后序遍历。在这个问题中，我们只需要维护一个按优先系数升序的单调栈，然后顺序记录其弹出顺序即可。不过值得一提的是，由于数值和括号在优先系数的定义中的特殊性，对其进行特殊处理，反而可以简化代码。另外注意处理相同优先级的输出顺序。

​对数值的特殊处理： 由于数值应当是 int 类型的，而运算符应当是 char 类型的，将数值强制压栈处理相对麻烦，我们特殊处理这个问题。由于数值具有最高优先系数，且数值不能相邻，压栈后一定立即出栈，因此直接输出即可，不必压栈。

​对括号的特殊处理： 前面提到括号具有附加优先系数，那么最直接的做法是维护一个运算符前有多少个未匹配的括号，即为当前运算符的附加优先系数。但由于被括号附加的区间一定是连续的，我们可以优化它。

  • 首先明确附加优先系数不等时，可以直接判定两符号优先系数的大小。因为附加优先系数要求大于其他所有运算符。
  • 当遇到 ( 时将其压栈，并将其优先系数记作 −∞-\infty。因为到下一个 ) 前所有运算符附加优先系数都大于最近一个 ( 前的所有运算符。
  • 当遇到 ) 时依次出栈，直到弹出最近的 (。因为该符号后一个运算符附加优先系数一定小于这对 () 之间的所有符号。注意 ( 出栈时不输出，因为它在栈中的作用是辅助符号。

洛谷 P1175 代码

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
// P1175 表达式的转换
// Module Version 230418
// Powered by GreatLiangpi
#ifdef ONLINE_JUDGE
#define TEST 1  // Test Switch
#else
// #define TEST 1
#define LOCAL 1  // Debug Switch
#endif
#ifndef LOCAL
#define TEST 1
#endif
#include <bits/stdc++.h>
#define int int64_t
#ifdef TEST
// #pragma GCC optimize(3, "Ofast", "inline")  // Optimization Switch
#define endl '\n'
#endif
#ifdef LOCAL
#define endl " **\n"
#endif
#define tomax(x, y) x = max(x, (y))
#define tomin(x, y) x = min(x, (y))
using namespace std;
#ifdef TEST
const int MAX = 200005;
#else
#ifdef LOCAL
const int MAX = 105;
#endif
#endif
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1000000007;
int call_count = 0;

class Opt {
   private:
    // 获取优先级
    int getval() const {
        switch (opt) {
            case '(':
                return 0;
            case '+':
                return 1;
            case '-':
                return 1;
            case '*':
                return 2;
            case '/':
                return 2;
            case '^':
                return 3;
            default:
                return -1;
        }
    }

   public:
    char opt;  // 运算符

    Opt(char c) : opt(c) {}

    friend bool operator>=(const Opt &x, const Opt &y) {
        int xx = x.getval(), yy = y.getval();
        if (xx != yy) return xx > yy;
        if (x.opt == '^') return false;  // 特殊处理 ^ 的向右结合
        return true;
    }
};

class Ele {
   public:
    bool type;  // 是否为运算符
    union {
        int val;
        char opt;
    } u;

    friend ostream &operator<<(ostream &cout, const Ele &x) {
        if (x.type)
            return cout << x.u.opt;
        return cout << x.u.val;
    }
};

int pow(int x, int y) {
    int res = 1;
    for (int i = 0; i < y; i++) {
        res *= x;
    }
    return res;
}

void solve() {
    vector<Ele> suffix;

    {
        string s;
        cin >> s;
        s += '$';
        int i = 0;
        stack<Opt> stk;
        while (i < s.size())
            if (isdigit(s[i])) {
                int x = 0;
                while (isdigit(s[i])) {
                    x = x * 10 + s[i] - '0';
                    suffix.push_back({false, x});
                    i++;
                }
            } else {
                char c = s[i++];
                switch (c) {
                    case '(':
                        stk.push('(');
                        break;
                    case ')':
                        while (stk.top().opt != '(') {
                            suffix.push_back({true, stk.top().opt});
                            stk.pop();
                        }
                        stk.pop();
                        break;
                    default:
                        while (not stk.empty() and stk.top() >= c) {
                            suffix.push_back({true, stk.top().opt});
                            stk.pop();
                        }
                        stk.push(c);
                        break;
                }
            }
    }

    {
        for (const Ele &ele : suffix)
            cout << ele << ' ';
        cout << endl;
        while (suffix.size() > 1) {
            int i = 2;
            while (not suffix[i].type)
                i++;
            int x = suffix[i - 2].u.val;
            int y = suffix[i - 1].u.val;
            int c = suffix[i].u.opt;
            suffix.erase(suffix.begin() + i - 1, suffix.begin() + i + 1);
            switch (c) {
                case '+':
                    x = x + y;
                    break;
                case '-':
                    x = x - y;
                    break;
                case '*':
                    x = x * y;
                    break;
                case '/':
                    x = x / y;
                    break;
                case '^':
                    x = pow(x, y);
                    break;
            }
            suffix[i - 2].u.val = x;
            for (const Ele &ele : suffix)
                cout << ele << ' ';
            cout << endl;
        }
    }
}

int32_t main() {
#ifdef TEST
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
#endif
#ifdef LOCAL
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    clock_t start_time = clock();
#endif
    cout << fixed << setprecision(2);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

#ifdef LOCAL
    cout << "Used " << call_count << " Function Calls." << endl;
    cout << "Used " << (int)(clock() - start_time) << " Microseconds of Time." << endl;
#endif
    return 0;
}