【數(shù)據(jù)結(jié)構(gòu)】計算器的實(shí)現(xiàn)--棧的實(shí)戰(zhàn)

??

大家好啊，我是新來的小編~此處應(yīng)有歡迎聲~~

??今天是第一天上班，給大家?guī)淼氖恰队嬎闫鞯膶?shí)現(xiàn)------棧的實(shí)戰(zhàn)》。

??大家有沒有和小編一樣小時候的計算能力很差，被各種計算折磨的暈頭轉(zhuǎn)向?到后來，我發(fā)現(xiàn)了計算器這樣神奇的東西，哇，真的是救我于水火之中。我因此瀟灑了一兩年的時間（此處應(yīng)有歸零聲音響起）。

??不過快樂并不長久，學(xué)校開始要求進(jìn)行多個數(shù)的加減乘除并且還涉及到大中小括號的四則運(yùn)算，家里的老式計算器不好使了。9+（3-1）*3+10/2，這么簡單的式子，計算器完全沒有辦法計算，幸好自己存了一點(diǎn)私房錢，買了一個高級一點(diǎn)的計算器，引入了四則運(yùn)算表達(dá)式和括號。

老式計算器對于兩個的運(yùn)算原理大家都會進(jìn)行，那么你有沒有想過現(xiàn)在新式的計算器他是如何實(shí)現(xiàn)對數(shù)學(xué)表達(dá)式的求值呢？

??在討論這個問題之前，讓我們來了解一種全新的數(shù)據(jù)結(jié)構(gòu)---棧（Stack）。

? 首先讓我們來舉一個例子，彈夾式手槍，我想大家一定都在電視上面見過甚至很多同學(xué)肯定都還玩過，那么彈夾中的子彈射出來的先后順序你們有沒有想過呢？對的，是先射出后面的子彈然后再射出前面的子彈，想要射出前面的子彈就必須要先射完后面的子彈。

覺得這個例子不夠形象？那讓我們再看一個例子。在使用APP時，大家一定都用過返回鍵吧？它是不是優(yōu)先返回到前一步，而不是返回到前前步，或者前前前步？

上述例子的原因究竟是什么呢？就是因?yàn)樗鼈冇玫搅艘环N叫做棧的數(shù)據(jù)結(jié)構(gòu)。

棧（stack）是限定僅在表尾進(jìn)行插入和刪除的線性表。

在通常情況下，我們把允許插入和刪除的一端稱為棧頂（top），另一端稱為棧底（botton），不含任何數(shù)據(jù)元素的棧稱為空棧。棧又稱為后進(jìn)先出（Last In First Out)的線性表，簡稱為LIFO結(jié)構(gòu)。

首先你要明確棧是一個線性表，棧的元素具有線性結(jié)構(gòu)，即前驅(qū)后繼關(guān)系，只不過他是一種特殊的線性表，他的插入和刪除只能發(fā)生在棧頂而不是發(fā)生在其他的位置。

棧的插入我們叫做進(jìn)棧，棧的刪除我們叫做出棧。

簡單的介紹了棧這種結(jié)構(gòu)之后，現(xiàn)在讓我們回到我們最初的問題，如何實(shí)現(xiàn)計算器的各種功能。

現(xiàn)在大家來看一看一個多項計算表達(dá)式，比如：“9+（5-1）*2+16/2”，仔細(xì)觀察我們會發(fā)現(xiàn)，括號都是成對出現(xiàn)的，由左括號就一定會有右括號，對于多重括號，最終也是完全嵌套匹配的。這用棧結(jié)構(gòu)正好合適，只要碰到左括號，就入棧，不管表達(dá)式有多少重括號，反正遇到左括號就進(jìn)棧，而后面出現(xiàn)右括號時，就讓棧頂?shù)淖罄ㄌ柍鰲?，期間讓數(shù)字運(yùn)算，這樣，最終右括號的表達(dá)式從左到右巡查一遍，棧應(yīng)該是由空到有元素，最終再因全部匹配成功后成為空棧。

解決了括號的問題還不夠啊，因?yàn)槔ㄌ栔皇撬膭t運(yùn)算的一小部分，先乘除后加減使得問題依舊復(fù)雜，怎么辦呢？波蘭邏輯學(xué)家J?盧卡西維茲(J? Lukasewicz)于1929年提出了一種不需要括號的后綴表達(dá)式，我們也把它稱為逆波蘭（Rever Polish Notation，RPN）表示。為啥叫這個名字呢？我覺得可能是因?yàn)檫@位邏輯學(xué)家的名字太復(fù)雜？Hh~~這也告訴我們呀，想要流芳百世，名字必須要取的好~~

讓我們用剛開始的例子來分析一下逆波蘭表達(dá)式，對于“9+（5-1）*2+16/2”，如果變成逆波蘭的樣子，應(yīng)該為“9 5 1 - 2 * + 16 2 / +”，看見這個變化大家肯定對于后綴表達(dá)式這個名字的理解又深化了一些吧？其實(shí)就是所有的符號都是在要運(yùn)算數(shù)字的后面出現(xiàn)。這里的括號不見了，同學(xué)們看起來肯定一點(diǎn)也不習(xí)慣，不過沒關(guān)系，咱們聰明的計算機(jī)喜歡。

為了更好的給同學(xué)們解釋逆波蘭表達(dá)式的好處，我們現(xiàn)在來看看計算機(jī)如何運(yùn)用它來計算出來最終結(jié)果的。

后綴表達(dá)式：9 5 1 - 2 * + 16 2 / +

規(guī)則：從左到右遍歷表達(dá)式的每個數(shù)字和符號，遇到是數(shù)字就進(jìn)棧，遇到是符號，就將處于棧頂?shù)膬蓚€數(shù)字出棧進(jìn)行運(yùn)算，運(yùn)算結(jié)果再進(jìn)棧，一直帶最終獲得結(jié)果。

1：初始化一個空棧。此棧用來對要運(yùn)算的數(shù)字進(jìn)出使用，如圖所示

2：后綴表達(dá)式的前三個元素都是數(shù)字，直接進(jìn)棧

3：接下來是“-”，所以將1出棧作為減數(shù)，5出棧作為被減數(shù)，并運(yùn)算得到4，再將4進(jìn)棧

4：接著是2入棧

5：后面是“*”，也就意味著棧中的4,2出棧。得到8，然后將8進(jìn)棧

6：下面是“+”，所以將8和9出棧相加得到17，再進(jìn)棧

7：接著16和2進(jìn)棧

8：接下來是“/”，因此，棧頂?shù)?和16出棧，16和2相除得到8,8進(jìn)棧

9：最后一個符號是“+”，所以8和17出棧并相加得到25，將25進(jìn)棧

10：最后將25出棧，棧變?yōu)榭铡?/span>

很快，我們就解決了計算的問題，但是似乎，還有一個更重要的問題我們沒有解決啊，怎么樣將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式呢？

下面讓我們來了解一下如何將中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式。

目的，將9+（5-1）*2+16/2轉(zhuǎn)變?yōu)? 5 1 - 2 * + 16 2 / +

??規(guī)則：從左到右遍歷中綴表達(dá)式的每個數(shù)字和符號，若是數(shù)字就輸出，即成為后綴表達(dá)式的一部分;若是符號，則判斷其與棧頂符號的優(yōu)先級，是右括號或者優(yōu)先級不高于棧頂符號（乘除優(yōu)先加減）則棧頂元素依次出棧并輸出，并將當(dāng)前符號進(jìn)棧，直到最終輸出后綴表達(dá)式為止。

?1：初始化一個空棧，用來對符號進(jìn)出棧使用。

2：第一個字符是數(shù)字9，輸出9，后面的是符號“+”，進(jìn)棧。

3：第三個符號是“（”，依然是符號，因?yàn)樗亲罄ㄌ?，還沒有完成配對，進(jìn)棧，如圖所示。

4：第四個字符是5，輸出，總表示為9 5，接著是“-”，進(jìn)棧。

5：接下來是數(shù)字1，輸出，表達(dá)式變?yōu)? 5 1，后面是“）”，此時，我們需要去匹配此前的“（”，所以棧頂依次出棧，并輸出，直到“（”出棧為止，此時左括號上方只有“-”，因此輸出“-”，表達(dá)式變?yōu)? 5 1 -。

6：緊接著是“*”，因?yàn)榇藭r的棧頂符號是“+”，優(yōu)先級低于“*”,因此不輸出，“*”進(jìn)棧，接著是數(shù)字2，輸出，表達(dá)式變?yōu)? 5 1 - 2，

7：之后是符號“+”，此時當(dāng)前棧頂元素“*”比這個“+”的優(yōu)先級高，因此棧中的元素出棧并輸出（沒有比“+”更低的優(yōu)先級，所以全部出棧），總輸出表達(dá)式為9 5 1 - 2 * +。然后將“+”入棧，

8：緊接著是數(shù)字16，輸出，表達(dá)式變?yōu)? 5 1 - 3 * + 16.后面是符號“/”，入棧。

9：最后一個數(shù)字是2，輸出。

?10：因?yàn)橐呀?jīng)到了最后，所以此時我們將棧里面的所有元素出棧并輸出。最終表達(dá)式變?yōu)? 5 1 - 2 * + 16 2 / +。

經(jīng)過上面的介紹，我們可以得出要想讓我們的計算機(jī)具有處理我們通常的標(biāo)準(zhǔn)（中綴）表達(dá)式的能力，關(guān)鍵在于兩個步驟。

?1：中綴變后綴（棧用來進(jìn)出運(yùn)算的符號）

2：計算后綴（棧用來進(jìn)出運(yùn)算的數(shù)字）

看了以上的介紹，我想大家一定都迫不及待的想見一見計算器的代碼了，準(zhǔn)備好，他來了。

#includeusing namespace std;int top;int j = 2;int k = 0;class date {  public:  double a = -1;  //double是因?yàn)闀霈F(xiàn)小數(shù)，設(shè)為-1是為了方便判斷  char m=NULL;}b[99], c[99], d[99];//生成棧，并初始化棧,這里生成三個棧，分別用于獲得元素，儲存符號，儲存數(shù)字void getdate()//獲取元素 {  char q;  int i = 0;  while ((q = getchar()) != '\n')//這里需要用getchar，因?yàn)槭禽斎氲淖址?{    if (i == 0)//第一個元素要單獨(dú)拿出來 {      if (q != '0')      b[i].a = q - '0';      //一個小技巧，將字符’n’轉(zhuǎn)變?yōu)檎麛?shù)n else {        cout << "error date";        return;      }    } else    if (q >= '0' && q <= '9')    if (b[i-1].a >=0)  //判斷一個數(shù)是幾位數(shù) {      b[i - 1].a = b[i - 1].a * 10 + (q - '0');      //多位數(shù)應(yīng)該如何儲存      i--;    } else    b[i].a = q - '0'; else    b[i].m = q;    i++;  }  top = i - 1;  //棧頂top所在的位置應(yīng)該為i-1}void sort()//進(jìn)行中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式 {  for (int i = 0 ;i <= top; i++) {    if (b[i].a >= 0) {      d[k].a = b[i].a;      k++;    } else    if (j == 2) {      c[j].m = b[i].m;      j++;    } else    if (b[i].m == '(') {      c[j].m = b[i].m;      j++;    } else    if (b[i].m == ')') {      d[k++].m = c[--j].m;      c[j].m = NULL;      c[--j].m = NULL;    } else if (c[0].m == '*' || c[0].m == '/') {      d[k++].m = c[--j].m;      d[k++].m = c[--j].m;      c[j].m = b[i].m;    } else    c[j++].m = b[i].m;  }  while ((j - 1) != 1)  d[k++].m = c[--j].m;}void calculate() {  double q[11] ;  int o = 2;  //為何設(shè)為2？因?yàn)樵诤竺嬗衞-2，在編譯時系統(tǒng)會自動認(rèn)為輸入了-2，無法通過編譯  q[0] = 1;  q[1] = 1;  k--;  for (int i = 0; i <= k; i++)  if (d[i].a != -1) {    q[o] = d[i].a;    o++;  } else {    switch (d[i].m) {      case '+': {        q[o - 2] = q[o - 2] + q[o - 1];        o--;        break;      }      case '-': {        q[o - 2] = q[o - 2] - q[o - 1];        o--;        break;      }      case '*': {        q[o - 2] = q[o - 2] * q[o - 1];        o--;        break;      }      case '/': {        q[o - 2] = (q[o - 2]*1.0) / q[o - 1];        o--;        break;      }      //*1.0是為了防止直接將分?jǐn)?shù)轉(zhuǎn)變?yōu)檎麛?shù)    }  }  if (--o == 2) {    cout << "你想要保留的小數(shù)位為？";    int z;    cin >> z;    cout << "經(jīng)過計算你的結(jié)果為  " <q[2];  }  void main() {    cout << "這是一個計算器，請輸入你需要計算的式子" << endl;    getdate();    sort();    calculate();  }

最終成果圖~~

本次的推文就到此結(jié)束啦，希望各位看客老爺能夠有所收獲！

參考書籍程杰《大話數(shù)據(jù)結(jié)構(gòu)》