分享一下我老師大神的人工智能教程！零基礎，通俗易懂！http://blog.csdn.net/jiangjunshow

也歡迎大家轉載本篇文章。分享知識，造福人民，實現我們中華民族偉大復興！

本文章的解決方法參考了《大話數據結構》中關于棧的應用介紹

值得注意的是，書中關于中綴表達式轉后綴的講解中不盡清楚。本人也在這里花了點時間進行推敲錯誤的原因，也在網上搜到了這篇文章，比較好地介紹了中綴轉后綴的的規則

原理：

用計算機求解四則運算，可以使用棧。因為棧的“先進后出”的特性正好滿足了能通過后綴表達式去計算出四則運算式子的結果。而后綴表達式的轉化也能使用棧對中綴表達式進行操作從而轉化。明顯地，由中綴表達式-》后綴表達式， 后綴表達式-》式子結果。 都需要使用到棧。所以編碼實現中，我們著重的是實現這兩個過程的函數（infix_to_suffix()、suffix_to_result()）

注意：

測試數據

• 每個數可以是只達個位的數，也可以達十位以上的數
• 可以是負數或正數（負數需在兩邊添加括號）
• 括號內能存在多個括號，例：( ( 2 + 3 ) + ( 4 + 5 ) + ( ( 6 + 7 ) + 8 ) )

實現

• 定義了一個全局table用來存儲各個運算符的優先級。 + - 等優先級，* / 等優先級， （）不存在優先級（這里主要為了代碼實現而取消其優先級）
• 設置了一個 priority 變量進行存儲棧頂元素的優先級，這在中綴轉后綴的時候被使用到，并在每次的壓棧出棧后，都須對新的棧頂元素進行記錄其優先級
• 在中綴轉后綴的函數中，主要包含這幾部分：1. 遇到數字直接輸出，然后continue ?2.左括號直接壓棧，然后continue?3.右括號則將將棧中在左括號以上的所有運算符彈出，然后continue ?4. 若是運算符，判斷是否優先級比棧頂元素小或相等，若是，則將在左括號前或優先級大于或等于待壓棧元素的棧中元素出棧。若不是，則正常壓棧，正常壓棧過程中需判斷是否負數 ?5.遍歷中綴表達式結束后，將棧中還存在的所有元素進行出棧

#include <stdio.h>#include <stdlib.h>#include <string.h>const int MAXSIZE = 100;//棧的數據結構typedef struct {?int??? data[MAXSIZE];?int??? top;} Stack;int??? table[] = {0,0,2,1,0,1,0,2};//查詢運算符優先級表//函數說明：將中綴表達式轉換為后綴表達式//參數說明：//sta：??? 轉換過程需使用的棧空間//infix：? 待轉換的中綴表達式//suffix： 存儲轉換后的后綴表達式//length： 記錄后綴表達式的長度void infix_to_suffix(Stack *sta, char *infix, int *suffix, int *length);//函數說明：將后綴表達式轉換為結果直接返回//參數說明：//sta：??? 轉換過程需使用的棧空間//suffix： 存儲轉換后的后綴表達式//length： 記錄后綴表達式的長度int? suffix_to_result(Stack *sta, int *suffix, int length);void init(Stack *sta);//棧空間初始化int main(){?//這里將標準輸入輸出流重定向到文件中//?freopen("in.txt", "r", stdin);//?freopen("out.txt", "w", stdout);?Stack???? sta;?int?????? length;?int?????? result;???????? //接受后綴表達式轉換的結果?int?????? sstr[MAXSIZE];? //存儲后綴表達式?char????? istr[MAXSIZE];? //存儲中綴表達式?printf("請輸入以 + - * / 組成的四則運算\n（注意負數需要在兩旁添加上括號）\n");?scanf("%s", istr);?init(&sta); //對棧空間初始化?infix_to_suffix(&sta, istr, sstr, &length);?init(&sta); //再次對棧空間初始化?result = suffix_to_result(&sta, sstr, length);?printf("%d\n", result);//?fclose(stdin);//?fclose(stdout);?return??? 0;}void infix_to_suffix(Stack *sta, char *infix, int *suffix, int *length){?int??? i;????//循環變量?int??? b = 0;???//當數字是十位或以上的時候進行記錄?int??? j = 0;???//suffix數組的下標?int??? priority = 0;?//記錄棧頂元素的優先級?//for循環的第三表達式不進行i++，將其放在每一次的壓棧后或直接輸出到suffix進行i++?for (i = 0; i < strlen(infix); )?{??//如果是數字的話，直接放在suffix中,然后continue??if (infix[i] >= '0' && infix[i] <= '9')??{???b = 0;??//謹記每次都需重新賦值為零！???while (infix[i] >= '0' && infix[i] <= '9')???{????b = b * 10 + (infix[i] - '0');????i++;???}???suffix[j] = b;???j++;???continue;??}??//如果是右括號的話，將棧中在左括號以上的所有運算符彈出,然后continue??if (infix[i] == 41)??{???while (sta->data[sta->top] != 40)???{????suffix[j] = sta->data[sta->top];????sta->data[sta->top] = 0;????sta->top--;????j++;???}???sta->data[sta->top] = 0;???sta->top--;???//注意出棧后，須將新的棧頂元素的優先級記錄下來???priority = table[sta->data[sta->top] % 10];???i++;???continue;??}??//如果是左括號的話，直接壓棧??if (infix[i] == 40)??{???sta->top++;???sta->data[sta->top] = infix[i];???//注意壓棧后，須將新的棧頂元素的優先級記錄下來???priority = table[sta->data[sta->top] % 10];???i++;???continue;??}??//如果只是普通的運算符，則壓棧??if (infix[i] >= 42 && infix[i] <= 47)??{???//首先比較棧頂元素的優先級是否比入棧元素優先級要大???//如果是大于的話，則從棧頂將元素依次出棧后，把待入棧的元素壓棧???if (priority >= table[infix[i] % 10])???{????while (priority >= table[infix[i] % 10] && sta->data[sta->top] != 40)????{?????suffix[j] = sta->data[sta->top];?????sta->data[sta->top] = 0;?????sta->top--;?????//注意每次的出棧后，須將新的棧頂元素的優先級記錄下來用作比較?????priority = table[sta->data[sta->top] % 10];?????j++;????}????sta->top++;????sta->data[sta->top] = infix[i];????//注意壓棧后，須將新的棧頂元素的優先級記錄下來????priority = table[sta->data[sta->top] % 10];????i++;???}???else ???{????//這里主要處理負數的提取????if (infix[i] == 45 && sta->data[sta->top] == 40)????{?????b = 0;?????while (infix[i+1] >= '0' && infix[i+1] <= '9')?????{??????b = b * 10 + (infix[i+1] - '0');??????i++;?????}?????suffix[j] = b * -1;?????sta->data[sta->top] = 0;?????sta->top--;?????j++;?????i += 2;?????priority = table[sta->data[sta->top] % 10];?????continue;????}????sta->top++;????sta->data[sta->top] = infix[i];????//注意壓棧后，須將新的棧頂元素的優先級記錄下來????priority = table[sta->data[sta->top] % 10];????????i++;???}??}?}?//把棧中還存在的元素進行彈出?while (sta->top != -1)?{??suffix[j] = sta->data[sta->top];??sta->top--;??j++;?}?*length = j;}int suffix_to_result(Stack *sta, int *suffix, int length){?int??? i;?int??? j;?int??? result = 0;?for (i = 0; i < length; i++)?{??//循環遍歷后綴表達式，數字就直接壓棧，運算符就取棧頂兩個元素出來計算，并將結果壓棧??switch (suffix[i])??{??case 42:???result = sta->data[sta->top - 1] * sta->data[sta->top];???sta->top -= 1;???sta->data[sta->top] = result;???break;??case 43:???result = sta->data[sta->top - 1] + sta->data[sta->top];???sta->top -= 1;???sta->data[sta->top] = result;???break;??case 45:???result = sta->data[sta->top - 1] - sta->data[sta->top];???sta->top -= 1;???sta->data[sta->top] = result;???break;??case 47:???result = sta->data[sta->top - 1] / sta->data[sta->top];???sta->top -= 1;???sta->data[sta->top] = result;???break;??default:???sta->top++;???sta->data[sta->top] = suffix[i];???break;??}?}?return?? result;}//初始化棧空間void init(Stack *sta){?int???? i;?for (i = 0; i < MAXSIZE; i++)?{??sta->data[i] = 0;?}?sta->top = -1;}

???????????

給我老師的人工智能教程打call！http://blog.csdn.net/jiangjunshow

總結

以上是生活随笔為你收集整理的用栈解决四则运算问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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