【信息學奧賽一本通】第三部分_棧 ex1_4cale （中綴轉後綴7符號），信息學奧賽
其實這個中綴轉後綴是費了很大功夫的，明白算法後第一次實現花了近三小時ORZ
![]()
#include <stdio.h>
#include <string.h>
#include <ctype.h>
char Mstr[511],Msta[511] = {'@'},Bstr[511];
int sta[511];
const short list[4][4] = {{0,-1,1,1},{1,0,1,1},{1,1,1,-2},{-1,-1,2,1}};
int level (char c){
switch (c){
case '+':
case '-':return 0;break;
case '*':
case '/':return 1;break;
case '(':return 2;break;
case ')':return 3;
}
}
int main (){
// freopen ("中後6.in","r",stdin);
// freopen (".out","w",stdout);
_Bool flag = 1;
int i,Br = -1,Ma = 0;
gets (Mstr);
for (i = 0;Mstr[i-1]!='@';i++){
if (isdigit(Mstr[i])){
Bstr[++Br] = Mstr[i];
flag = 1;
}
else{
if (flag == 1){
Bstr[++Br] = ' ';
flag = 0;
}
int lr = level(Mstr[i]),la = level(Msta[Ma]);
int res;
if (Msta[Ma] == '@')
res = 1;
else if (Mstr[i] == '@')
res = -1;
else
res = list[lr][la];
if (res == 2){
Ma--;
continue;
}
do{
switch (res){
case 1:Msta[++Ma] = Mstr[i];break;
case -1:Bstr[++Br] = Msta[Ma--];res = list[lr][level(Msta[Ma])];break;
case -2:printf ("input error!");return 0;
}
if (res == 2)
Ma--;
}while (res == -1);
if (res == 0){
Bstr[++Br] = Msta[Ma];
Msta[Ma] = Mstr[i];
}
}
}
printf ("%s",Bstr);
return 0;
}
初版6符號
但還是邏輯性不強，而且感覺還是沒理解透，於是又作死花了近兩小時隔天打了一遍。用長變量名達到不需要注釋，邏輯性自認增強很多
![]()
1 #include <stdio.h>
2 #include <string.h>
3 #include <ctype.h>
4
5 char Mstr[32] = {0},Msta[32] = {0},Bstr[32] = {0};
6 int Bsta[32] = {0};
7 int MstrLen,BstrLen,MstaTop,BstrTop,BstaTop;
8
9 const short kind (char c){
10 switch (c){
11 case ')': return -1;
12 case '@': return 0;
13 case '+':
14 case '-': return 1;
15 case '*':
16 case '/': return 2;
17 case '(': return 3;
18 case '^': return 4;
19 }
20 }
21
22 void Mstr_Bsta (void){
23 gets (Mstr);
24 MstrLen = strlen (Mstr);
25 Mstr[MstrLen++] = '@';
26 MstaTop = BstrTop = -1;
27 Msta[++MstaTop] = '@';
28
29 int SpaceFlag,NoSmallerFlag;
30 int i;
31
32 for (i = 0;i<MstrLen;i++){
33 if (isdigit(Mstr[i])){
34 Bstr[++BstrTop] = Mstr[i];
35 SpaceFlag = 1;
36 }
37 else{
38 if (SpaceFlag == 1){
39 Bstr[++BstrTop] = ' ';
40 SpaceFlag = 0;
41 }
42
43 int KindMstr,KindMsta;
44 do{
45 NoSmallerFlag = 1;
46 KindMstr = kind(Mstr[i]);
47 KindMsta = kind(Msta[MstaTop]);
48
49 if (KindMstr>KindMsta || (KindMstr == 3 && KindMsta == 4) || (KindMsta == 3 && KindMstr!=-1))
50 Msta[++MstaTop] = Mstr[i];
51 else if (KindMstr == KindMsta){
52 Bstr[++BstrTop] = Msta[MstaTop];
53 Msta[MstaTop] = Mstr[i];
54 }
55 else{
56 if (KindMstr == -1 && KindMsta == 3){
57 --MstaTop;
58 break;
59 }
60 else
61 Bstr[++BstrTop] = Msta[MstaTop--];
62 NoSmallerFlag = 0;
63 }
64 }while (KindMstr<KindMsta && NoSmallerFlag == 0);
65 }
66 }
67 }
68
69 int PowerQuickly (int x,int n){ //快速冪
70 int ans = 1;
71
72 while (n>0){
73 if (n&1 == 1)
74 ans*=x;
75 n/=2;
76 x*=x;
77 }
78 return ans;
79 }
80
81 void Bsta_Count (void){
82 int i;
83
84 for (i = 0,BstaTop = 0;Bstr[i]!='@';){
85 if (isdigit(Bstr[i])){
86 int num = Bstr[i++]-'0';
87 while (Bstr[i]!=' ')
88 num = num*=10+Bstr[i++]-'0';
89 Bsta[++BstaTop] = num;
90 i++;
91 }
92 else{
93 switch (Bstr[i++]){
94 case '+': Bsta[BstaTop-1] += Bsta[BstaTop--];break;
95 case '-': Bsta[BstaTop-1] -= Bsta[BstaTop--];break;
96 case '*': Bsta[BstaTop-1] *= Bsta[BstaTop--];break;
97 case '/': Bsta[BstaTop-1] /= Bsta[BstaTop--];break;
98 case '^': Bsta[BstaTop-1] = PowerQuickly(Bsta[BstaTop-1],Bsta[BstaTop]); BstaTop--;
99 }
100 }
101 }
102 }
103
104 int main (){
105 Mstr_Bsta ();
106 Bsta_Count ();
107 printf ("%d",Bsta[BstaTop]);
108
109 return 0;
110 }
View Code
