首页 > 试题广场 >

题目来源于王道论坛 假设栈初始为空,将中缀表

[单选题]
题目来源于王道论坛

假设栈初始为空,将中缀表达式a/b+(c*d-e*f)/g转换为等价的后缀表达式的过程中,当扫描到f时,栈中的元素依次是


  • + ( * -
  • + ( - *
  • / + ( * - *
  • / + - *
推荐

解析:

将中缀表达式转换为后缀表达式的算法思想如下:

从左向右开始扫描中缀表达式;

遇到数字时,加入后缀表达式;

遇到运算符时:

a. 若为‘(’,入栈;

b. 若为‘)’,则依次把栈中的的运算符加入后缀表达式中,直到出现‘(’,从栈中删除‘(’;

c. 若为除括号外的其他运算符,当其优先级高于除 ‘(’ 以外的栈顶运算符时,直接入栈。否则从栈顶开始,依次弹出比当前处理的运算符优先级高和优先级相等的运算符,直到一个比它优先级低的或者遇到了一个左括号为止。

当扫描的中缀表达式结束时,栈中的所有运算符依次出栈加入后缀表达式。

待处理序列

后缀表达式

当前扫描元素

动作

a/b+(c*d-e*f)/g

a

a加入后缀表达式

/b+(c*d-e*f)/g

a

/

/入栈

b+(c*d-e*f)/g

/

a

b

b加入后缀表达式

+(c*d-e*f)/g

/

ab

+

+优先级低于栈顶的/,弹出/

+(c*d-e*f)/g

ab/

+

+入栈

(c*d-e*f)/g

+

ab/

(

( 入栈

c*d-e*f)/g

+(

ab/

c

c加入后缀表达式

*d-e*f)/g

+(

ab/c

*

栈顶为(*入栈

d-e*f)/g

+(*

ab/c

d

d加入后缀表达式

-e*f)/g

+(*

ab/cd

-

-优先级低于栈顶的*,弹出*

-e*f)/g

+(

ab/cd*

-

栈顶为(-入栈

e*f)/g

+(-

ab/cd*

e

e 加入后缀表达式

*f)/g

+(-

ab/cd*e

*

*优先级高于栈顶的-*入栈

续表

待处理序列

后缀表达式

当前扫描元素

动作

f)/g

+(-*

ab/cd*e

f

f加入后缀表达式

)/g

+(-*

ab/cd*ef

)

把栈中(之前的符号加入表达式

/g

+

ab/cd*ef*-

/

/优先级高于栈顶的+/入栈

g

+/

ab/cd*ef*-

g

g加入后缀表达式

+/

ab/cd*ef*-g

扫描完毕,运算符依次退栈加入表达式

ab/cd*ef*-g/+

完成

由此可知,当扫描到f的时候,栈中的元素依次是+(-*,选B

在此,再给出中缀表达式转换为前缀或后缀表达式的手工做法,以上面给出的中缀表达式为例:

第一步:按照运算符的优先级对所有的运算单位加括号。

式子变成了:((a/b)+(((c*d)-(e*f))/g))

第二步:转换为前缀或后缀表达式。

前缀:把运算符号移动到对应的括号前面,则变成了:+(/(ab)/(-(*(cd)*(ef))g))

把括号去掉:+/ab/-*cd*efg前缀式子出现。

后缀:把运算符号移动到对应的括号后面,则变成了:((ab)/(((cd)*(ef)*)-g)/)+

把括号去掉:ab/cd*ef*-g/+ 后缀式子出现。

当题目要求直接求前缀或后缀表达式时,这种方***比上一种快捷得多。

发表于 2018-06-16 11:37:32 回复(7)
总结了前中后缀表达式的特点,以及相互转换的规则及例子:


编辑于 2019-10-21 16:52:19 回复(1)
用二叉树的遍历思想做可以不
发表于 2018-10-30 19:46:12 回复(0)

比较优先级,乘除大于加减,当栈内乘除遇到栈外加减是,先计算栈内加减,把乘号约去了,***🙃🙃

发表于 2018-10-30 14:22:42 回复(0)
完全懵逼啊😖
发表于 2018-10-05 14:43:18 回复(0)
中缀转后缀,从前往后扫描 中缀转前缀,从后往前扫描,最后翻转数组
发表于 2018-08-17 15:57:49 回复(0)