后缀表达式

题意

给出一个后缀表达式。表达式中：

数字后面用 . 表示这个操作数结束；
@ 表示整个表达式结束；
运算符只包含 + - * /；
除法按 C++ 整数除法规则向 0 取整。

求表达式的值。

思路

后缀表达式的好处是：不需要考虑括号和优先级，只需要从左到右处理。

先看一个直接模拟版：

cpp

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// brute.cpp：小数据朴素解，直接按后缀表达式从左到右模拟。
#include <bits/stdc++.h>
using namespace std;

vector<long long> st;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    int i = 0;
    while (i < (int)s.size() && s[i] != '@') {
        if ('0' <= s[i] && s[i] <= '9') {
            long long x = 0;
            while (i < (int)s.size() && '0' <= s[i] && s[i] <= '9') {
                x = x * 10 + (s[i] - '0');
                i++;
            }
            st.push_back(x);
            if (i < (int)s.size() && s[i] == '.') {
                i++;
            }
            continue;
        }

        long long b = st.back();
        st.pop_back();
        long long a = st.back();
        st.pop_back();
        if (s[i] == '+') {
            st.push_back(a + b);
        } else if (s[i] == '-') {
            st.push_back(a - b);
        } else if (s[i] == '*') {
            st.push_back(a * b);
        } else {
            st.push_back(a / b);
        }
        i++;
    }

    cout << st.back() << '\n';
    return 0;
}

核心规则只有两类：

读到一个完整数字，就把它压入栈；
读到一个运算符，就弹出栈顶两个数，先弹出的是右操作数，后弹出的是左操作数，算完后把结果压回栈。

例如遇到 5 2 - 时，应计算 5 - 2，而不是 2 - 5。所以减法和除法尤其要注意左右顺序。

正式代码一边扫描字符串，一边把连续数字拼成整数；遇到 . 时说明数字结束，压栈；遇到运算符时完成一次计算；遇到 @ 结束。

Python 知识

Python 列表的 append/pop 正好实现栈顶压入与弹出。
连续数字先收集到字符列表，遇到 . 后用 int("".join(digits)) 转成整数，再 clear() 复用列表。
Python 的 // 是向负无穷取整，不等于题目要求的向零取整；代码用绝对值整除后恢复符号。
/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：字符串逐字符扫描与拼接。
/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：频繁字符串拼接应先收集再 join。

代码

python

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
31expression = input().strip()
stack = []
digits = []


def divide_toward_zero(left, right):
    sign = -1 if (left < 0) != (right < 0) else 1
    return sign * (abs(left) // abs(right))


for character in expression:
    if character.isdigit():
        digits.append(character)
    elif character == ".":
        stack.append(int("".join(digits)))
        digits.clear()
    elif character == "@":
        break
    else:
        right = stack.pop()
        left = stack.pop()
        if character == "+":
            stack.append(left + right)
        elif character == "-":
            stack.append(left - right)
        elif character == "*":
            stack.append(left * right)
        else:
            stack.append(divide_toward_zero(left, right))

print(stack[-1])

STL 写法

C++ 里这道题正好是 stack 的主场：读到一个数就 push 进栈，读到一个运算符就 top + pop 两次取出右操作数和左操作数，算完再把结果 push 回去，最后栈顶就是答案。和上面 brute.cpp 拿 vector 的 push_back / pop_back 当栈用相比，stack 只开放栈顶这一端，接口更少、更贴题；但 pop() 不返回被删掉的元素，取值必须先用 top() 读、再 pop() 删。

对应的 cppbook 章节：stack：最后放入，最先取出

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 00:49
 * update_at: 2026-10-07 01:03
 */
// 这是 STL 写法：操作数直接放进 stack<ll>，读到数字压栈，读到运算符弹出两个操作数算完再压回。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

stack<ll> num_stack; // 操作数栈，栈顶是最近读入的那个操作数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    ll number = 0; // 正在拼的数字，遇到 '.' 时说明这个操作数读完
    ll len = s.size();

    for (ll i = 0; i < len; i++) {
        char ch = s[i];
        if ('0' <= ch && ch <= '9') {
            number = number * 10 + (ch - '0'); // 逐位拼成整数
        } else if (ch == '.') {
            // 数字以 '.' 结尾，把它压入栈顶
            num_stack.push(number);
            number = 0;
        } else if (ch == '@') {
            break; // '@' 表示整个表达式结束
        } else {
            // 先弹出的是右操作数，后弹出的才是左操作数
            ll right = num_stack.top();
            num_stack.pop();
            ll left = num_stack.top();
            num_stack.pop();

            if (ch == '+') {
                num_stack.push(left + right);
            } else if (ch == '-') {
                num_stack.push(left - right);
            } else if (ch == '*') {
                num_stack.push(left * right);
            } else {
                num_stack.push(left / right); // 题目保证除数不为 0，C++ 除法向 0 取整
            }
        }
    }

    // 表达式处理完，栈里只剩一个数，栈顶就是答案
    cout << num_stack.top() << '\n';

    return 0;
}

复杂度

时间复杂度： $O(|s|)$
空间复杂度： $O(|s|)$

总结

后缀表达式求值是栈的经典应用。看到数字入栈，看到运算符弹两个数计算，再把结果压回去。

目录

题意

思路

Python 知识

代码

STL 写法

复杂度

总结