表达式求值(中缀表达式转换为后缀表达式)

                                  表达式求值

 (番外)对栈与队列不是很理解的宝宝欢迎看一下这里---------->https://blog.csdn.net/qq_38193883/article/details/93158778

 -------一个表达式由操作数(亦称运算对象)、操作符(亦称运算符)和分界符组成。------ 

 算术表达式有三种表示:

  1. 中缀(infix)表示      : - <操作数> <操作符> <操作数>,如A+B;
  2. 前缀(prefix)表示    :- <操作符> <操作数> <操作数>,如+AB;
  3. 后缀(postfix)表示  :- <操作数> <操作数> <操作符>,如AB+;                                                                                               

         eg:      中缀表达式  :   a + b*(c-d) - e/f
                    后缀表达式  :   a b c d - * + e f / -
----表达式中相邻两个操作符的计算次序为:----✨ (小童鞋们都晓得哦~打脸打脸……^v^)
              a)优先级高的先计算;
              b)优先级相同的自左向右计算;
              c) 当使用括号时从最内层括号开始计算。
  中缀表达式计算时,需要同时使用两个栈辅助求值;
      后缀表达式求值,则只需要一个栈,相对简单-些。

思路:

前缀表达式的计算涉及的两个栈相辅相成,整个过程需要一个字符一个字符判断:

  1. 若是操作数:直接压栈
  2. 若是操作符:需判断当前操作符与栈顶的操作符谁的优先级高,如果当前运算符优先级高,压栈。反之,栈顶操作符出栈,相应的操作数栈依次弹出两个元素进行相应的操作,注意:后弹出的(操作符)先弹出的。例如,操作数栈为ABCD,操作符栈顶为*,这时读入-,很明显*此时是老大,应该不理 -,先计算 *,因此需要将*出栈,相应的依次弹出D、C进行C-D结果记为r1,将r1压入操作数栈,再用刚刚的-与新的操作符栈顶比较。                                                                                                                                              

中缀表达式程序设计思路(宝宝们可以先看下我这个表格,有疑问的地方看下下面的备注,最好自己在草纸上比划比划~):

为了更好的理解,这里针对“ A+B*(C-D)-E/F”具体阐述

A+B*(C-D)-E/F#
步骤 读取 操作数栈(栈底--->栈顶) 操作符栈 判别条件 相应操作
1   (先初始化为空) (先初始化并且放一个#)   两个栈的初始化
2 A   #   A 进数栈
3 + A # + > # + 进符栈
4 B A # +   B 进数栈
5 * A B # + * > + *  进符栈
6 ( A B # + * ( >  * ( 进符栈
7 C A B # + * (   C 进数栈
8 - A B C # + * ( - > ( - 进符栈
9 D A B C # + * ( -  

D 进数栈

10 ) A B C D # + * ( - ) < - -需出栈,D、C出栈,r1=C-D,r1进数栈
11   A B CD r1 # + * ( ) = ( (退栈,相当于消括号
12  - A B r1 # + * - < * * 出栈 r1、B出栈,r2=*r1,r2进数栈
13   A  r2 # +  - < + + 出栈,r2,A出栈,r3=A+r2,r3入数栈
14   r3 # - > #  - 入栈
15 E r3 # -   E 进数栈
16 / r3 E # -  / >- /  进符栈
17 F r3 E # - /   F 进数栈
18 # r3 E F # - / # < / / 出栈,F、E出栈,r4=E/F,r4进数栈
19   r3 r4 # - # < - -出栈,r4、r3出栈,r5=r3-r4,r5进数栈
20   r5 # # = # #出栈,程序结束,r5即所求表达式的值

                                      温柔可爱的周星星给出了通俗的解释
第一步: 初始化操作符栈(放进去一个#)
第二步: 读取字符A,压入操作数栈
第三步: 读取符号'+',而+的运算优先级>'#',暂时把+压栈而不能直接运算(防止后面有更高优先级操作符)
第四步: 读取字符B,压栈,
第五步: 读取符号'*',由于*的优先级大于当前栈顶元素'+',继续压栈
第六步: 读取符号'(',优先级大于当前栈顶元素'*',继续压栈
第七步: 读取符号C压栈
第八步: 读取操作符'-',需要注意的是(进栈后优先级变低,所以此时-的优先级要远大于栈内'(',继续压栈
第九步: 读取字符D,压栈
第十步: 读取操作符')',栈外(内)的右括号的优先级超低(高),因此'-' > ')',此时需出栈计算,D.C依次pop,'-'也pop,计算C-D(这里记为r1)后再将结果r1压栈
第十一步: ')'与栈内的'('优先级相同,栈顶左括号出栈
第十二步: 读取符号'-',优先级小于栈顶的'*',需出栈计算,r1,B出栈,*出栈,计算结果r2=B*r1压栈
第十三步: 符号'-'与新栈顶'+'相比是同级运算,但栈内的+优先于栈外的-,所以'-'  <  '+',仍需要出栈计算,r2,A依次出栈,+出栈,计算结果r3=r2+A,然后r3进栈
第十四步: 符号'-' > '#'需进栈
第十五步: 读取E压栈
第十六步: 读取符号'/',优先级大于栈顶'-',仍需进栈
第十七步: 读取F压栈
第十八步: 读取#,优先级小于栈顶 '/',出栈计算,F,E依次出栈,计算结果r4=E/F,r4进栈
第十九步: #优先级依然小于新栈顶'-',出栈计算,r4,r3依次出栈,计算结果r5=r3-r4,r5压栈
第二十步: #优先级等于#,出栈。r5出栈即表达式的值

如果哪位呆萌的宝宝实在不理解各个运算符的优先级,请往下看:

             那么这里本可爱再给出一个表:需要思考的是若栈外刚读取的运算符如果与栈顶运算符同级时怎么办呢?当然是栈内优先级高啦,人家先读的,而且在表达式中在前面,比如加减,谁在前先算谁呀~,紧接着再思考,(在栈外时 优先级是最高的,一旦入栈内,便不如加减运算了,同理,)在栈外优先级超低,但是一旦入栈,那就不得了,优先级咔咔滴~,Why?

运算符栈内外优先级综合表(超牛)
操作符 # ^ *  /  % + -
isp(栈内) 0 1 7 5 3 8
icp(栈外) 0 8 6 4 2 1

搞清楚这个以后,具体的代码实现戳这里——>https://blog.csdn.net/qq_38193883/article/details/93464781

正经致谢:------------->

表达式求值(中缀表达式转换为后缀表达式)_第1张图片

 

你可能感兴趣的