數據結構---棧及四則運算實現
- 2020 年 4 月 2 日
- 筆記
假設我們要求輸入類似這樣一個表達式：9+(3-1)*3+10/2，輸出結果。我們知道先括弧，再乘除，最後加減，中學時候使用的科學計算器，是允許輸入這樣的表達式計算結果的，那麼電腦怎麼知道這個串裡面先算括弧再算乘除呢？我們先來介紹下棧這種數據結構，再來解決這個問題。
前面已經說過數組的連表，現在來說另外一種線性表的數據結構---棧。
舉個比較形象的例子，洗盤子的時候，是不是一個一個往上面堆著放，拿的時候也從上面一個一個的拿，最先放的在最下面，最後放的在最上面，拿的時候第一個拿到。這就是典型的棧結構。先進後出First In Last Out(FILO).
怎麼來實現一個棧結構呢，棧也是一種線性表，前面也有提到兩種很基礎的線性表結構的數據結構數組和鏈表。棧其實就是第一個特殊的鏈表或者數組。可以基於數組或者鏈表來實現，成為數組棧或者鏈棧，與之具有數組和鏈表相關特點。
棧的特殊點在於先進去的元素放在棧低，後進的在棧頂。向棧中插入一個元素叫入棧、進棧、壓棧都行，插入的數據會被放在棧頂。從棧中取出一個元素叫出棧、退棧都行，取出之後，原本棧頂的這個元素就會被刪掉，讓它下面的那個元素成為新的棧頂元素。
數組棧一般棧低是索引開始的元素，壓棧就往索引增長方向走；鏈棧一般棧低是頭結點，棧頂是尾結點。
既然都是用數組或鏈表來實現，為什麼還單獨拎出來一個數據結構呢。數組和鏈表暴露了太多了的操作。就會更容易出錯。針對性的封裝出來的棧這種結構，在某些場景會更加適合。想像一下我們瀏覽器的的前進後退，是不是就很像兩個棧的數據在互相交換操作，一個前進棧，一個後退棧。點後退，把後退棧的棧頂彈出，放進前進棧的棧頂；再點前進，是不是就是壓進前進棧頂的後退棧的棧頂元素。就這樣互相交替著。
想像一個程式的調用流程是不是也是一個棧結構。最後調用的方法最先執行。
Java裡面的Stack也是基於數組實現的，它繼承了Vector。我們用數組實現一個簡單棧的基本操作：
package com.nijunyang.algorithm.stack; /** * Description: * Created by nijunyang on 2020/4/1 23:48 */ public class MyStack<E> { private static final int DEFAULT_SIZE = 10; private Object[] elements; private int size; public MyStack() { this(DEFAULT_SIZE); } public MyStack(int capacity) { this.elements = new Object[capacity]; } /** * 入棧 * @param e */ public void push(E e) { //彈性伸縮，擴容/收縮釋放記憶體空間 if (size >= elements.length) { resize(size * 2); } else if (size > 0 && size < elements.length / 2) { resize(elements.length / 2); } elements[size++] = e; } /** * 出棧 */ public E pop() { if (isEmpty()) { return null; } E e = (E) elements[--size]; //size是5，那麼最後一個元素就是4也就是--size elements[size] = null; //現在size已經是4了，彈出就是4這個元素的位置置為空 return e; } public boolean isEmpty() { return size == 0; } public int size() { return size; } /** * 擴容/收縮 */ private void resize(int newCapacity) { Object[] temp = new Object[newCapacity]; for(int i = 0 ; i < size; i ++){ temp[i] = elements[i]; } elements = temp; } public static void main(String[] args){ MyStack<Integer> myStack = new MyStack(5); myStack.push(1); myStack.push(2); myStack.push(3); myStack.push(4); myStack.push(5); myStack.push(6); System.out.println(myStack.size); Integer e = myStack.pop(); System.out.println(e); e = myStack.pop(); System.out.println(e); e = myStack.pop(); System.out.println(e); e = myStack.pop(); System.out.println(e); e = myStack.pop(); System.out.println(e); e = myStack.pop(); System.out.println(e); e = myStack.pop(); System.out.println(e); } }
現在用我們看看怎麼用棧來解決9+(3-1)*3+10/2這個計算問題
首先我們要怎麼來處理括弧和運算符號的優先順序呢
這裡先說一下中綴表達式和後綴表達式，像這個表達式9+(3-1)*3+10/2就是中綴表達式，如果我們轉換成9 3 1 - 3 * + 10 2 / + 這個就是後綴表達式，後綴表達式也叫逆波蘭，可以可以自行百度或者google,後綴表達式就是操作符號在兩個操作數的後面，而中綴表達式就是操作符號在兩個操作數的中間。
看下後綴表達式是怎麼操作的，就是遇到操作符號就把前面兩個數進行符號運算：
9 3 1 - 3 * + 10 2 / + 這個表達式的操作如下：
9 3 1 - 這個時候就把3和1 相減得到2 => 9 2 3 * 這個時候就把2和3相乘 得到6 =>
9 6 + => 15 10 2 / =>15 5 + => 20
大致就是這麼個流程，這個過程是不是很像棧的操作，遇到數字就入棧，遇到符號就把數字前面兩個數字出棧進行計算，然後將結果入棧，直到表達式結束。
現在我們只要把中綴表達式轉換成後綴表達式就可以進行計算了。看下百度的轉換流程
簡單來說就是用一個棧來存放符號，然後從左到右遍歷中綴表達式的數字和字元，若是數字就輸出，若是符號則判斷和棧頂符號的優先順序，如果是括弧或優先順序低於棧頂元素，則依次出棧並輸出，將當前符號進棧，直到最後結束。
9+(3-1)*3+10/2
先初始化一個棧stack，然後依次遍歷我們的中綴表達式，操作邏輯如下：
- 9 輸出 => 9
- + 棧空的直接進棧：stack：+
- ( 未配對的 直接進棧：stack：+ (
- 3 數字直接輸出：9 3
- - 前面是( 直接進棧：stack + ( -
- 1 直接輸出： 9 3 1
- ) 將前面的符號彈出輸出，直到匹配到第一個(為止：9 3 1 - stack: +
- * 優先順序高於 + 進棧： stack： + *
- 3 輸出 9 3 1 - 3
- + 優先順序低於棧頂的* 將棧頂彈出輸出 繼續判斷之後棧頂是否比+優先順序低(同級也彈出，直到有限比棧頂高，或者空棧為止)，這裡就會連續彈出 * + 然後將當前的 + 入棧：9 3 1 - 3 * + stack: +
- 10 輸出：9 3 1 - 3 * + 10
- / 優先順序高於棧頂 + 直接入棧：stack： + /
- 2 直接輸出： 9 3 1 - 3 * + 10 2
- 最後符號依次出輸出：9 3 1 - 3 * + 10 2 / +
從上述邏輯中可以看到，不管是最後的計算，還是中綴表達式轉後綴表達式中都用到棧這種數據結構。
