【例1-2】后缀表达式的值

题目描述

从键盘读入一行后缀表达式，运算数是 0-9 组成的非负整数，运算符是 + - * /，以 @ 结束。运算数之间用空格隔开，但运算符可以连写（如 +*-）；长度小于 250，中间值与结果绝对值 $<2^{64}$ ，除法保证整除，输入保证合法。样例输入：16 9 4 3 +*-@，样例输出：-47（对应中缀 $16 - 9 \times (4 + 3)$ ）。

思路

逐字符扫描：数字位用 number = number*10 + 位 边扫边拼多位数并设 reading 标志防止未读完的数提前入栈；遇到非数字位先结算可能存在的运算数，然后正面枚举四种之一才归约（弹出右、弹出左，算完压回），其它字符一律当分隔符；@ 之后不看，扫描结束对 reading 收尾入栈。复杂度 $O(L)$ 。

参考代码

Python 版：

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51#!/usr/bin/env python3
# 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-09-30 05:43
# update_at: 2026-09-30 05:49

import sys

END = '@'       # 表达式结束标志，它之后的内容（换行、多余空白）一律不看
OPERATORS = '+-*/'  # 全部运算符；够用来判定「这个非数字字符该不该触发一次归约」


def evaluate(expr: str) -> int:
    """扫描后缀表达式字符串求值：数字入栈；遇运算符弹出右、左操作数，算完把结果压回。

    只有运算数之间保证有空格，运算符可以连续出现（如 `+*-`），所以只能按字符扫描，
    不能先 split() 再分 token。多位数靠 `number * 10 + 位值` 逐位拼装。
    """
    stack: list[int] = []
    number = 0       # 正在拼装的运算数
    reading = False  # 是否正处于一个运算数内部：用于区分「数字 0」和「还没开始读数」
    for ch in expr:
        if '0' <= ch <= '9':  # 只认 ASCII 数字位，等价于题面「只含有 0-9 组成的运算数」
            number = number * 10 + int(ch)
            reading = True
        elif reading:  # 遇到任何非数字字符都表示当前运算数结束，先把它入栈
            stack.append(number)
            number, reading = 0, False
        if ch not in OPERATORS:  # 空格、换行、制表符等其余字符只当分隔符
            continue
        right = stack.pop()  # 后缀表达式中右操作数入栈更晚，所以先弹出
        left = stack.pop()
        stack.append(
            left + right if ch == '+'
            else left - right if ch == '-'
            else left * right if ch == '*'
            else left // right  # 题面保证除法整除，整除时 // 与向零截断结果一致
        )
    if reading:  # `@` 紧跟运算数时可以省掉末尾空格，这里补一次收尾
        stack.append(number)
    return stack[-1]  # 合法表达式求值完栈里恰好剩一个数，它就是答案


def solve() -> None:
    source = sys.stdin.buffer.read().decode()
    print(evaluate(source[: source.index(END)]))  # 只取 @ 之前的表达式部分


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75/**
 * 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-05 10:01
 * update_at: 2026-10-05 10:01
 */

// main.cpp：后缀表达式求值。逐字符扫描，运算符按四字母十交集弹出两个压回栈；
// 不能用 split() 切 token，因为运算符可以连写（如 `+*-`）。

#include <cstdio>
#include <cstdlib>
#include <cstring>

typedef long long ll;

const char END_MARK = '@';          // 表达式结束标志，它之后的内容一律忽略
const char *OPERATORS = "+-*/";     // 四种运算符；正面枚举才能避免把其它字符当成运算符多弹栈

ll stack_buf[300]; // 表达式长度 < 250，中间结果最多约 125 个；题面约束 < 2^64，超出 ll 范围时会发生溢出，按 OJ 习惯用 ll 表示
int top;            // 栈顶指针：stack_buf[0..top-1] 是当前栈，栈空时 top == 0

// 把已经拼好的数字压栈：仅当运算符与运算符之间隔了数字时调用
void push_number(ll &number, int &reading) {
    if (reading) {
        stack_buf[top++] = number;
        number = 0;
        reading = 0;
    }
}

// 遇运算符：先弹右、后弹左，算完压回；调用前必须保证两操作数都已经在栈上
void apply_operator(char op) {
    ll right = stack_buf[--top]; // 栈顶是右操作数（后入栈）
    ll left  = stack_buf[--top]; // 下面是左操作数（先入栈）
    ll res;
    if (op == '+')      res = left + right;
    else if (op == '-') res = left - right;
    else if (op == '*') res = left * right;
    else                res = left / right; // 题面保证整除，结果无歧义
    stack_buf[top++] = res;
}

int is_digit(char ch) { return '0' <= ch && ch <= '9'; }   // 只认 ASCII 数字位，避免 Unicode 数字陷阱
int is_operator(char ch) { return std::strchr(OPERATORS, ch) != NULL; } // 正面枚举运算符

int main() {
    // 一行读完整个表达式（可能含空格 / 换行 / `@` 之后的内容）
    char buf[512];
    if (!std::fgets(buf, sizeof buf, stdin)) return 0;

    top = 0;
    ll number = 0;       // 正在拼装的运算数
    int reading = 0;     // 是否正处于一个运算数内部：区分「读到的是 0」与「还没开始读数」

    for (int i = 0; buf[i] != '\0'; ++i) {
        char ch = buf[i];
        if (ch == END_MARK) break;                  // `@` 之后的内容一律不看
        if (is_digit(ch)) {                         // 数字位：边扫边拼多位数
            number = number * 10 + (ch - '0');
            reading = 1;
            continue;
        }
        // 非数字位：先把可能存在的「待入栈运算数」结算掉（顺序必须先于运算符处理）
        push_number(number, reading);
        if (is_operator(ch)) apply_operator(ch);    // 只对四种运算符归约；空格/制表符/换行当分隔符
        // 其它字符（空格等）一律跳过，不影响结果
    }
    // `@` 可能紧跟运算数（如 `12@`），这里补一次收尾入栈
    push_number(number, reading);

    std::printf("%lld\n", stack_buf[0]);
    return 0;
}

【例1-2】后缀表达式的值

目录

题目描述

思路

参考代码