题目重点：用arity与compute注册表驱动栈求值，保持操作数顺序并定义错误语义。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练token为整数文字或已注册operator，注册表只接收受信回调；本文不执行任意用户上传代码。
- operator提供非负arity，数值文字不得与operator名冲突；未知token、栈下溢和多余结果报错。
- 除法可选本文truncate-toward-zero helper，正式题舍入合同未公开。
解题路线
- Parser只负责token分类，Registry负责Operator(arity,compute)，Evaluator负责栈与错误。新增operator不改一串if/else，只加注册项；arity允许0常量、1一元、2二元和更多参数。
- 拿栈尾arity个参数时保持从左到右顺序，如tokens=[8,3,-]要compute(8,3)，不能逆序弹成3-8。arity=0单独处理，Python[-0:]是整个列表，不应清空已有栈。
- 合法表达式每次operator消费arity项并产生1项，最终必须恰一值。少项是下溢，多值表示表达式未完整组合；任何时候都不能默默忽略token。
- 计算错误需定义事务边界：示例一次性eval，回调报错让整个调用失败。长寿命stack服务若要继续，须先计算成功再提交栈变化或回滚原栈。
- 用户自定义语义不等于允许任意代码执行。受信插件可直接callable；不受信代码要隔离、超时/资源限制、可用类型和副作用权限，不能用eval执行token。
- truncate除法用abs整数除再符号修正，避免Python//负数向下取整与int(a/b)大整数浮点精度问题。
手动走一遍
训练注册-为arity2、square为arity1，8 3 - square得25；0元constant插入一个值而不能擦除旧stack；-7 3 /按训练truncate得-2。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from dataclasses import dataclass
from typing import Callable
@dataclass(frozen=True)
class Operator:
arity:int
compute:Callable
def evaluate(tokens,operators):
stack=[]
for token in tokens:
if token in operators:
operation=operators[token]
if operation.arity < 0 or len(stack) < operation.arity:
raise ValueError("invalid arity or stack underflow")
args=stack[-operation.arity:] if operation.arity else []
if operation.arity:del stack[-operation.arity:]
stack.append(operation.compute(*args))
else:
try:stack.append(int(token))
except ValueError:raise ValueError("unknown token") from None
if len(stack)!=1:raise ValueError("expression must leave exactly one result")
return stack[0]
def truncate_divide(a,b):
if b==0:raise ZeroDivisionError("division by zero")
magnitude=abs(a)//abs(b)
return -magnitude if (a<0)!=(b<0) else magnitude
复杂度
N token基础遍历O(N+Σarity)，空间O(N)最坏；自定义compute成本和大整数运算另算，不能对任意回调承诺O(1)。
易错点与追问
容易失分的边界
- 二元参数逆序。
- arity0切片误清stack。
- 注册表开放eval任意代码。
- Python//被误当截断到0。
继续深挖
- 不同返回类型怎样做type checking？
- compute报错后stack能否恢复？
- 动态注册与并发eval怎样固定版本？
