学习目标
- 用运算符栈实现中缀表达式转后缀表达式。
- 正确处理
* /高于+ -、同级左结合与圆括号。 - 拒绝相邻操作数、缺少操作数和未匹配括号。
前置知识与环境
建议先学习第 2 章栈与队列。使用 ISO C++17；开始前可在本目录运行 make doctor。
任务
操作数直接加入结果；左括号入栈，右括号使运算符弹出至对应左括号；新运算符要先弹出栈顶优先级不低于自身的运算符。这让 a-b-c 转成 ab-c-。读到不合法字符或语法错误时输出 ERROR。
输入格式
一行不含空格、长度 1..200000 的表达式；操作数是单个 ASCII 字母（A-Z、a-z）或数字（0-9），运算符仅有二元 + - * /，允许圆括号。不接受多位数、隐式乘法、一元正负号或空括号；无需计算数值。
输出格式
合法时输出不含空格的后缀表达式并换行；非法时只输出 ERROR。
样例 a+b*c 转换为 abc*+：先计算 b*c，再把结果与 a 相加。(a+b)*c 则得到 ab+c*。
数据范围与限制
- 输入规模不超过
200000，除题面另有说明外整数使用 64 位有符号范围。 - 标准输出只保留题目要求的结果；调试信息写入标准错误。
- 目标算法应为线性或摊还线性时间，辅助空间不超过
O(n)。
边界与验收重点
- 单个操作数合法；
a+、a(b)、ab、a++b和()非法。 a-b-c与a/b*c检查同优先级的左结合。- 右括号无对应左括号、扫描结束左括号未关闭时输出
ERROR。
如何验证
powershell
make doctor
make run
make score未安装 Make 时，在仓库根目录运行：
powershell
pnpm lab:validate -- labs/chapter-02/exercise/E-02-11-infix-to-postfix
pnpm lab:run -- labs/chapter-02/exercise/E-02-11-infix-to-postfix
pnpm lab:score -- labs/chapter-02/exercise/E-02-11-infix-to-postfix思考与复盘
- 处理第二个
-时为何要先弹出第一个-？ - 为什么
a(b)必须判错？
思考题参考
- 减法左结合：
a-b-c表示(a-b)-c，后缀为ab-c-。 - 题目不允许隐式乘法，右侧
(前还缺少一个显式二元运算符。
题解
点击查看题解
思路与不变量
使用输出字符串保存已经确定顺序的操作数和运算符，使用运算符栈暂存尚不能输出的运算符。扫描时维护 expectOperand：为真时只能读操作数或左括号，为假时只能读运算符或右括号。栈中除左括号外始终按待处理优先级排列。
算法步骤
- 操作数直接追加到输出；左括号入栈；
- 读到运算符时，弹出栈顶所有优先级不低于当前运算符的同层运算符，再压入当前运算符；
- 读到右括号时弹栈至对应左括号，找不到左括号则非法；
- 扫描结束后若仍在等待操作数或栈中有未关闭左括号，输出
ERROR，否则弹出剩余运算符。
正确性说明
优先级不低于当前运算符的栈顶运算符必须先计算，左结合性因此得到保证；左括号隔离了括号内外的运算符。每个操作数按原顺序输出，每个运算符在所有更高或同级的左侧运算符处理后输出，所以最终字符串满足后缀表达式的计算顺序。
复杂度分析
- 时间复杂度：
O(|s|)，每个字符及运算符最多入栈、出栈一次； - 额外空间：
O(|s|)，包括输出字符串和运算符栈。
边界注意
a(b)、ab、a++b等违反操作数/运算符交替规则的表达式必须拒绝；- 右括号不能出现在等待操作数的状态，空括号
()也因此非法； - 扫描结束时要继续检查栈内是否残留左括号。