[NOIP 2013 普及组] 表达式求值

题意

给定一个只包含数字、+、* 的表达式。

按正常优先级“先乘后加”计算它的值，并输出对 10000 取模后的结果。

思路

先看最容易想到的做法：把表达式拆成数字和运算符，再先把所有乘法处理掉，最后把剩下的项全部相加。

这个版本比较直观：

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#include <bits/stdc++.h>
using namespace std;

const int mod = 10000;

string s;
vector<long long> nums;
vector<char> ops;

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

    cin >> s;

    long long num = 0;
    for (char c : s) {
        if (isdigit(c)) {
            num = num * 10 + (c - '0');
        } else {
            nums.push_back(num);
            ops.push_back(c);
            num = 0;
        }
    }
    nums.push_back(num);

    vector<long long> nums2;
    vector<char> ops2;
    nums2.push_back(nums[0] % mod);

    for (int i = 0; i < (int) ops.size(); i++) {
        if (ops[i] == '*') {
            nums2.back() = nums2.back() * (nums[i + 1] % mod) % mod;
        } else {
            ops2.push_back('+');
            nums2.push_back(nums[i + 1] % mod);
        }
    }

    long long ans = 0;
    for (long long x : nums2) {
        ans = (ans + x) % mod;
    }

    cout << ans % mod << '\n';
    return 0;
}

但这题其实不需要完整表达式求值器。

因为只有两种运算：

+ 只负责分段；
* 只发生在段内。

所以整个式子可以看成“若干个乘积段的和”。

例如：

text

11+2*3*4+5*6

本质上就是：

text

1(1) + (2*3*4) + (5*6)

于是可以一边扫描，一边维护：

num：当前正在读的数字
cur：当前乘积段的值
ans：前面所有完整乘积段的和
last_op：上一运算符

当一个数字读完时：

如果前一个运算符是 *，就把它乘进当前乘积段；
否则说明前一个乘积段已经结束，先把旧 cur 加到 ans，再用这个数字开启新段。

最后别忘了把最后一个乘积段再加进去。

代码

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#include <bits/stdc++.h>
using namespace std;

const int mod = 10000;

string s;

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

    cin >> s;

    long long ans = 0;
    long long cur = 0;
    long long num = 0;
    char last_op = '+';

    for (int i = 0; i <= (int) s.size(); i++) {
        if (i < (int) s.size() && isdigit(s[i])) {
            num = (num * 10 + (s[i] - '0')) % mod;
        } else {
            if (last_op == '*') {
                cur = cur * num % mod;
            } else {
                ans = (ans + cur) % mod;
                cur = num;
            }

            if (i < (int) s.size()) {
                last_op = s[i];
            }
            num = 0;
        }
    }

    ans = (ans + cur) % mod;
    cout << ans % mod << '\n';
    return 0;
}

后缀表达式解法

上面的做法是专门为“只有加和乘”设计的。如果换成任意优先级的运算符，可以走更通用的路线：先把中缀表达式转成后缀表达式，再从左到右扫一遍后缀完成求值。这也是 rbook 里中缀转后缀一节介绍的调度场算法。

这条路线分成三步：

词法分析：把表达式切成 token。本题的运算数可能有多位，必须先切成完整的数字串，否则 123 会被当成 1、2、3 三个操作数。
中缀转后缀：数字 token 直接追加到结果；运算符入栈前，先把栈顶所有优先级不低于它的运算符弹出。因为本题同级从左到右算，所以用的是“优先级相同也弹栈”。
后缀求值：遇到数字入栈，遇到运算符就弹出栈顶两个数（先弹出的是右操作数）算完再压回去。

每一步都只扫描一遍，所以时间、空间都是 $O(n)$ ；常数比加号分段法大，但思路可以直接迁移到更复杂的表达式求值题上。

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
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/**
 * 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-03 16:10
 * update_at: 2026-10-03 17:05
 */
// main-user.cpp：P1981 表达式求值的另一种写法，走「中缀转后缀 + 扫一遍后缀求值」。
// 这条路线不利用“只有 + 和 *”的特殊结构，换成任意优先级的运算符也能套用；
// 代价是要把表达式切成 token 并存一份后缀，常数比 main.cpp 的加号分段法大。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 运算符最多 1e5 个，切出来的 token 最多 2 * 1e5 + 1 个
const ll MAXL = 200005;
const ll mod = 10000;  // 题目要求只输出最后 4 位

string s;                  // 输入的中缀表达式

string token[MAXL];        // 词法分析结果：数字串或运算符，下标从 1 开始
ll token_cnt;

string postfix[MAXL];      // 后缀表达式，仍然按 token 存（下标从 1 开始）
ll postfix_cnt;

string op_stack[MAXL];     // 调度场算法的运算符栈
ll value_stack[MAXL];      // 求值栈，存放还没有参与运算的操作数

// 判断是不是运算符（本题只有加和乘）
bool is_op(char ch) {
    return ch == '+' || ch == '*';
}

// 判断一个 token 是不是数字串
bool is_number(const string &t) {
    return t[0] >= '0' && t[0] <= '9';
}

// 运算符优先级：'*' 高于 '+'。本题同级从左到右算，所以优先级相等时也要弹栈
ll priority_of(const string &op) {
    if (op == "*") {
        return 2;
    }
    return 1;
}

// 第一步：词法分析。逐字符扫描，把表达式切成数字串和单个运算符。
// 必须先把多位数字看成一个 token，否则后面的转换会把它拆成一个个数字。
void read_tokens() {
    token_cnt = 0;

    for (ll i = 0; i < (ll)s.size();) {
        if (is_op(s[i])) {
            token[++token_cnt] = s.substr(i, 1);
            i++;
        } else {
            ll j = i;
            while (j < (ll)s.size() && !is_op(s[j])) {
                j++;
            }
            token[++token_cnt] = s.substr(i, j - i);
            i = j;
        }
    }
}

// 第二步：调度场算法，中缀表达式 -> 后缀表达式。
// 数字 token 直接追加到结果里；运算符入栈前，先把栈顶那些“应该先算”的弹出来，
// 栈里剩下的就是还没轮到它计算的运算符。
void infix_to_postfix() {
    ll op_top = 0;
    postfix_cnt = 0;

    for (ll i = 1; i <= token_cnt; i++) {
        if (is_number(token[i])) {
            postfix[++postfix_cnt] = token[i];
        } else {
            while (op_top > 0 && priority_of(op_stack[op_top]) >= priority_of(token[i])) {
                postfix[++postfix_cnt] = op_stack[op_top--];
            }
            op_stack[++op_top] = token[i];
        }
    }

    while (op_top > 0) {
        postfix[++postfix_cnt] = op_stack[op_top--];
    }
}

// 把数字串转成数值，边读边对 10000 取模（题目只要求最后 4 位，不必用高精度）
ll string_to_num(const string &t) {
    ll num = 0;
    for (ll i = 0; i < (ll)t.size(); i++) {
        num = (num * 10 + (t[i] - '0')) % mod;
    }
    return num;
}

// 第三步：从左到右扫描后缀表达式求值。
// 后缀里没有括号，运算符出现的顺序就是真正的计算顺序：
// 遇到数字就入栈，遇到运算符就弹出栈顶两个数（先弹出的是右操作数）算完再压回去。
ll evaluate_postfix() {
    ll top = 0;

    for (ll i = 1; i <= postfix_cnt; i++) {
        if (is_number(postfix[i])) {
            value_stack[++top] = string_to_num(postfix[i]);
        } else {
            ll right_num = value_stack[top--];
            ll left_num = value_stack[top--];

            if (postfix[i] == "*") {
                value_stack[++top] = left_num * right_num % mod;
            } else {
                value_stack[++top] = (left_num + right_num) % mod;
            }
        }
    }

    return value_stack[top];
}

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

    cin >> s;

    read_tokens();
    infix_to_postfix();
    ll answer = evaluate_postfix();

    // 取模后的数直接按整数输出，前导 0 不会被打出来
    cout << answer << '\n';
    return 0;
}

复杂度

时间复杂度： $O(n)$
空间复杂度： $O(1)$

总结

这题的关键不是栈，而是看出表达式结构已经被简化到了“加号分段、段内连乘”。

一旦完成这个转化，顺着字符串扫描一遍就够了。

[NOIP 2013 普及组] 表达式求值

目录

题意

思路

代码

后缀表达式解法

复杂度

总结