无行终止符的Shunting Yard算法：如何基于操作元数终止解析？

这是扩展Shunting Yard算法时非常典型的痛点——尤其是当表达式不是独占一行，还得和其他语句混在一起解析的时候，判断什么时候该停、什么时候是语法错误确实需要结合运算符元数来精准处理。结合你的需求，我整理了一套可落地的思路和实现细节：

1. 先维护一个「表达式完整性状态」 #

我们需要实时跟踪当前解析进度是否构成了可独立求值的合法单元，结合运算符元数，这个状态主要看两个维度：

• 当前是否处于「等待操作数」的状态（比如刚写完二元运算符、刚打开左括号）
• 已解析结构是否满足所有运算符的元数要求（比如二元运算符必须左右都有操作数，一元运算符必须有右侧操作数）

举个直观的例子：

• 解析10后，我们得到一个独立操作数，此时状态是「完整表达式」——没有未满足的运算符需求，随时可以终止解析。
• 解析10+后，状态是「等待右操作数」——二元+还缺右侧操作数，这时如果遇到非表达式的语句Token（比如赋值号=、关键字if），就必须触发语法错误。

2. 用Token边界区分「表达式延续」和「终止信号」 #

因为语言里还有其他语句，我们得明确哪些Token属于表达式的合法后续，哪些是终止解析的信号：

• 合法后续Token：操作数（数值、变量）、左括号(、一元运算符（比如负号-，元数是区分它和二元减号的关键）
• 终止信号：非表达式元素，比如赋值运算符=、逗号,、关键字return/if、匹配完成的右括号)等

当遇到终止信号时，立刻做状态检查：

• 如果状态是「完整表达式」：终止解析，输出最终的逆波兰式（比如10+20*30会输出[10,20,30,*,+]）
• 如果状态是「不完整」（比如等待操作数、有未闭合的括号、有未满足元数的运算符）：直接抛出「表达式不完整」的语法错误

3. 结合元数处理歧义运算符（比如一元/二元-） #

这是核心细节，元数直接决定了我们对后续Token的预期：

• 当解析到-时，先判断元数：如果当前处于「等待操作数」状态（比如表达式开头、刚遇到二元运算符、刚遇到左括号），它就是一元运算符（元数1），后续必须有操作数；否则是二元运算符（元数2），此时已经有左操作数，需要右操作数。
• 比如解析10-20：-是二元，左操作数10已存在，解析完20后状态完整；如果解析10-后遇到终止信号，直接报错。
• 再比如解析-10：-是一元，解析完10后状态完整；如果只解析-就遇到终止信号，触发报错。

4. 核心逻辑伪代码示例 #

用伪代码梳理关键步骤，方便你落地实现：

# 初始化状态与数据结构
operator_stack = []
output_queue = []
current_state = "等待操作数"  # 可选值：等待操作数 / 等待运算符/终止符
bracket_depth = 0

# 遍历Token流，遇到非表达式Token时跳出
for token in token_stream:
    if token是操作数（数值/变量）:
        output_queue.append(token)
        current_state = "等待运算符/终止符"
    elif token == "(":
        operator_stack.append(token)
        bracket_depth += 1
        current_state = "等待操作数"
    elif token == ")":
        bracket_depth -= 1
        if bracket_depth < 0:
            raise SyntaxError("未匹配的右括号")
        # 弹出运算符直到遇到左括号
        while operator_stack and operator_stack[-1] != "(":
            output_queue.append(operator_stack.pop())
        operator_stack.pop()  # 弹出左括号，不加入输出队列
        current_state = "等待运算符/终止符"
    elif token in ["+", "*", "-"]:
        # 根据当前状态判断运算符元数
        if current_state == "等待操作数":
            arity = 1  # 一元运算符
        else:
            arity = 2  # 二元运算符
        # 标准Shunting Yard的优先级/关联性处理
        while operator_stack and operator_stack[-1] != "(" and (
            (运算符优先级[operator_stack[-1]] > 运算符优先级[token]) or
            (运算符优先级[operator_stack[-1]] == 运算符优先级[token] and token是左关联)
        ):
            output_queue.append(operator_stack.pop())
        operator_stack.append( (token, arity) )  # 标记元数存入栈
        current_state = "等待操作数"
    else:
        # 遇到非表达式Token，触发终止检查
        break

# 处理栈中剩余运算符
while operator_stack:
    top_op = operator_stack.pop()
    if top_op == "(":
        raise SyntaxError("未闭合的左括号")
    output_queue.append(top_op[0])  # 取出运算符本身

# 最终状态检查
if current_state == "等待操作数" or bracket_depth > 0:
    raise SyntaxError("表达式不完整")
else:
    return output_queue

5. 测试用例验证 #

• 案例1：10 → 解析后状态完整，输出[10]
• 案例2：10+20*30 → 处理完运算符栈后输出[10,20,30,*,+]
• 案例3：10+ → 终止时状态为「等待操作数」，触发报错
• 案例4：(10+20 → 终止时括号深度不为0，触发「未闭合的左括号」报错

内容的提问来源于stack exchange，提问作者Eric '3ToedSloth'