假设栈初始为空,将中缀表达式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
/
/入栈
b+(c*d-e*f)/g
b
b加入后缀表达式
+(c*d-e*f)/g
ab
+
+优先级低于栈顶的/,弹出/
ab/
+入栈
(c*d-e*f)/g
(
( 入栈
c*d-e*f)/g
+(
c
c加入后缀表达式
*d-e*f)/g
ab/c
*
栈顶为(,*入栈
d-e*f)/g
+(*
d
d加入后缀表达式
-e*f)/g
ab/cd
-
-优先级低于栈顶的*,弹出*
ab/cd*
栈顶为(,-入栈
e*f)/g
+(-
e
e 加入后缀表达式
*f)/g
ab/cd*e
*优先级高于栈顶的-,*入栈
续表
f)/g
+(-*
f
f加入后缀表达式
)/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/+ 后缀式子出现。
当题目要求直接求前缀或后缀表达式时,这种方***比上一种快捷得多。
比较优先级,乘除大于加减,当栈内乘除遇到栈外加减是,先计算栈内加减,把乘号约去了,***🙃🙃
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题
解析:
将中缀表达式转换为后缀表达式的算法思想如下:
从左向右开始扫描中缀表达式;
遇到数字时,加入后缀表达式;
遇到运算符时:
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/+ 后缀式子出现。
当题目要求直接求前缀或后缀表达式时,这种方***比上一种快捷得多。