各位看官們,大家好,前幾回中咱們說(shuō)了堆棧的原理,并且舉了實(shí)際的例子進(jìn)行解說(shuō),這一回咱們說(shuō)的例 子是:表達(dá)式求值。表達(dá)式求值和上一回中說(shuō)的括號(hào)匹配一樣,都使用了堆棧的原理,大家可以從例子中 看出來(lái),所以我們把它們放在一起。閑話休提,言歸正轉(zhuǎn)。讓我們一起talk C栗子吧!
看官們,我們?cè)谶@里說(shuō)的表達(dá)式為包含加,減,乘除的四則運(yùn)算表達(dá)式。例如:1+23-4/5就是一個(gè)四則運(yùn) 算表達(dá)式。這個(gè)表達(dá)式中,運(yùn)算符在數(shù)字中間,所以我們叫它中綴表達(dá)式,這也是符合我們思維的一種表 現(xiàn)形式,不過(guò),計(jì)算機(jī)就不理解中綴表達(dá)式了,因?yàn)樗鼪](méi)有辦法像我們一樣先進(jìn)行乘除運(yùn)算,然后再進(jìn)行 加減運(yùn)算,所以我們需要把中綴表達(dá)式轉(zhuǎn)換成計(jì)算機(jī)能理解的后綴表達(dá)式。“什么是后綴表達(dá)式”,這時(shí)候 臺(tái)下有看官在提問(wèn)了,看官莫急,所謂的后綴表達(dá)式就是運(yùn)算符在數(shù)字后面。例如:" 1+23-6/3 "這個(gè)中綴 表達(dá)式可以為" 123*+63/- "這種后綴表達(dá)式.
表達(dá)式求值有兩個(gè)大的步驟:
這兩個(gè)大的步驟中還有一些小的步驟,接下來(lái)我們?cè)敿?xì)說(shuō)說(shuō)這些小步驟。在說(shuō)之前,我首先說(shuō)明一個(gè)概念: 優(yōu)先級(jí)。優(yōu)先級(jí)代表著先后順序,舉一個(gè)日常為生活中的例子:排隊(duì)買東西的時(shí)候,排在隊(duì)列前面的人, 比排在隊(duì)列后面人具有優(yōu)先買東西的權(quán)利,我們就可以說(shuō):排在隊(duì)列前面的人買東西的優(yōu)先級(jí)高。優(yōu)先級(jí) 在表達(dá)式運(yùn)算過(guò)程中體現(xiàn)為:乘法和除法的優(yōu)先級(jí)比加法和減法的優(yōu)先級(jí)高。也就是我們通常說(shuō)的先乘除 后加減,這個(gè)內(nèi)容我就不多說(shuō)了,大家在小學(xué)數(shù)學(xué)中都學(xué)過(guò)。我們?cè)诒磉_(dá)式求值過(guò)程中把中綴表達(dá)式轉(zhuǎn)換 為后綴表達(dá)式也與優(yōu)先級(jí)有關(guān),因?yàn)楹缶Y表達(dá)式可以去掉運(yùn)算符的優(yōu)先級(jí)。沒(méi)有優(yōu)先級(jí)了,計(jì)算機(jī)就能理 解后綴表達(dá)式并對(duì)其進(jìn)行相關(guān)的運(yùn)算。
中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的步驟如下:
對(duì)后綴表達(dá)式求值的步驟如下:
看官們,詳細(xì)的代碼如下,請(qǐng)大家參考:
1 /* **************************
2 * Head file of Expression Evaluation
3 * *************************/
4 #ifndef EXPRESSION_EVALUATION_H
5 #define EXPRESSION_EVALUATION_H
6
7 #include<stdio.h>
8 #include<stdlib.h>
9
10 #define SUCCESS 0
11 #define FAILE 1
12
13 #define LEN 20 //棧的長(zhǎng)度先定義為5,需要時(shí)可自行修改
14
15 typedef char StackElmt; //把char當(dāng)作棧中元素的類型,實(shí)際中可以使用其它的類型或者自己定義一個(gè)元素類型
16 typedef struct _Stack{
17 StackElmt *base;
18 StackElmt *top;
19 int size;
20 }Stack;
21
22 StackElmt STACK[LEN+1] = {0}; //順序存儲(chǔ)方式的棧,防止數(shù)組越界,最后一個(gè)位置不放元素
23
24 //聲明函數(shù)原型,這里有入棧和出棧操的函數(shù)
25 int StackInit(Stack *s);
26 int StackDestroy(Stack *s);
27 int StackPrint(Stack *s);
28 int StackPush(Stack *s, StackElmt e);
29 int StackPop(Stack *s, StackElmt *e);
30
31 #endif /* EXPRESSION_EVALUATION_H */
1 /* **************************
2 * Soure file of Expression Evaluation
3 * *************************/
4
5 #include"ExpressionEvaluation.h"
6
7 //實(shí)現(xiàn)棧相關(guān)的函數(shù),為了方便,放到了主函數(shù)所在的文件中,最好是單獨(dú)建立實(shí)現(xiàn)函數(shù)的源文件
8 //初始化中棧
9 int StackInit(Stack *s)
10 {
11 if(NULL == s)
12 return FAILE;
13
14 s->top = s->base = &STACK[0];
15 s->size = 0;
16
17 }
18 int StackDestroy(Stack *s)
19 {
20 int i =0;
21
22 if(NULL == s)
23 return FAILE;
24
25 while(i<LEN)
26 {
27 STACK[i] = 0;
28 i++;
29 }
30 s->top = s->base = NULL;
31 s->size = 0;
32 }
33 //輸出棧中存放的元素
34 int StackPrint(Stack *s)
35 {
36 int index = 0;
37
38 if(NULL == s)
39 return FAILE;
40
41 if(s->size == 0)
42 {
43 printf("the Stack is empty,there is not any element \n");
44 return FAILE;
45 }
46
47 while(index < (s->size))
48 {
49 printf("%d ",*((s->base)+index) );
50 index++;
51 }
52
53 printf("\n ");
54
55 return SUCCESS;
56 }
57
58 //入棧函數(shù),top指向棧頂,先把元素入棧,然后向棧頂移動(dòng)一位
59 int StackPush(Stack *s, StackElmt e)
60 {
61 if(NULL == s)
62 return FAILE;
63
64 if(s->size >= LEN)
65 {
66 printf("the Stack is full \n");
67 return FAILE;
68 }
69
70 *(s->top) = e;
71 (s->top)++;
72 (s->size)++;
73
74 return SUCCESS;
75 }
76
77 //出棧函數(shù),top先向棧底移到一位,然后移出當(dāng)前它所指向的元素
78 int StackPop(Stack *s, StackElmt *e)
79 {
80 if(NULL == s)
81 return FAILE;
82
83 if(s->size == 0)
84 {
85 //printf("the Stack is empty \n");
86 return FAILE;
87 }
88
89 (s->top)--;
90 *e = *(s->top);
91 (s->size)--;
92
93 return SUCCESS;
94 }
95
96 int main()
97 {
98 char ch = '\0';
99 char str[2];
100 char *a1= "1+2*3-6/3"; // 存放中綴表達(dá)式
101 //char *a1="1+2+3*4";
102 char a2[LEN]={'\0'}; // 存放后綴表達(dá)式
103 Stack s;
104 int i,j;
105 int a,b;
106 int res = 0;
107 int stack[LEN] ={0};
108
109 i = j = a = b = 0;
110 StackInit(&s);
111
112 while(*(a1+i) != '\0') //遍歷中綴表達(dá)式
113 {
114 printf("%c",*(a1+i));
115
116 if(*(a1+i) == '+' || *(a1+i) == '-')
117 {
118 if(s.size != 0)
119 {
120 while( s.size >= 0 && !StackPop(&s,&ch))
121 {
122 *(a2+j) = ch;
123 ch = '\0';
124 j++;
125 }
126 StackPush( &s,*(a1+i) );
127 }
128 else
129 StackPush(&s,*(a1+i));
130 }
131 else if( *(a1+i) == '*' || *(a1+i) == '/')
132 {
133 if(s.size != 0)
134 {
135 if(!StackPop(&s,&ch))
136 {
137 if(ch == '+' || ch == '-')
138 {
139 StackPush(&s,ch);
140 StackPush( &s,*(a1+i) );
141 }
142 else
143 {
144 StackPush(&s,ch);
145 while( !StackPop(&s,&ch) && (ch == '*' || ch == '/') )
146 {
147 *(a2+j) = ch;
148 ch = '\0';
149 j++;
150 }
151 StackPush( &s,*(a1+i) );
152 }
153 }
154 }
155 else
156 StackPush(&s,*(a1+i));
157 }
158 else //從中綴表達(dá)式中讀取的字符是數(shù)字,保存到數(shù)組中
159 {
160 *(a2+j) = *(a1+i);
161 j++;
162 }
163
164 i++;
165 }
166
167 while( s.size >= 0 && !StackPop(&s,&ch)) //棧中還有運(yùn)算符的話,需要全部取出,放到后綴表達(dá)式中
168 {
169 *(a2+j) = ch;
170 ch = '\0';
171 j++;
172 }
173 *(a2+j) = '\0';
174
175 i=j=0;
176 StackDestroy(&s);
177 StackInit(&s);
178
179 while(*(a2+i) != '\0') //遍歷后綴表達(dá)式
180 {
181 if(*(a2+i) == '+')
182 {
183 j--;
184 a = stack[j];
185 j--;
186 b = stack[j];
187
188 stack[j]= a+b;
189 j++;
190 }
191 else if(*(a2+i) == '-')
192 {
193 j--;
194 a = stack[j];
195 j--;
196 b = stack[j];
197
198 stack[j]= b-a;
199 j++;
200 }
201 else if(*(a2+i) == '*')
202 {
203 j--;
204 a = stack[j];
205 j--;
206 b = stack[j];
207
208 stack[j]= a*b;
209 j++;
210 }
211 else if(*(a2+i) == '/')
212 {
213 j--;
214 a = stack[j];
215 j--;
216 b = stack[j];
217
218 stack[j]= b/a;
219 j++;
220 }
221 else
222 {
223 str[0] =*(a2+i);
224 str[1] ='\0';
225 stack[j]= atoi(str);
226 j++;
227 }
228
229 i++;
230 }
231 res =stack[0];
232
233 printf(" = %d ",res);
234 printf("\n");
235 return SUCCESS;
236 }
從代碼中可以看到,我們用了兩次棧,一次是在中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式的過(guò)程中,棧用來(lái)存放運(yùn)算 符。另外一次是在后綴表達(dá)式求值的過(guò)程中,棧用來(lái)存放參與運(yùn)算的數(shù)字。
各位看官,關(guān)于表達(dá)式求值的例子咱們就說(shuō)到這里。欲知后面還有什么例子,且聽(tīng)下回分解。