[GDKOI2024 普及组] EX 中缀表达式

赛事要求

2024 年广东省重点中学信息学邀请赛 (GDKOI 2024)

普及组 第二试

2024 年 1 月 7 日

注意事项

1. 严格按照题目所要求的格式进行输入、输出，否则严重影响得分。
2. 题目测试数据有严格的时间限制，超时不得分。
3. C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须是 0。
4. 输入文件格式不用判错；输入输出文件名均已给定，不用键盘输入。
5. 评测环境为 NOI 系列活动标准竞赛环境，编译器版本为 g++ 9.4.0。
6. 若无特殊说明，结果的比较方式为全文比较 (过滤行末空格及文末回车)。
7. 对于 C++ 选手，64 位整数输入输出格式为 %lld。
8. 选手提交的程序源文件必须不大于 100KB。
9. 对于 C++ 语言的编译选项为 -O2 -std=c++14

题目描述

Alice 最近学习了表达式，现在他想写一个属于自己的表达式计算器。

规定：

• 单个数字：由若干数字（至少一个）连续拼接，最后必须跟一个 . 字符（不含引号）。例如：00123. 0. 789. 都是合法的数字。
• 单个操作符：由若干数字连续拼接，最后跟一个字符。
• 操作符的字符：表示该操作符的操作。该字符必须是 +、*、^ 之一，分别表示加法，乘法和乘方。特别约定 0^0=1。 例如：000000789+，123^，如果前面的数值合法，那么它们就都是合法的操作符。
• 操作符的数字：表示该操作符的优先级，优先级的取值是 $[1, n]$ 之间的正整数，数字越大表示优先级越高。
• 对于优先级相同的操作符，题目将给出一个长度为 $n$ 的 $01$ 串 $C$，用于说明对应优先级的操作符之间，是左结合还是右结合。 其中 $0$ 表示左结合，$1$ 表示右结合。 例如 $C=111011$，其中第 $4$ 个字符为 0，表示优先级为 $4$ 的操作符是左结合的。
• 左结合：表示该运算符从左往右计算。下面给出左结合的例子：1.4+2.4^3.4^4. 等价于 ((1.4+2.)4^3.)4^4，其结果与 ((1+2)^3)^4 相同
• 右结合：表示该运算符从右往左运算。下面给出右结合的例子：1.6+2.6^3.6^4. 等价于 1.6+(2.6^(3.6^4.))，其结果与 1+(2^(3^4)) 相同。
• 中缀表达式：

1. 单个数字是合法的中缀表达式。
2. 若 A 是合法的中缀表达式，则 (A) 也是合法的中缀表达式。
3. 若 A、B 均是合法的中缀表达式，c 是合法的单个操作符，则 AcB 也是合法的中缀表达式。
4. 其余情况均不合法。

现在给出一个长度为 $n$ 的 $01$ 串 $C$，用于说明，相同优先级的操作符之间，是左结合还是右结合。

给出一个中缀表达式，判断该表达式是否合法，不合法则输出 error（不包括引号），合法则输出该表达式的值对 $998244353$ 取模的结果。

输入格式

第一行一个正整数 $n$。

第二行一个长度为 $n$ 的 $01$ 串 $C$。

第三行一个字符串 $S$，表示一个中缀表达式。

保证表达式中不会存在空格。

输出格式

若中缀表达式不合法则输出 error，否则输出该表达式的值对 $998244353$ 取模的结果。

样例 #1

样例输入 #1

2
01
1.2+2.1^3.2*4.2^(5.2*6.)2+7.

样例输出 #1

243640717

提示

【样例解释】

243640717 = ((1+2)^(3*(4^((5*6)+7)))) mod 998244353

【数据范围】

特殊性质 1：不会出现 ^ 字符。

特殊性质 2：不会出现 + 和 * 字符。

特殊性质 3：不会出现 ( 和 )。

对于 $8\%$ 的数据，$n = 1$，$1 \leq |S| \leq 100$，且满足特殊性质 $1$ 和特殊性质 $3$。

对于另外 $8\%$ 的数据，$n = 1$，$1 \leq |S| \leq 100$，且满足特殊性质 $1$。

对于另外 $20\%$ 的数据，$n = 1$，$1 \leq |S| \leq 100$，且满足特殊性质 $2$ 和特殊性质 $3$。

对于另外 $24\%$ 的数据，$n = 1$，$1 \leq |S| \leq 1000$,，且满足特殊性质 $2$。

对于 $100\%$ 的数据，$1 \leq n \leq 9$，$1 \leq |S| \leq 10000$。