编写C++表达式解析器时如何按运算符优先级拆分表达式构建语法树

拆分的通用可遵循逻辑 #

不需要手动判断运算符前后的拆分边界，严格按照以下递归规则即可覆盖任意复杂表达式的拆分需求：

• 对任意一层待拆分的表达式文本，首先识别所有未被未配对括号包裹的顶层运算符，筛选出其中优先级最低的运算符作为当前层的拆分根节点。
• 若存在多个同最低优先级的运算符，按照对应运算符的结合方向确定拆分位置：左结合运算符取序列中最靠左的位置拆分，右结合运算符取最靠右的位置拆分。
• 将拆分运算符前后的剩余文本，分别作为左子表达式、右子表达式递归执行相同的拆分流程，直到所有单元都拆分为不可再分的原子块为止。
• 被配对括号完全包裹的内容属于特殊原子块，拆分时不需要在括号内部找顶层运算符，而是将括号内的文本单独作为子表达式递归拆分，拆分完成后整体作为单个操作数参与外层的优先级判断。
• 原子块的识别优先级从高到低固定：函数调用、数组下标、链式成员访问 → 字面量、标识符 → 括号包裹的子表达式。

关于乘法运算符拆分的疑问解答 #

你提到的4 * givemeanobj(a & c & e, b, hello(c)).method()场景，完全可以用上述通用规则覆盖，不需要额外判断*号的拆分范围：

1. 先识别当前层的所有最高优先级原子块：4是字面量原子块，givemeanobj(...).method()是函数调用+链式成员访问的原子块，两者的优先级都高于乘法运算符。
2. 乘法运算符*的优先级高于比较类运算符，因此两个相邻原子块会直接作为*的左右操作数，组成一个独立的乘法算术块。
3. 这个乘法块的整体优先级，高于外层的<比较运算符，因此在拆分外层比较逻辑时，这个乘法块会作为<运算符的单个右操作数存在，完全不需要跨远层边界拆分多余内容。

极端复杂用例的拆分流程参考 #

你给出的测试表达式片段拆分时完全按照上述规则执行：

if (test(s[4]) < 4 && b + 3 < r && a!=b && ((c | e) == (g | e)) ||
   r % 7 < 4 * givemeanobj(a & c & e, b, hello(c)).method())

顶层拆分步骤如下：

1. 从整个待拆分的表达式（即if括号内的内容）中，找出所有未被配对括号包裹的顶层运算符，其中优先级最低的是逻辑或||，将其作为整个语法树的根节点：左分支为test(s[4]) < 4 && b + 3 < r && a!=b && ((c | e) == (g | e))，右分支为r % 7 < 4 * givemeanobj(a & c & e, b, hello(c)).method()。
2. 递归拆分左分支：该分支内所有顶层未被包裹的运算符均为逻辑与&&（优先级高于||，但低于算术、比较类运算），按照左结合规则取最靠左的&&作为拆分点，将左侧的test(s[4]) < 4作为左操作数，剩余的右段文本作为新的子表达式递归拆分，直到拆到最内层的比较运算、算术运算、原子块层级。
3. 递归拆分右分支：该分支内优先级最低的顶层运算符是小于号<，将其作为子树的根节点，左操作数为算术块r % 7，右操作数为算术块4 * givemeanobj(...)，两个算术块内部再按照优先级递归拆分即可。

实现注意事项 #

• 拆分流程不需要前置校验表达式合法性：哪怕输入存在语法错误，也可以按照优先级规则完成树结构拆分，后续合法性校验仅需基于拆分完成的树节点类型做匹配检查即可。
• 链式的成员访问、函数调用不需要作为独立运算符拆分，直接归为最高优先级的原子块处理，避免和算术、逻辑运算符的优先级判断产生冲突。

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