后缀表达式

题意

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

数字后面用 . 表示这个操作数结束；
@ 表示整个表达式结束；
运算符只包含 + - * /；
除法按 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])

复杂度

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

总结

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

目录

题意

思路

Python 知识

代码

复杂度

总结