64 lines
2.3 KiB
C++
64 lines
2.3 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
|
||
const int N = 100010, mod = 10007;
|
||
|
||
/*
|
||
整体理解为一个表达式二叉树，每个节点是一个运算完的结果。
|
||
本题中要模拟的数字，在表达式二叉树中，其实是叶子节点，
|
||
stack<vector<int>> num; 中，入栈的每一个对象，其实都是一个只有两个
|
||
长度的小整数数组，分别是a[0],a[1],分别代表是0的方案数量，是1的方案数量
|
||
对于叶子节点而言，可以是1也可以是0，方案数量都是1种。
|
||
所以下面的代码中会有num.push({1, 1});
|
||
*/
|
||
stack<char> op; // 运算符栈
|
||
stack<vector<int>> num; // 得0的方案数num[0],得1的方案数num[1]
|
||
// 运算符优化级
|
||
unordered_map<char, int> h = {{'+', 1}, {'*', 2}};
|
||
|
||
void eval() {
|
||
// 运算符
|
||
auto c = op.top();
|
||
op.pop();
|
||
|
||
// 两个数，本题的弹出顺序不重要，事实上是先b后a,因为是栈
|
||
auto b = num.top();
|
||
num.pop();
|
||
auto a = num.top();
|
||
num.pop();
|
||
|
||
// ⊕ 运算符
|
||
if (c == '+')
|
||
num.push({a[0] * b[0] % mod,
|
||
(a[0] * b[1] + a[1] * b[0] + a[1] * b[1]) % mod});
|
||
else // × 运算符
|
||
num.push({(a[0] * b[0] + a[1] * b[0] + a[0] * b[1]) % mod,
|
||
a[1] * b[1] % mod});
|
||
}
|
||
|
||
int main() {
|
||
int n;
|
||
string expr;
|
||
cin >> n >> expr;
|
||
|
||
// 第一个位置,需要放上一个数字，可以是0也可以是1，方案数都是1
|
||
num.push({1, 1});
|
||
for (auto c : expr) { // 读入表达式
|
||
if (c == '(')
|
||
op.push(c); // 左括号入栈
|
||
else if (c == '+' || c == '*') {
|
||
// 通过while循环，把栈内的表达式先计算出结果,再将当前操作符入栈
|
||
while (op.size() && h[op.top()] >= h[c]) eval();
|
||
op.push(c);
|
||
// 处理完操作符，需要模拟下面的数字是0，还是1
|
||
num.push({1, 1}); // 无论是0还是1，方案数都是1,这样所有情况都考虑到了
|
||
} else { // 右括号
|
||
while (op.top() != '(') eval();
|
||
op.pop();
|
||
}
|
||
}
|
||
// 1*1-0 类似这样的表达式，op栈中应该有*-两种符号，需要再次弹栈计算
|
||
while (op.size()) eval();
|
||
cout << num.top()[0] << endl;
|
||
return 0;
|
||
} |