把表达式按加号切成若干乘积段，边扫描边维护当前乘积段与前面各段之和即可。
OJ: luogu
题目 ID: P1981
难度:普及-
标签:模拟字符串noip
日期: 2026-06-18 15:35
题意
给定一个只包含数字、+、* 的表达式。
按正常优先级“先乘后加”计算它的值，并输出对 10000 取模后的结果。
思路
先看最容易想到的做法：把表达式拆成数字和运算符，再先把所有乘法处理掉，最后把剩下的项全部相加。
这个版本比较直观：
cpp
#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
1+2*3*4+5*6本质上就是：
text
(1) + (2*3*4) + (5*6)于是可以一边扫描，一边维护：
num：当前正在读的数字cur：当前乘积段的值ans：前面所有完整乘积段的和last_op：上一运算符
当一个数字读完时：
- 如果前一个运算符是
*，就把它乘进当前乘积段； - 否则说明前一个乘积段已经结束，先把旧
cur加到ans，再用这个数字开启新段。
最后别忘了把最后一个乘积段再加进去。
代码
cpp
#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;
}复杂度
- 时间复杂度：
- 空间复杂度：
总结
这题的关键不是栈，而是看出表达式结构已经被简化到了“加号分段、段内连乘”。
一旦完成这个转化，顺着字符串扫描一遍就够了。