中缀表达式(a+b)*c*(d-ef) 转成后缀为？_小米集团笔试题

推荐

小海豹

ab+c*def/-*

后缀表达式是波兰逻辑学家卢卡西维奇（Lukasiewicz)发明的一种表示表达式的方法。这种表示方式把运算符写在运算对象的后面，例如，把a+b写成ab+，所以也称为后缀式。这种表示法的优点是根据运算对象和算符的出现次序进行计算，不需要使用括号，也便于用机械实现求值。

编辑于 2015-01-27 20:16:52 回复(5)

之初

中缀表达式转后缀表达式的方法：
1.遇到操作数：直接输出（添加到后缀表达式中）
2.栈为空时，遇到运算符，直接入栈
3.遇到左括号：将其入栈
4.遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，括号不输出。
5.遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈
6.最终将栈中的元素依次出栈，输出。
例如
(a+b)*c*(d-e/f) -> ab+c*def/-*

遇到(: 进栈：

堆栈：(

遇到a:直接输出：
后缀表达式：a
堆栈：(

遇到+:堆栈：(并没有遇见)，所以+入栈
后缀表达式：a

堆栈：(+

遇到b: 直接输出
后缀表达式：ab

堆栈：(+

遇到): 出栈，直到遇见左括号

后缀表达式：ab+

堆栈：空

遇到*: 堆栈中元素为空，进栈

后缀表达式：ab+

堆栈：*

遇到c：直接输出

后缀表达式： ab+c

堆栈：*

遇到*：和堆栈中符号优先级相同，弹出栈中的，将该*压入栈

后缀表达式：ab+c*

堆栈：*

遇到(: 进栈：

后缀表达式：ab+c*

堆栈：*(

遇到d: 直接输出

后缀表达式：ab+c*d

堆栈：*(

遇到-: 入栈

后缀表达式：ab+c*d

堆栈：*(-

遇到e: 直接输出

后缀表达式：ab+c*de

堆栈：*(-

遇到/: 高于-，入栈

后缀表达式：ab+c*de

堆栈：*(-/

遇到f: 直接输出

后缀表达式：ab+c*def

堆栈：*(-/

遇到): 出栈，直到左括号出栈

后缀表达式：ab+c*def/-

堆栈：*

遇到中缀表达式结束：弹出所有的运算符并输出
后缀表达式：ab+c*def/-*
堆栈：空

发表于 2015-09-05 17:10:55 回复(6)

商郡马

ab+cdef/-**和 ab+c*def/-*都是对的吧。

由于c既可以和左边的乘号也可以和右边的乘号先结合，所以有两种答案。

将表达是构建成二叉树也确实有两种可能：

发表于 2015-08-30 16:57:13 回复(6)

renzhichu

ab+c*def/-*

这里我给出一个中缀表达式：a+b*c-(d+e)

第一步：按照运算符的优先级对所有的运算单位加括号：式子变成了：((a+(b*c))-(d+e))

第二步：转换前缀与后缀表达式

前缀：把运算符号移动到对应的括号前面

则变成拉：-( +(a *(bc)) +(de))

把括号去掉：-+a*bc+de 前缀式子出现

后缀：把运算符号移动到对应的括号后面

则变成拉：((a(bc)* )+ (de)+ )-

把括号去掉：abc*+de+- 后缀式子出现

发现没有，前缀式，后缀式是不需要用括号来进行优先级的确定的。

发表于 2015-11-10 18:22:29 回复(2)

百度高级测试开发工程师

就是不服为啥 ab+c*de-f/* 不对（兄弟们把我赞到第一位！！！就是不服）

编辑于 2016-03-05 16:28:34 回复(2)

wcz2023

不小心把答案写成 def/-cab+**了，注意到这样译过来是(d-e/f)*(a+b)*c,而不是 (a+b)*c*(d-e/f)，

所以说顺序很重要！

发表于 2015-09-13 00:00:10 回复(0)

L.K.

ab+c*def/-*

进行中缀转后缀操作，使用符号栈存储遍历过程中遇到的符号。

从左到右遍历中缀表达式，遇到数字直接输出，遇到符号准备将其放入符号栈：

若符号栈为空，直接放入。
若当前符号大于栈顶符号优先级，直接放入。
如果小于等于栈顶符号优先级，将栈顶符号弹出，直到栈顶符号小于当前符号，再将当前符号入栈。
如果当前符号为“（”，直接入栈。
如果当前符号为“）”，依次将符号栈的符号弹出，直到找到“（”。

按此规则进行遍历，最后如果符号栈仍有符号，弹出即可。

编辑于 2015-08-08 13:23:35 回复(0)

我的天呐

博哥来解题

编辑于 2022-05-09 20:33:40 回复(1)

牛客8034813号

根据优先级添加括号，从最内层开始，然后将运算符提到右边的括号的右边，并去掉所有括号

发表于 2017-04-27 20:47:53 回复(0)

MSean

中缀表达式：(a+b)*c*(d-e/f)

后缀表达式：ab+*cdef/-*

后缀表达式又称逆波兰式，将中缀表达式转化为后缀表达式的方法：

把运算符写在运算对象的后面。

感觉这一句就够了，从左到右看中缀表达式，根据其结合顺序，依次把运算符写在运算对象后面，并把括号去掉，往后面顺序输出。

如: a-b 即为 ab- ; ( a * b - c ) 即为 ab*c-

编辑于 2016-08-27 17:22:29 回复(0)

牛客134755号

中缀表达式 =>按优先级加括号=> 运算符移到对应括号后=>去括号=>后缀表达式

(a+b)*c*(d-e/f) => (((a+b)*c)*(d-(e/f))) => (((ab)+c*(d(ef)/)-)* => ab+c*def/-*

发表于 2016-01-18 12:43:45 回复(0)

黏黏糖

待入栈的操作符的优先级 > 栈顶元素

发表于 2017-05-16 11:30:22 回复(0)

大将军豆腐脑好

***吧，减号写成–，就错了

发表于 2017-05-11 07:49:08 回复(0)

_TQC_

一个小技巧：学过编译原理的同学应该容易理解，构造如图二叉树，后序遍历之。

发表于 2017-04-03 16:03:30 回复(0)

wanlanwalan

中缀表达式转后缀表达式的方法：

1.遇到操作数：直接输出（添加到后缀表达式中）

2.栈为空时，遇到运算符，直接入栈

3.遇到左括号：将其入栈

4.遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，括号不输出。

5.遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈

6.最终将栈中的元素依次出栈，输出。

发表于 2017-03-29 10:38:52 回复(0)

天杀包子神

a+b*c
bc要先*然后+a
就会变成

abc*+
变量的顺序是不会变的。

发表于 2017-03-18 15:02:09 回复(0)

dragonaxz

用二叉树做好理解，中缀表达式就是中序遍历，后缀表达式就是同一个二叉树后序遍历

发表于 2016-12-20 13:12:00 回复(0)

牛客143068号

中缀表达式(a+b)*c*(d-e/f) 转成后缀 ab+c*def/-*。

中缀表达式转后缀表达式的方法：
1.遇到操作数：直接输出（添加到后缀表达式中）
2.栈为空时，遇到运算符，直接入栈
3.遇到左括号：将其入栈
4.遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，括号不输出。
5.遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈
6.最终将栈中的元素依次出栈，输出。

发表于 2016-12-14 15:35:03 回复(0)

BrainerGao

简单来说，可以借鉴树的概念，中缀表达式就是相当于树的中序遍历，后缀表达式相当于树的后序遍历。其实也是很方便的，可以试一试。

发表于 2016-05-06 18:29:53 回复(0)

huixieqingchun

 要考虑原表达式的运算符优先级，从而展开成后缀表达式

发表于 2016-04-25 11:40:03 回复(0)

何时明月

中缀表达式转后缀表达式的方法：
1.遇到操作数：直接输出（添加到后缀表达式中）
2.栈为空时，遇到运算符，直接入栈
3.遇到左括号：将其入栈
4.遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，括号不输出。
5.遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈
6.最终将栈中的元素依次出栈，输出。（转载。。）

发表于 2016-04-11 19:48:22 回复(0)

中缀表达式(a+b)c(d-ef) 转成后缀为？

问题信息

热门推荐

相关试题