如何依据SCIM过滤器优先级规则重排字符串中的表达式元素？

你遇到的问题本质是带优先级和括号的表达式解析，最优解决方案是使用调度场算法（Shunting-yard Algorithm）——这是Dijkstra提出的专门用于将中缀表达式转换为后缀表达式（逆波兰式）的算法，完美适配SCIM过滤的优先级规则。

核心步骤实现 #

1. 先做词法拆分（Tokenize）

首先要把原始过滤字符串拆分为可识别的Token，不能用简单的split()，需要逐字符扫描：

• 识别操作数：比如SCIM里的userName eq "foo"这类完整的条件表达式，遇到操作符或括号时截断。
• 识别操作符：NOT、AND、OR（注意SCIM规范大小写不敏感，统一转成大写/小写处理）。
• 识别括号：( 和 )。
• 处理空格：忽略表达式中的空格，避免干扰Token识别。

比如输入A and (B or (C))，拆分后得到Token列表：[A, AND, (, B, OR, (, C, ), )]

2. 用调度场算法生成后缀表达式

按照SCIM的优先级（括号 > NOT > AND > OR），结合算法规则处理Token：

• 初始化一个操作符栈，一个输出队列。
• 遍历每个Token：
  • 操作数：直接加入输出队列。
  • 左括号(：压入操作符栈。
  • 右括号)：不断弹出栈顶操作符到输出队列，直到遇到左括号；弹出左括号但不加入队列（如果栈空还没找到左括号，说明表达式语法错误）。
  • 操作符（NOT/AND/OR）：
    • 当栈不为空，且栈顶不是左括号，且栈顶操作符的优先级高于或等于当前操作符时（注意NOT是单目操作符，优先级高于AND，且为右结合），弹出栈顶到输出队列。
    • 将当前操作符压入栈。
• 遍历完成后，将栈中剩余的所有操作符依次弹出到输出队列。

拿你的例子来说，处理后得到的后缀表达式是：[C, B, OR, A, AND]，对应的运算逻辑就是先执行B OR C，再执行A AND 结果，完全符合原表达式的优先级。

3. 基于后缀表达式构建表达式树或求值

得到后缀表达式后，构建二叉树就变得简单：

• 遍历后缀表达式，遇到操作数就创建节点压入栈。
• 遇到操作符时，弹出栈顶节点作为右子节点（单目操作符如NOT只弹出一个），再弹出一个作为左子节点，创建操作符节点后压入栈。
• 遍历结束后，栈中剩余的节点就是表达式树的根节点。

关键注意点 #

• 单目操作符NOT的处理：调度场算法默认处理双目操作符，需要单独适配——比如设定NOT的优先级高于AND，且为右结合（即遇到连续NOT时，从右往左运算）。
• 语法校验：在Tokenize和算法处理过程中，要加入语法校验（比如括号不匹配、操作符前后没有合法操作数等），避免非法表达式导致崩溃。

内容的提问来源于stack exchange，提问作者jimmayhem