首页 > 试题广场 >

已知一算数表达式的中缀表达式为 af+(b-cd)e，

[填空题]

已知一算数表达式的中缀表达式为 a*f+(b-c/d)*e，其后缀形式1

查看正确选项

城枫墨凉

这里所谓的前缀，中缀，后缀是根据操作符的位置来定的，如果操作符在操作数前面，则称为前缀表达式，例如“- + 1 × + 2 3 4 5”;如果操作符在操作数之间，则称为中缀表达式，例如

“1+((2+3)×4)-5”;如果操作符在操作数后面，则称为后缀表达式，例如“1 2 3 + 4 × + 5 -”。

虽然中缀表达式符合人类的日常思维习惯，但是计算机在存储中缀表达式时，需要使用树这种数据结构，如果表达式过于复杂，那么树的高度会变得很高，大大增加了时间复杂度和空间复杂度。如果转换成线性结构，那么效率将变得高很多，所以需要将中缀表达式先转换成前缀或者后缀表达式，然后依靠栈这种线性数据结构来进行计算。

前缀表达式又叫波兰表达式，后缀表达式又叫逆波兰表达式。前缀表达式基本没有在商业计算机中使用过，所以现实中用的更多的是后缀表达式。

如何将中缀表达式转化成后缀表达式呢？

利用两个栈S1，S2：其中S1存放操作符，S2存放操作数

从左往右遍历中缀表达式，如果遇到数字，则放入S2中，如果遇到操作符，则放入S1中。在放操作符的时候有一定的规则，如果栈为空或栈顶元素为（，则直接压栈。如果是(，也直接压栈;如果栈顶元素为普通操作符，则比较优先级，如果待压栈的操作符比栈顶操作符优先级高，则直接压栈，否则将S1中的栈顶元素出栈，并压入S2中，再接着比较S1栈顶元素的优先级。如果遇到)，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃。最后将S1中剩余的运算符依次弹出并压入S2，逆序输出S2（从栈底到栈顶）便得到了后缀表达式。（注意：等号的优先级最低，因为要到最后才进行赋值操作）

得到后缀表达式之后，计算就变得方便多了，遇到数字就压栈，遇到操作符的时候，pop出栈顶的两个元素，进行计算后将结果又压入栈中，这样一直下去，直到得到最终结果。

将中缀表达式“a*f+(b-c/d)*e”转换为后缀表达式的过程如下：

扫描到的元素

S2(栈底->栈顶)数字

S1 (栈底->栈顶)操作符

说明

空

数字，直接入栈

S1为空，运算符直接入栈

数字，直接入栈

af*

+比*优先级低

将S1中的栈顶元素出栈，并压入S2中

(

af*

( ,直接入栈

af*b

数字，直接入栈

af*b

+(-

S1栈顶为左括号，运算符直接入栈

af*bc

+(-

数字，直接入栈

af*bc

+(-/

/比-优先级高，则直接压栈

af*bcd

+(-/

数字，直接入栈

)

af*bcd/-

右括号，弹出运算符到s2直至遇到左括号

af*bcd/-

*比+优先级高，则直接压栈

af*bcd/-e

数字，直接入栈

到达最右端

af*bcd/-e*+

空

弹出S1中剩余的运算符

得出结果：af*bcd/-e*+，OK

编辑于 2018-01-09 14:53:28 回复(0)

夏花爱秋叶

* `中缀表达式转为后缀表达式(从左到右扫描)`
* `分为两个栈，结果栈和运算栈，遇到的情况有`
```
1. 如果是操作数(数字、字母)，则进入结果栈
2. 如果是左括号，那么入运算栈；
3. 如果是右括号，那么把运算栈的栈顶元素出栈，入栈到结果栈，知道遇到左括号，遇到左括号后，这一对括号都消灭
4.1 如果是运算符，如果运算栈为空，那么入栈
4.2 如果是运算符，此时运算栈顶运算符不为左括号！！！，且栈里不存在优先级大于或等于该运算符的运算符，则该运算符入栈，
否则大于等于该运算符的其他运算符先出栈再入栈到结果栈
4.3 如果是运算符，此时栈顶运算符是左括号，那么入栈
```

* 首先a是操作数，进结果栈；`结果栈为 a`

* * 是运算符，运算栈空，进运算栈
* f是操作数，进结果栈 `结果栈为 a f`
* +是运算符，但是栈中存在优先级大于等于的*，所以 * 先出栈，然后 * 入运算栈 `结果栈为 a f *`
* (是左括号，入运算栈，`运算栈为 + (`
* b是操作数，入结果栈，`结果栈 a f * b`
* -是运算符，栈顶元素是左括号，所以-入运算栈 `运算栈 + ( -`
* c是操作数，入结果栈， `结果栈 a f * b c`
* /是运算符，运算栈顶元素不是左括号，`运算栈 + ( -`不存在优先级大于等于 / 的元素，所以 / 入运算栈
* d是操作数，d入结果栈，`结果栈 a f * b c d`
* )是右括号，所以运算栈的栈顶元素出栈，知道左括号，入栈后进到结果栈
* 此时运算栈是 `+ ( - /` ，所以结果栈变为 `a f * b c d / -`,运算栈变为 `+`,左右括号消灭了
* 然后*是运算符，运算栈中不存在大于等于的元素，所以入运算栈,运算栈为`+ *`
* e是操作数，e入结果栈，结果栈为`a f * b c d / - e`,
* 扫描结束，所以运算栈全部出栈到结果栈，为 `a f * b c d / - * +`

发表于 2020-03-02 13:36:20 回复(0)

提交观点

问题信息

算法工程师唯品会 2018

来自：唯品会2018校招数据...

上传者：小小

难度：

2条回答 30收藏 1765浏览

已知一算数表达式的中缀表达式为 af+(b-cd)e，

问题信息

热门推荐

相关试题

已知一算数表达式的中缀表达式为 a*f+(b-cd)*e，

问题信息

热门推荐

相关试题

已知一算数表达式的中缀表达式为 af+(b-cd)e，