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

??

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

??今天是第一天上班，給大家?guī)?lái)的是《計(jì)算器的實(shí)現(xiàn)------棧的實(shí)戰(zhàn)》。

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

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

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

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

? 首先讓我們來(lái)舉一個(gè)例子，彈夾式手槍?zhuān)蚁氪蠹乙欢ǘ荚陔娨暽厦嬉?jiàn)過(guò)甚至很多同學(xué)肯定都還玩過(guò)，那么彈夾中的子彈射出來(lái)的先后順序你們有沒(méi)有想過(guò)呢？對(duì)的，是先射出后面的子彈然后再射出前面的子彈，想要射出前面的子彈就必須要先射完后面的子彈。

覺(jué)得這個(gè)例子不夠形象？那讓我們?cè)倏匆粋€(gè)例子。在使用APP時(shí)，大家一定都用過(guò)返回鍵吧？它是不是優(yōu)先返回到前一步，而不是返回到前前步，或者前前前步？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3：接下來(lái)是“-”，所以將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：接下來(lái)是“/”，因此，棧頂?shù)?和16出棧，16和2相除得到8,8進(jìn)棧

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

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

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

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

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

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

?1：初始化一個(gè)空棧，用來(lái)對(duì)符號(hào)進(jìn)出棧使用。

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

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

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

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

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

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

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

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

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

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

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

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

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

#includeusing namespace std;int top;int j = 2;int k = 0;class date {  public:  double a = -1;  //double是因?yàn)闀?huì)出現(xiàn)小數(shù)，設(shè)為-1是為了方便判斷  char m=NULL;}b[99], c[99], d[99];//生成棧，并初始化棧,這里生成三個(gè)棧，分別用于獲得元素，儲(chǔ)存符號(hào)，儲(chǔ)存數(shù)字void getdate()//獲取元素 {  char q;  int i = 0;  while ((q = getchar()) != '\n')//這里需要用getchar，因?yàn)槭禽斎氲淖址?{    if (i == 0)//第一個(gè)元素要單獨(dú)拿出來(lái) {      if (q != '0')      b[i].a = q - '0';      //一個(gè)小技巧，將字符’n’轉(zhuǎn)變?yōu)檎麛?shù)n else {        cout << "error date";        return;      }    } else    if (q >= '0' && q <= '9')    if (b[i-1].a >=0)  //判斷一個(gè)數(shù)是幾位數(shù) {      b[i - 1].a = b[i - 1].a * 10 + (q - '0');      //多位數(shù)應(yīng)該如何儲(chǔ)存      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，在編譯時(shí)系統(tǒng)會(huì)自動(dòng)認(rèn)為輸入了-2，無(wú)法通過(guò)編譯  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)過(guò)計(jì)算你的結(jié)果為  " <q[2];  }  void main() {    cout << "這是一個(gè)計(jì)算器，請(qǐng)輸入你需要計(jì)算的式子" << endl;    getdate();    sort();    calculate();  }

最終成果圖~~

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

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