数据结构考研笔记之栈与队列（四）栈与队列应用----括号匹配、中缀表达式转前缀后缀问题

小咪咪 2022-12-13 04:35 115阅读 0赞

### 栈与队列 ###

*  1.括号匹配问题
 *   *  栈
     *   *  例题1
         *  例题2-----不匹配例题1
         *  例题3-----不匹配例题2
 *  2. 表达式求值问题
 *   *  例题
     *   *  1.中缀表达式转前缀表达式
         *  2.中缀表达式转后缀表达式
         *  实现过程：
 *  3. 递归：
 *   *  递归产生的问题：

# 1.括号匹配问题 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center]

## 栈 ##

### 例题1 ###

![在这里插入图片描述][20201010103640926.png_pic_center]  
`算法思想:`  
**1）初始一个空栈，顺序读入括号。  
若是右括号，则与栈顶元素进行匹配  
·若匹配，则弹出栈顶元素并进行下一个元素  
·若不匹配，则该序列不合法  
3)若是左括号，则压入栈中  
4)若全部元素遍历完毕，栈中非空则序列不合法**  
`解题`：  
1.首先1、2都是左括号，直接进栈  
![在这里插入图片描述][20201010103914200.png_pic_center]  
2.第3个括号是右括号`‘）’`并且和2`’（‘`匹配，所以弹出当前栈顶元素，如下图  
![在这里插入图片描述][20201010103929452.png_pic_center]

### 例题2-----不匹配例题1 ###

![在这里插入图片描述][2020101010430652.png_pic_center]’  
`解题`：  
1.和刚才一样,左括号进栈  
![在这里插入图片描述][20201010104230599.png_pic_center]  
2.第3个括号是右括号且与当前栈顶左括号2不匹配，所以此题不匹配  
![在这里插入图片描述][2020101010424165.png_pic_center]

### 例题3-----不匹配例题2 ###

题目：  
![在这里插入图片描述][20201010104346948.png_pic_center]  
`解题`：  
![在这里插入图片描述][2020101010440095.png_pic_center]  
1.左括号1、2进栈，如下图  
![在这里插入图片描述][20201010104454517.png_pic_center]  
2.第三个括号为右括号且与当前栈顶2 左括号匹配，所以弹出此时栈顶2 左括号，  
然后括号4‘ `]`’,与当前栈顶1 左括号’`[`‘,相匹配，所以弹出此时栈顶1’\[‘  
第5个为左括号进栈，如下图  
![在这里插入图片描述][20201010104511368.png_pic_center]  
3.栈非空，不合法。

# 2. 表达式求值问题 #

前缀表达式:+AB  
中缀表达式:A+B  
后缀表达式:AB+  
`符号分别在式子的前中后`

## 例题 ##

`题目：[(A+B)*C]- [E-F]`

### 1.中缀表达式转前缀表达式 ###

1.最先运算的A+B ,`‘+’`提前,如下图  
![在这里插入图片描述][20201010104822740.png_pic_center]  
2，然后是（）\*c, 转换前缀就是将`*`提前 ，如下图  
![在这里插入图片描述][2020101010485228.png_pic_center]  
3，E-F, 将`‘-’`提前。如下图  
![在这里插入图片描述][20201010105059935.png_pic_center]  
4.最后一步就是【】-【】，两个中括号相减， 改为前缀就是将减号提前，如下图  
![在这里插入图片描述][20201010105301811.png_pic_center]  
\[(A+B)\*C\]- \[E-F\] 转成下图  
![在这里插入图片描述][20201010105309725.png_pic_center]

### 2.中缀表达式转后缀表达式 ###

1，*式子首先运算A+B,将’`+`‘后移，如下图：A B +*  
![在这里插入图片描述][20201010105409696.png_pic_center]  
2，\*计算（ ）\*c，转为后缀是将’`*`‘后移，为（）C *,如下图：*  
![在这里插入图片描述][20201010105427887.png_pic_center]  
3，计算\[E-F\],将’`-`’后移，E F - ，如下图  
![在这里插入图片描述][20201010105439593.png_pic_center]  
4，计算\[ \] -\[ \],将‘`-`’后移 \[ \] \[ \] - , 如下图  
![在这里插入图片描述][20201010105509645.png_pic_center]  
最终：A B + C \* E F - -

### 实现过程： ###

`算法思想:`  
**数字直接加入后缀表达式  
运算符时:  
a.若为‘(’，入栈;  
b.若为‘)’，则依次把栈中的运算符加入后缀表达式，直到出现’(’，并从栈中删除’(’;  
c.若为’+’，‘-’，‘\*’，’/‘，  
·栈空，入栈;  
·栈顶元素为’(’，入栈;  
·高于栈顶元素优先级，入栈;  
·否则，依次弹出栈而运算符，直到一个优先级比它低的运算符或‘('为止;  
d.遍历完成，若栈非空依次弹出所有元素。**

1.都为左括号，入栈（算法思想中情况a），如下图  
![在这里插入图片描述][20201010105918610.png_pic_center]  
2，数字A直接加入表达式  
3.加号‘+’，且此时栈顶为左括号，入栈操作，（算法思想中c）如下图  
![在这里插入图片描述][20201010105931678.png_pic_center]  
4.数字B直接加入表达式  
5.符号‘）’，(算法思想b)依次将此时栈中元素弹出加入后缀表达式直到遇到左括号‘（’，并从栈中删除“（”，如下图，  
![在这里插入图片描述][20201010110056191.png_pic_center]  
删除后，栈中只有第一个‘（’  
![在这里插入图片描述][202010101101031.png_pic_center]  
6.符号‘*’，（算法思想c）此时栈顶为‘（’ ，直接入栈，如下图  
![在这里插入图片描述][2020101011014880.png_pic_center]  
7.减号‘-’，不高于此时栈顶‘*’的优先级，弹出栈中元素，直到‘(’,（算法思想c).  
![在这里插入图片描述][20201010110158994.png_pic_center]  
![在这里插入图片描述][20201010110203993.png_pic_center]

8.减号‘-’，此时栈为空，直接入栈（算法思想C）  
左括号‘（’，直接入栈  
数字E直接加入后缀（算法思想a）  
减号‘-’，因为此时栈顶为左括号‘（’，所以减号直接入栈（算法思想C）  
数字F直接加入后缀（算法思想a）  
![在这里插入图片描述][20201010110229511.png_pic_center]  
9.右括号‘）’，依次弹出栈顶加入到后缀，直到遇到左括号‘（’（算法思想b）。  
![在这里插入图片描述][20201010110239228.png_pic_center]  
![在这里插入图片描述][2020101011024577.png_pic_center]  
10.遍历完了，若栈不为空，将栈中数据依次弹出加入到后缀。（算法思想d）  
![在这里插入图片描述][20201010110250186.png_pic_center]

# 3. 递归： #

递归若在一个函数、过程或数据结构的定义中又应用了它自身，则称它为递归定义的，简称递归  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][2020101011055522.png_pic_center]

int Fib(int n){
        
    	if(n == o)
    		return 0 ;
    	else if(n == 1)
    		return l;
    	else
    		return Fib(n-1) + Fib (n-2);
    )

递归的精髓在于能否将原始问题转换为属性相同但规模较小的问题

## 递归产生的问题： ##

*在递归调用过程中，系统为每一层的返回点、局部变量、传入实参等开辟了递归工作栈来进行数据存储，递归次数过多容易造成栈溢出。
     *通常情况下递归的效率并不高

\*\*\*递归转换算法转换为非递归算法，往往需要借助栈来进行

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/bc7347342f6b470d883f1f81a108c28a.png
[20201010103640926.png_pic_center]: /images/20221123/cfd4b65d54d0469c95ad838033da2d23.png
[20201010103914200.png_pic_center]: /images/20221123/7a5f12148cde480f8ff353c735007e45.png
[20201010103929452.png_pic_center]: /images/20221123/0d51cc737bbd478da5581e98b4262666.png
[2020101010430652.png_pic_center]: /images/20221123/4ba2285591c84a67a6f85133d14a8fad.png
[20201010104230599.png_pic_center]: /images/20221123/7afade29ed1f4181a5953028404afa1c.png
[2020101010424165.png_pic_center]: /images/20221123/7939e3f18ca74a42b37d2d2b53c86538.png
[20201010104346948.png_pic_center]: /images/20221123/c1e6358147414704977bd97600213f16.png
[2020101010440095.png_pic_center]: /images/20221123/59677a3a674041ca9c8f49071eea2feb.png
[20201010104454517.png_pic_center]: /images/20221123/380b74c7335d484ca976f67852cc41f9.png
[20201010104511368.png_pic_center]: /images/20221123/55b9a91a62534ff49280c471a08c39c2.png
[20201010104822740.png_pic_center]: /images/20221123/9a0292a504554061a9fd5c4880b7867c.png
[2020101010485228.png_pic_center]: /images/20221123/53f20db4cf044879ab6c92360cb5cddd.png
[20201010105059935.png_pic_center]: /images/20221123/60daea5bc61f427f81df4d7a31ad3c3a.png
[20201010105301811.png_pic_center]: /images/20221123/4bf4d30ba96348d48a7e58bc1c38368c.png
[20201010105309725.png_pic_center]: /images/20221123/6b0e65cb517d4e99bd0a5669f19468c9.png
[20201010105409696.png_pic_center]: /images/20221123/cbf605fc2c1e40859dc1534589ad75ee.png
[20201010105427887.png_pic_center]: /images/20221123/c0df4dd7541842989d7ce3dfbe0027f1.png
[20201010105439593.png_pic_center]: /images/20221123/6ea7c309f0a847e08d59532104a85a73.png
[20201010105509645.png_pic_center]: /images/20221123/2cf4202f9e654bd39d149dae9b8b0216.png
[20201010105918610.png_pic_center]: /images/20221123/7468c28761a540f993452a5baf79076e.png
[20201010105931678.png_pic_center]: /images/20221123/9f186acfb2ae44c29d84ec076c520559.png
[20201010110056191.png_pic_center]: /images/20221123/59878ad0d0f34dd1aefe046f6fbae7b4.png
[202010101101031.png_pic_center]: /images/20221123/d7fa77c8ddba46f5aecf28adfd4770d4.png
[2020101011014880.png_pic_center]: /images/20221123/ed75ac85e32c4bb19ed567e2c17fc046.png
[20201010110158994.png_pic_center]: /images/20221123/7b6a2d2a1f294bccb424c85f2535df8b.png
[20201010110203993.png_pic_center]: /images/20221123/d80334c88e1f4bdf96956a7dcae1659d.png
[20201010110229511.png_pic_center]: /images/20221123/526d710a8d13429cb0bab57f2323b72d.png
[20201010110239228.png_pic_center]: /images/20221123/d73c558613af4f71a8e3aa0d06036ded.png
[2020101011024577.png_pic_center]: /images/20221123/069bb428192443d68c81f7d59e5e35fd.png
[20201010110250186.png_pic_center]: /images/20221123/4cb1f331994e4f1bb308be062cefa5c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NmOTA5MA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/af72c5dd504248b4910ffe4c44ebc222.png
[2020101011055522.png_pic_center]: /images/20221123/5e2a8a4394304b0fb1389af006bd9977.png