首页 > 试题广场 >

写出a*(b-c*d)+e-fg*(h+i*j-k)的逆波

[单选题]
写出a*(b-c*d)+e-f/g*(h+i*j-k)的逆波兰表达式。 
  • a(b-c*d)*+e-(f/g(h+i*j-k)*)
  • a(b-(cd*))*+e-(fg/(h+ij*-k)*)
  • a(bcd*-)*+e-(fg/hij*+k-*)
  • abcd*-*e+fg/hij*+k-*-
添加回答
推荐
小小吴头像 小小吴
表达式一般由操作数、运算符组成，例如算术表达式中，通常把运算符放在两个操作数的中间，这称为中缀表达式，如A+B。波兰数学家Jan Lukasiewicz提出了另一种数学表示法，它有两种表示形式：把运算符写在操作数之前，称为波兰表达式或前缀表达式，如+AB；把运算符写在操作数之后，称为逆波兰表达式或后缀表达式，如AB+；

将中缀表达式转换成后缀表达式算法：
1、从左至右扫描中缀表达式。
2、若读取的是操作数，则判断该操作数的类型，并将该操作数存入操作数堆栈
3、若读取的是运算符
  (1) 该运算符为左括号"("，则直接存入运算符堆栈。
  (2) 该运算符为右括号")"，则输出运算符堆栈中的运算符到操作数堆栈，直到遇到左括号为止。
  (3) 该运算符为非括号运算符：
      (a) 若运算符堆栈栈顶的运算符为括号，则直接存入运算符堆栈。
      (b) 若比运算符堆栈栈顶的运算符优先级高或相等，则直接存入运算符堆栈。
      (c) 若比运算符堆栈栈顶的运算符优先级低，则输出栈顶运算符到操作数堆栈，并将当前运算符压入运算符堆栈。
4、当表达式读取完成后运算符堆栈中尚有运算符时，则依序取出运算符到操作数堆栈，直到运算符堆栈为空。


逆波兰表达式求值算法：
1、循环扫描语法单元的项目。
2、如果扫描的项目是操作数，则将其压入操作数堆栈，并扫描下一个项目。
3、如果扫描的项目是一个二元运算符，则对栈的顶上两个操作数执行该运算。
4、如果扫描的项目是一个一元运算符，则对栈的最顶上操作数执行该运算。
5、将运算结果重新压入堆栈。
6、重复步骤2-5，堆栈中即为结果值。

故选D


编辑于 2015-02-02 18:13:30 回复(2)
村东头二大爷头像 村东头二大爷
选D，我的分析和源代码：http://blog.csdn.net/huangpingcai/article/details/73864521
发表于 2017-06-29 09:44:44 回复(0)
Miner_Sty头像 Miner_Sty
根据运算符优先级添加括号。
    a*(b-c*d)+e-f/g*(h+i*j-k)
=  a * (b - (c * d)) + e - (f / g) * (h + (i * j) - k)
=  a * (b - (cd*)) + e - (fg/) * (h + (ij*) - k)
=  a * (bcd*-) + e - (fg/) * ((hij*+) - k)
=  (abcd*-*) + e - (fg/) * (hij*+k-)
=  (abcd*-*e+) - (fg/hij*+k-*)
=  (abcd*-*e+fg/hij*+k-*-)
发表于 2015-09-08 20:37:08 回复(6)
S.Xiao头像 S.Xiao
D

本题可以快速求解，显然逆波兰式中不存在括号，所以必然为D，仔细分析D的表达式为正确表达式。
发表于 2015-01-17 03:08:54 回复(4)
武汉孙一峰头像 武汉孙一峰
可以试着将二叉树构造出来
发表于 2016-08-26 17:03:53 回复(3)
人生还有多少个二十年头像 人生还有多少个二十年
逆波兰表达式(又称为后缀表达式)
波兰表达式（又称为前缀表达式）
而我们中小学接触过的则是中缀表示法。
eg:                 求1和2的积
前缀表达式为：        *12
中缀表达式为：        1*2
后缀表达式为：        12*

题中给出了中缀表达式： a*(b-c*d)+e-f/g*(h+i*j-k)
我们可以把它当做三项，分别用X , Y , Z 代替它们，则
            原表达式为：X+Y-Z
            则其后缀表达式为：XY+Z-
            然后再用后缀表示法来表示每个子项就可以了。
结论：后缀表示法的结尾肯定是中缀表示法最后一个子项的符号， 前缀表示法的开头肯定是中缀表示法最后一个子项的符号
发表于 2016-11-05 13:30:06 回复(0)
牛客334705号头像 牛客334705号
逆波兰表达式没括号，快速选择的话是D。
将中缀表达式装成逆波兰就是中序转后序，可以构造成树，再写出后序遍历序列


发表于 2016-09-17 20:54:06 回复(2)
只有更坑，没有最坑头像 只有更坑，没有最坑
这个是和数的后序遍历一样的吗
发表于 2020-03-07 00:31:54 回复(0)
寒樟桐头像 寒樟桐
我当然是选择屏蔽掉
发表于 2020-09-14 20:20:18 回复(0)
黑闪⚡头像 黑闪⚡
有括号的都排除
发表于 2020-05-09 20:40:27 回复(0)
stezpy头像 stezpy
提供由中缀表达式到后缀表达式的算法

发表于 2019-09-15 11:11:50 回复(0)
跳跳虎还是跳跳鼠头像 跳跳虎还是跳跳鼠
逆波兰表达式，其实就是二叉树的后序遍历，所以先将表达式以中序遍历构建二叉树，然后对二叉树进行后序遍历，得到的序列就是逆波兰表达式

发表于 2019-01-09 23:28:12 回复(0)
秋雨叶落时头像 秋雨叶落时

其实我觉得：abcd-e+fghij+k-/-,即把/放在后边也是对的。

就好比：a+b-c的逆波兰表达式是：abc-+和a+bc-都可以

发表于 2018-08-20 20:36:29 回复(0)
JohnkikiJiang头像 JohnkikiJiang
逆波兰式就是后缀表达式，不存在括号的。
发表于 2018-06-19 10:44:52 回复(0)
edithw头像 edithw
后缀表达式是没有括号的
发表于 2017-10-02 12:46:01 回复(0)
想打架的蜜蜂头像 想打架的蜜蜂
概念清楚就好了，就是运算符写在操作数之后，称为逆波兰表达式或后缀表达式，且没有括号
编辑于 2015-08-31 22:12:01 回复(0)
wikizhu头像 wikizhu
D 无括号
发表于 2015-03-19 19:04:45 回复(0)
提交观点

问题信息

微软 复杂度
来自：算法工程师能力评估
上传者：小小
难度：
17条回答 16900浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号