C語言數據結構之棧：中綴表達式的計算

*註：本人技術不咋的，就是拿代碼出來和大家看看，代碼漏洞百出，完全沒有優化，主要看氣質，是吧

學了數據結構——棧，當然少不了習題。習題中最難的也是最有意思的就是這個中綴表達式的計算了（可以算+-*/和^，當然也可以帶小括弧）。搞了很久很久啊，終於搞出來的。簡單說一下程式原理：

因為中綴表達式基本沒法算（就算可以也肯定會超時），所以得把中綴表達式轉為尾碼表達式。

程式分為兩步

第一步：將中綴表達式轉為尾碼表達式

創建一個字元串，比如叫get，用於存儲尾碼表達式

先是輸入一個字元串，逐一讀取單個字元，當是數字則直接存入get，如果是操作符則：

創建棧，比如叫chas

while迴圈 當棧頂操作符優先順序大於或等於當前操作符則彈出並把棧頂元素賦值給get 直到發現優先順序小於當前操作符的棧頂的操作符，小於當前操作符的那個棧頂操作符不彈出 然後將當前操作符壓入棧內

噹噹前操作符為'('則直接壓入棧內

噹噹前操作符為')'則while迴圈 彈出棧頂操作符並賦值給get直到彈出的是'(' （ '('只彈出不賦值 ） 註意，')'不壓入棧中

第二部：計算get

創建int型數組棧，比如ints

逐個讀入get

當讀到數字壓入ints

當讀到操作符則彈出兩個ints的棧頂元素，併進行相應計算，將計算得到的值壓入棧ints中

最後讀完get時，ints數組只剩下一個元素了，輸出。

自個兒寫的稀巴爛源碼(c):

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <math.h>
  4 
  5 int ints[10000];
  6 int intt;//ints的top 
  7 char chas[10000];
  8 int chat;//chas的top 
  9 int i=0, ii=1;
 10 char c;
 11 char get[10000];//輸入的中綴表達式 
 12 char get2[10000];//計算得出的尾碼表達式 
 13 
 14 void intpush(x)//整型棧壓棧 
 15 {
 16     intt++;    ints[intt]=x;
 17 }
 18 void chapush(x)//字元型棧壓棧 
 19 {
 20     chat++;    chas[chat]=x;
 21 }
 22 int intpop()//整型棧彈出 
 23 {
 24     intt--;    return ints[intt+1];
 25 }
 26 char chapop()//字元型棧彈出 
 27 {
 28     chat--;    return chas[chat+1];
 29 }
 30 void intadd(int x)//整型棧棧頂元素加入新的個位數字 
 31 {
 32     ints[intt]*=10;    ints[intt]+=x;
 33 }
 34 
 35 int find()//get2加入操作符 
 36 {
 37     c=chapop();
 38     get2[ii]=' ';
 39     get2[ii+1]=c;
 40     ii+=2;
 41     if(chat==0) return 0;
 42     return 1;
 43 }
 44 
 45 int main()
 46 {
 47     intt=0;    chat=0;
 48     gets(get);
 49     int lengets=strlen(get);
 50     for(i=0;i<=lengets-1;i++)//逐個讀取輸入的中綴表達式 
 51     {
 52         if (isdigit(get[i]))//當get[i]為數字時 
 53         {
 54             get2[ii]=get[i];
 55             ii++;
 56         }
 57         else
 58         {
 59             if(get[i]=='(')chapush('(');
 60             if(get[i]=='^')chapush('^');
 61             if(get[i]==')')
 62             {
 63                 c=chapop();
 64                 while(c!='(')
 65                 {
 66                     get2[ii]=' ';
 67                     get2[ii+1]=c;
 68                     ii+=2;
 69                     c=chapop();
 70                 }
 71             }
 72             if(get[i]=='+')
 73             {
 74                 while(chas[chat]=='+'||chas[chat]=='-'||chas[chat]=='*'||chas[chat]=='/'||chas[chat]=='^')
 75                 {
 76                     if(find()==0)break;
 77                 }
 78                 chapush('+');
 79             }
 80             if(get[i]=='-')
 81             {
 82                 while(chas[chat]=='+'||chas[chat]=='-'||chas[chat]=='*'||chas[chat]=='/'||chas[chat]=='^')
 83                 {
 84                     if(find()==0)break;
 85                 }
 86                 chapush('-');
 87             }
 88             if(get[i]=='*')
 89             {
 90                 while(chas[chat]=='*'||chas[chat]=='/'||chas[chat]=='^')
 91                 {
 92                     if(find()==0)break;
 93                 }
 94                 chapush('*');
 95             }
 96             if(get[i]=='/')
 97             {
 98                 while(chas[chat]=='*'||chas[chat]=='/'||chas[chat]=='^')
 99                 {
100                     if(find()==0)break;
101                 }
102                 chapush('/');
103             }
104             get2[ii]=' ';
105             ii++;
106         }
107         
108     }
109     while(chat>0)//輸出棧內剩餘的操作符 
110     {
111         int c=chapop();
112         get2[ii]=' ';
113         get2[ii+1]=c;
114         ii+=2;
115     }
116     get2[ii]='@';//加入結束符 
117     i=1;
118     while(get2[i]!='@')//當看到結束符停止計算 
119     {
120         if(get2[i]=='+'||get2[i]=='-'||get2[i]=='*'||get2[i]=='/'||get2[i]=='^')
121         {
122             int a=intpop();int b=intpop();int c;
123             if(get2[i]=='+') c=a+b;
124             if(get2[i]=='-') c=b-a;
125             if(get2[i]=='*') c=a*b;
126             if(get2[i]=='/') c=b/a;
127             if(get2[i]=='^') c=pow(b,a);
128             intpush(c);
129         }
130         else
131         {
132             if(get2[i]!=' ')
133             {
134                 intpush(get2[i]-48);
135                 ii=1;
136                 while(get2[i+ii]!=' ')
137                 {
138                     intadd(get2[i+ii]-48);
139                     ii++;
140                 }
141                 i+=ii-1;
142             }
143         }
144         i++;
145     }
146     printf("%d",ints[1]);
147     return 0;
148 }

樣例輸入：

1+(3+2)*(7^2+6*9)/(2)

樣例輸出：

258

好了，就寫到這了。（原題：信息學奧賽一本通C++版 數據結構 棧 上機練習4 calc）//別問我為什麼C++的書的練習我寫的是C，我不會告訴你是因為那樣文件名可以少打兩個p

對了，再說一下，其實這玩意完全沒必要寫這麼長，最NB辦法：

右鍵桌面：新建文本文件

雙擊打開新建文本文件.txt，輸入如下腳本：

@echo off
set /p get=
set /a ans=%get%
echo %ans%
pause
exit::可以不要這句exit

右鍵新建文本文件，重命名為：calc.bat

雙擊打開

樣例輸入：

1+(3+2)*(7*7+6*9)/(2)

樣例輸出：

258

除了乘方沒法算，別的都一樣

呵呵，我不想多什麼了……