文字：獨木

排版：獨木

圖片：獨木

棧與隊列

• 1.括號匹配問題

  • 棧

    • 例題1

    • 例題2-----不匹配例題1

    • 例題3-----不匹配例題2

• 2. 表達式求值問題

  • 例題

    • 1.中綴表達式轉前綴表達式

    • 2.中綴表達式轉后綴表達式

    • 實現過程：

• 3. 遞歸：

  • 遞歸產生的問題：

1.括號匹配問題

棧

例題1

算法思想:1)初始一個空棧，順序讀入括號。
若是右括號，則與棧頂元素進行匹配
·若匹配，則彈出棧頂元素并進行下一個元素
·若不匹配，則該序列不合法
3)若是左括號，則壓入棧中
4)若全部元素遍歷完畢，棧中非空則序列不合法

???解題：1.首先1、2都是左括號，直接進棧

2.第3個括號是右括號‘)’并且和2’(‘匹配，所以彈出當前棧頂元素，如下圖

例題2-----不匹配例題1

’

?解題：1.和剛才一樣,左括號進棧2.第3個括號是右括號且與當前棧頂左括號2不匹配，所以此題不匹配

例題3-----不匹配例題2

題目：

?解題：1.左括號1、2進棧，如下圖2.第三個括號為右括號且與當前棧頂2 左括號匹配，所以彈出此時棧頂2 左括號，然后括號4‘?]’,與當前棧頂1 左括號’[‘,相匹配，所以彈出此時棧頂1’[‘第5個為左括號進棧，如下圖3.棧非空，不合法。

2. 表達式求值問題

前綴表達式:+AB
中綴表達式:A+B
后綴表達式:AB+符號分別在式子的前中后

例題

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

1.中綴表達式轉前綴表達式

1.最先運算的A+B ,‘+’提前,如下圖
2.然后是()*c, 轉換前綴就是將*提前 ，如下圖
3，E-F, 將‘-’提前。如下圖
4.最后一步就是【】-【】，兩個中括號相減， 改為前綴就是將減號提前，如下圖
[(A+B)*C]- [E-F] 轉成下圖

2.中綴表達式轉后綴表達式

1，式子首先運算A+B,將’+‘后移，如下圖：A B +
2，*計算( )*c，轉為后綴是將’*‘后移，為()C?,如下圖：
3，計算[E-F],將’-’后移，E F - ，如下圖
4，計算[ ] -[ ],將‘-’后移 [ ] [ ] - , 如下圖
最終：A B + C * E F - -

實現過程：

算法思想:zho數字直接加入后綴表達式
運算符時:
a.若為‘(’，入棧;
b.若為‘)’，則依次把棧中的運算符加入后綴表達式，直到出現’(’，并從棧中刪除’(’;
c.若為’+’，‘-’，‘*’，’/‘，
·棧空，入棧;
·棧頂元素為’(’，入棧;
·高于棧頂元素優先級，入棧;
·否則，依次彈出棧頂運算符，直到一個優先級比它低的運算符或‘('為止;
d.遍歷完成，若棧非空依次彈出所有元素。

1.都為左括號，入棧(算法思想中情況a)，如下圖
2，數字A直接加入表達式
3.加號‘+’，且此時棧頂為左括號，入棧操作，(算法思想中c)如下圖
4.數字B直接加入表達式
5.符號‘)’，(算法思想b)依次將此時棧中元素彈出加入后綴表達式直到遇到左括號‘(’，并從棧中刪除“(”，如下圖，
刪除后，棧中只有第一個‘(’
6.符號‘’，(算法思想c)此時棧頂為‘(’ ，直接入棧，如下圖
7.減號‘-’，不高于此時棧頂‘’的優先級，彈出棧中元素，直到‘(’,(算法思想c).

8.減號‘-’，此時棧為空，直接入棧(算法思想C)
左括號‘(’，直接入棧
數字E直接加入后綴(算法思想a)
減號‘-’，因為此時棧頂為左括號‘(’，所以減號直接入棧(算法思想C)
數字F直接加入后綴(算法思想a)
9.右括號‘)’，依次彈出棧頂加入到后綴，直到遇到左括號‘(’(算法思想b)。
10.遍歷完了，若棧不為空，將棧中數據依次彈出加入到后綴。(算法思想d)

3. 遞歸：

遞歸若在一個函數、過程或數據結構的定義中又應用了它自身，則稱它為遞歸定義的，簡稱遞歸

int

遞歸的精髓在于能否將原始問題轉換為屬性相同但規模較小的問題

遞歸產生的問題：

*在遞歸調用過程中，系統為每一層的返回點、局部變量、傳入實參等開辟了遞歸工作棧來進行數據存儲，遞歸次數過多容易造成棧溢出。
*通常情況下遞歸的效率并不高

***遞歸轉換算法轉換為非遞歸算法，往往需要借助棧來進行

End

1

發現更多精彩

關注公眾號

總結

以上是生活随笔為你收集整理的c语言中缀表达式求值_数据结构考研笔记之栈与队列（四）栈与队列应用括号匹配、中缀表达式转前缀后缀问题...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。