*注：本人技術不咋的，就是拿代碼出來和大家看看，代碼漏洞百出，完全沒有優化，主要看氣質，是吧
學了數據結構——棧，當然少不了習題。習題中最難的也是最有意思的就是這個中綴表達式的計算了（可以算+-*/和^，當然也可以帶小括號）。搞了很久很久啊，終於搞出來的。簡單說一下程序原理：
因為中綴表達式基本沒法算（就算可以也肯定會超時），所以得把中綴表達式轉為後綴表達式。
程序分為兩步
第一步：將中綴表達式轉為後綴表達式
創建一個字符串，比如叫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辦法：
右鍵桌面：新建文本文件
雙擊打開新建文本文件.bat，輸入如下腳本：
@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
除了乘方沒法算，別的都一樣
呵呵，我不想多什麼了……
