五分钟小知识之什么是后缀表达式

快来打我* 2022-01-26 04:05 272阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

**后缀表达式，又称逆波兰式**，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则）。

**后缀表达式计算：**  
后缀表达式计算与前缀表达式类似，只是顺序是从左至右，具体过程如下：  
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果

例如：后缀表达式为“2 3 + 4 × 5 -”计算过程如下：  
  （1）从左至右扫描，将 2 和 3 压入堆栈；  
  （2）遇到 + 运算符，因此弹出 3 和 2（ 3 为栈顶元素，2 为次顶元素，注意与前缀表达式做比较），计算出 3+2 的值，得 5，再将 5 入栈；  
  （3）将 4 入栈；  
  （4）接下来是 × 运算符，因此弹出 4 和 5，计算出 4 × 5 = 20，将 20 入栈；  
  （5）将 5 入栈；  
  （6）最后是-运算符，计算出 20-5 的值，即 15，由此得出最终结果。

**中缀表达式转后缀表达式：**  
与转换为前缀表达式相似，步骤如下：  
  （1）初始化两个栈：运算符栈s1和储存中间结果的栈s2；  
  （2）从左至右扫描中缀表达式；  
  （3）遇到操作数时，将其压s2；  
  （4）遇到运算符时，比较其与 s1 栈顶运算符的优先级：  
    a：如果 s1 为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；  
    b：否则，若优先级比栈顶运算符的高，也将运算符压入 s1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）;  
    c：否则，将 s1 栈顶的运算符弹出并压入到 s2 中，再次转到（4）-（1）与s1中新的栈顶运算符相比较；  
  （5）遇到括号时：  
    a：如果是左括号“(”，则直接压入 s1；  
    b：如果是右括号“)”，则依次弹出 s1 栈顶的运算符，并压入 s2 ，直到遇到左括号为止，此时将这一对括号丢弃；  
  （6）重复步骤（2）至（5），直到表达式的最右边；  
  （7）将 s1 中剩余的运算符依次弹出并压入 s2；  
  （8）依次弹出 s2 中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）

例如，将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下：

<table> 
 <thead style="font-size:inherit;color:inherit;line-height:inherit;"> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">扫描到的元素</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">s2(栈底-&gt;栈顶)</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">s1 (栈底-&gt;栈顶)</th> 
   <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">说明</th> 
  </tr> 
 </thead> 
 <tbody style="font-size:inherit;color:inherit;line-height:inherit;border-width:0px;"> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">1</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">1</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">空</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">数字，直接入栈</td> 
  </tr> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">+</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">1</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">+</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">s1为空，运算符直接入栈</td> 
  </tr> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">(</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">1</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">+ (</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">左括号，直接入栈</td> 
  </tr> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">(</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">1</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">+ ( (</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">同上</td> 
  </tr> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">2</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">1 2</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">+ ( (</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">数字</td> 
  </tr> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">+</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">1 2</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">+ ( ( +</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">s1栈顶为左括号，运算符直接入栈</td> 
  </tr> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">3</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">1 2 3</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">+ ( ( +</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">数字</td> 
  </tr> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">)</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">1 2 3 +</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">+ (</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">右括号，弹出运算符直至遇到左括号</td> 
  </tr> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">×</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">1 2 3 +</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">+ ( ×</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">s1栈顶为左括号，运算符直接入栈</td> 
  </tr> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">4</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">1 2 3 + 4</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">+ ( ×</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">数字</td> 
  </tr> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">)</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">1 2 3 + 4 ×</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">+</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">右括号，弹出运算符直至遇到左括号</td> 
  </tr> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">-</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">1 2 3 + 4 × +</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">-</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">-与+优先级相同，因此弹出+，再压入-</td> 
  </tr> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">5</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">1 2 3 + 4 × + 5</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">-</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">数字</td> 
  </tr> 
  <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">到达最右端</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">1 2 3 + 4 × + 5 -</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">空</td> 
   <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">s1中剩余的运算符</td> 
  </tr> 
 </tbody> 
</table>

**得到的最终结果为：“ 1 2 3 + 4 × + 5 - ”**

**END**

![640?wx\_fmt=png][640_wx_fmt_png]

**推荐阅读**：

*  [盖尔-沙普利算法告诉你，你的对象在哪里？][-]

*  [面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

*  [如何有效的写算法题][Link 1]

*  [几道 BAT 算法面试中经常问的「字符串」问题][BAT]

*  [链表算法面试问题？看我就够了！][Link 2]

![640?wx\_fmt=png][640_wx_fmt_png]

欢迎长按下图关注公众号**五分钟学算法**，一起看动画学算法。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

[640_wx_fmt_jpeg]: /images/20220126/1fb18c0e14e6473d92c71334452995e3.png
[640_wx_fmt_png]: /images/20220126/270ac6f5b4e84591830b709b1d971c0f.png
[-]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485359&idx=1&sn=c80013d51595c46a93abf0c58af7d347&chksm=fa0e682ecd79e138acfcad3357051f27a86c440031c9017be0c7c05e61963c4c5f72045b10eb&scene=21#wechat_redirect
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485214&idx=1&sn=00de6e810caa7e261b8f2e19c3acd9cd&chksm=fa0e689fcd79e189282babbe3a688158b505e7b907971eede501addac9e0bec1e9d1c77ffb78&scene=21#wechat_redirect
[BAT]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485091&idx=1&sn=1503058d7c1313552f84073b495c5e76&chksm=fa0e6922cd79e034471194c636e89aa124941a13dabdf4d6197669f51d146f27098b124e5dd8&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484830&idx=1&sn=9d24fc787da4b49b82ac01c7f8de257b&chksm=fa0e6a1fcd79e309a2e7f3e09ec9913a55f1c077287c907f13528578b7785831a2effb3104e0&scene=21#wechat_redirect
[640_wx_fmt_jpeg 1]: /images/20220126/0f87c96d4e4741688aa856eeaa779a24.png