中缀表达式转后缀表达式(逆波兰)
哪些公司问过
答案要点
- 用运算符栈加输出序列实现调度场算法,从左到右扫描中缀表达式
- 操作数直接输出;左括号压栈;右括号弹栈输出到遇左括号为止并丢弃左括号
- 遇运算符先弹出栈顶优先级不低于它的运算符输出,再压入当前运算符
- 正确处理优先级:乘除高于加减,括号最高;扫描结束弹出栈中剩余运算符
- 多位数整体作一个操作数,输出用空格分隔;求值时再扫一遍后缀用栈计算
易错点
- 把多位数拆成单字符处理,导致 101 被当成 1、0、1
- 忽略左右结合性,同级运算符弹栈条件用错
- 右括号处理时忘记丢弃匹配的左括号,或括号不匹配未校验
- 输出不加分隔符,多位操作数连在一起无法区分
面试官常见追问
- 为什么遇到运算符要先弹出优先级不低于它的?
- 怎么处理右结合运算符,比如幂运算?
- 后缀表达式怎么求值?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 栈和队列的区别与应用68 场
- 四则运算表达式求值15 场
- 循环队列(环形缓冲区)的实现14 场
- 最长有效括号12 场
- 滑动窗口最大值与滑动平均滤波12 场
- 有效的括号(栈)11 场
- 实现支持 O(1) 获取最小值的栈9 场
- 单调栈:下一个更大元素与每日温度6 场
- 数据流的中位数(大根堆加小根堆)5 场
- 滑动窗口最大值的单调队列解法4 场