首页 > 试题广场 >

当扫描到f时,栈中的元素依次是 ()

[单选题]

假设栈初始为空,将中缀表达式 转换为等价后缀表达式的过程中,当扫描到f时,栈中的元素依次是 ()

  • +(*-
  • +(-*
  • /+(*-*
  • /+-*
基本概念:
在中缀变后缀时,操作数的顺序不会发生变化,只有运算符的顺序可能发生变化。同时又没有括号。所以在转换的过程中,只要碰到操作数,可以直接输出,而遇到运算符和括号进行相应的处理即可。
转换原则如下:
1.从左到右读取一个中序表达式。
2.若读取的是操作数,则直接输出。
3.若读取的是运算符,分三种情况。
A.该运算符为左括号( ,则直接存入堆栈。
B.该运算符为右括号),则输出堆栈中的运算符,直到取出左括号为止。
C.该运算符为非括号运算符,则与堆栈顶端的运算符做优先权比较,若较堆栈顶端运算符高或者相等,则直接存入堆栈;若较堆栈顶端运算符低,则输出堆栈中的运算符。
4.当表达式已经读取完成,而堆栈中尚有运算符时,则依次序取出运算符,直到堆栈为空,由此得到的结果就是中缀表达式转换成的后缀表达式。

接下来是该题解法:
1.首先 / 入栈
2.+入栈,并把/挤出栈 。此时栈中只有/
3.( 入栈。入栈时 级别最高,所以直接入栈。但是入栈后级别最低。此时栈中只有(+
4 。* 级别高于( (不懂的请看上面的基本概念)。 所以*入栈,此时栈中有*(+
5. -入栈,因为-低于*,所以-把*挤出栈,此时栈中有-(+
6.*优先级高于-,所以*直接入。所以最终栈中从上到下为 *-(+ 从下到上为+(-×


编辑于 2017-02-21 18:46:40 回复(6)
总结了前中后缀表达式的特点,以及相互转换的规则及例子:

编辑于 2019-10-21 16:53:08 回复(2)
依次把符号弹入栈  后面的符号比前面的符号优先级低  则把前面的符号弹出栈的 先入栈/ +号比/优先级低  则/弹出栈的 然后弹入左括号 括号优先级最高 必须等到右括号才会出栈   然后弹入*  -号比乘号优先级低  *号弹出栈 然后栈中再弹入*号的
1 /
2 + (
3 + (  *
4 + ( - *
发表于 2016-12-03 15:26:14 回复(1)
一共俩栈,操作数栈和符号栈。
对于符号栈来说,
如果当前符号优先级要小于栈顶元素,那么就弹出栈顶元素及对应的操作数,计算结果入操作数栈,然后再把当前符号压入栈中。就比如栈顶现在是*,当前符号是+,那么就先弹出两个操作数a和b,然后把a*b的结果再压回操作数栈,再把+入符号栈。
如果当前符号优先级要大于栈顶元素,那么就直接符号入栈。就比如栈顶现在是+,当前符号是*,那就直接把*压入符号栈。
回到本题,除了加减乘除还有个左括号,其优先级要大于其他的符号,如果栈顶是*,当前符号是(,那么就压入(,不过这个题还没出这种情况。当遇到)时,不断从符号栈弹出运算符,并弹出操作数依次计算,直到符号栈栈顶是左括号,弹出左括号,并把括号里计算的结果压入操作数栈。


发表于 2016-12-16 09:31:17 回复(0)
注意:扫描到F时
顺序:栈底-->顶。
规则:数字直接输出;
          符号,比较优先级,若是右括号或者优先级不高于栈顶元素的,栈顶元素出栈并输出,当前符号进栈。
例题的后缀表达式:ab/cd*ef*-g/+
发表于 2017-03-29 10:17:46 回复(0)
发表于 2023-02-24 15:26:53 回复(0)
后缀表达式的符号栈中,永远是优先级低的符号在栈底。可直接排除acd。
发表于 2017-02-10 15:14:27 回复(0)
等价过程: 
ab/  +  (cd*  -   ef*)g/
(ab/)  (((cd*)(ef*)-)g/ )+所以答案是b,其实也不太对,求高手解析


发表于 2016-12-02 10:46:34 回复(0)
栈的用法太底层 不宜深入
发表于 2022-04-19 14:57:13 回复(0)
1)中缀改为后缀需要两个栈S1和S2,其中S1存放操作符,S2存放操作数;
2)从左到右遍历中缀表达式,当遇到操作数,则存放在S2中;
3)当遇到操作符则存放在S1中;
4)存放操作符时,如果S1为空,或S1栈顶元素为"(",则直接压栈;
5)存放操作符时,如果S1栈顶为普通操作符,则需要进行优先级比较,若待压栈操作符比栈顶操作符优先级高,则直接压栈,否则(小于或等于栈顶操作符优先级)先将S1中的栈顶操作符出栈,并压入S2,再接着继续比较S1栈顶操作符的优先级;
6)如果遇到操作符“)”,则弹出S1栈顶操作符,并压入S2,知道遇到“(”,并消掉“()”,
7)最后将S1中剩余的运算符依次弹出并压入S2,逆序输出S2(从栈底到栈顶)便得到了后缀表达式。(注意:等号的优先级最低,因为要到最后才进行赋值操作)。
编辑于 2019-09-14 17:30:30 回复(0)
.

发表于 2023-03-28 21:03:39 回复(0)
题目是不是有问题,求解答
发表于 2022-09-22 19:40:20 回复(0)
从左到右依次进栈,**栈的比先入栈的优先级低,则将先入栈的挤出。
发表于 2021-06-04 23:46:39 回复(0)