题目内容

系统中日志采集模块支持用户配置日志过滤规则。为了避免每次匹配都重新解析规则，需要开发一个规则解析器。

给定一个日志规则字符串，实现一个函数，把规则转换成逆波兰表达式（RPN，即后缀表达式）。

日志关键字（操作数）只能是以下 5 个字符串，必须完全一致，包括大小写，规则保证不会出现其它关键字：

• ERROR
• NETWORK
• TIMEOUT
• DISK
• CPU

操作符只有以下 3 种；AND、OR 同级时从左到右结合，NOT 按右结合处理：

规则中可能包含括号，用于显式改变结合顺序，保证括号成对出现且嵌套正确：

• 左括号 (：进入新的运算层级；
• 右括号 )：结束当前运算层级。

输入格式

输入只有一行，是一条规则字符串 rule（不含首尾引号），例如：

ERROR AND (NETWORK OR TIMEOUT)

规则字符串满足：

1. $1 \le |rule| \le 1000$，其中 $|rule|$ 为字符串总长度；
2. 括号嵌套深度不超过 $10$；
3. 空格可能连续出现；
4. 操作符和关键字大小写敏感；
5. 输入规则保证语法正确。

输出格式

输出只有一行，为转换后的 RPN：按后缀表达式顺序输出各个单词（操作数与操作符），单词之间用一个半角空格分隔，行末换行。

输出中不要带引号、逗号或方括号。例如 ERROR AND NETWORK 的输出是：

ERROR NETWORK AND

数据范围

• 规则字符串长度：$1 \le |rule| \le 1000$；
• 括号嵌套深度：$\le 10$；
• 操作数个数、操作符个数由规则长度决定，输入保证语法正确。

示例 1

输入

ERROR AND NETWORK

输出

ERROR NETWORK AND

说明

ERROR、NETWORK 是 AND 的两个运算对象，先按顺序写出两个操作数，再把 AND 放到后面，得到 ERROR NETWORK AND。

示例 2

输入

ERROR AND (NETWORK OR TIMEOUT)

输出

ERROR NETWORK TIMEOUT OR AND

说明

括号使 NETWORK OR TIMEOUT 先结合成一组，括号内展开为 NETWORK TIMEOUT OR；外层再与 ERROR 做 AND，最终得到 ERROR NETWORK TIMEOUT OR AND。

示例 3（单操作数）

输入

DISK

输出

DISK

一个操作数不需要任何操作符，直接输出它本身。

关于 NOT 与结合性

• NOT 是一元前缀操作符，优先级最高，只作用于紧跟在其后的一个操作数，或紧跟在其后的一整个括号表达式。
• AND 的优先级高于 OR；AND、OR 同级时从左到右结合。
• NOT 连续出现时按右结合处理，例如 NOT NOT ERROR 等价于 NOT (NOT ERROR)，输出为 ERROR NOT NOT。

例如 NOT ERROR OR TIMEOUT 中，NOT 只作用于 ERROR，不会把后面的 TIMEOUT 也吞进去，因此输出为 ERROR NOT TIMEOUT OR；而 NOT (ERROR OR TIMEOUT) 中 NOT 作用于整个括号，输出为 ERROR TIMEOUT OR NOT。