# 整数运算器

**出题人解法：** 用运算符栈将中缀式转成后缀式，再用数值栈求值。**Codex（GPT-6）贡献：** 明确并实现可移植的 32 位环绕规则，补齐边界验证与正确性说明。

## 中缀转后缀

维护“下一个位置是否期待操作数”。开头、左括号后、运算符后期待操作数，此时正负号是一元；数字或右括号后不期待操作数，此时正负号是二元。用内部记号区分两种正负号。

数字直接写入后缀序列。左括号入栈；右括号让栈顶运算符依次出栈，直到丢弃匹配的左括号。读到运算符时，先弹出所有优先级更高的栈顶运算符；优先级相同时，仅当当前运算符左结合才弹出。最后把当前运算符压栈。读完输入后清空运算符栈。

此规则把较紧的子表达式放在外层运算之前。同级左结合先输出左边运算，同级右结合保留右边运算先执行，所以产生的后缀序列恰好保持题目的语法树次序。

## 数值栈与整数语义

读到数字就压栈。一元运算弹出一个操作数；二元运算先弹出右操作数，再弹出左操作数。结果重新压栈。后缀序列保证遇到运算符时，其子表达式已计算完毕；据此归纳，每个栈值都正确。

用 `uint32_t` 保存位模式。加减和取反保留低 32 位，乘法先扩展到 `uint64_t` 再截取。需要比较、除法或余数时，将位模式转成 64 位有符号值：若最高位为一，减去 $2^{32}$ .于是最小负数除以负一也能在 64 位中安全求出，再转回低 32 位。

除数为零立即报告错误。题中没有短路运算符，任一子表达式出错都会使整体出错，因此提前结束不会漏掉合法结果。不要用 C++ 的有符号溢出模拟环绕；有符号溢出不提供所需语义。

## 复杂度与方案选择

每个字符最多入栈、出栈各一次，时间和空间均为 $O(\ell)$ .两阶段都迭代实现，可处理深括号和长一元链。直接在运算符出栈时求值也是同一栈算法的融合写法；递归语法分析则需要额外处理深递归风险。保留出题人的两阶段解法为首选，不另列只是组织方式不同的程序。

## 实现与验证

[标准程序](std.cpp)、[生成器](tests/generate.py)、[测试配方](tests/plan.json)。

参考环境中标准程序最慢中位数 0.030337 秒，峰值 5.52 MiB，校准时限 0.5 秒。每例独立运行五次。

[评测环境](../../../docs/评测环境与性能.md)与[逐次时间和哈希](../../../docs/benchmark-R31.json)。数值只适用于所记录环境，迁移评测机需重新校准。