데이터 구조 - 표현 식 값 구하 기
36452 단어 데이터 구조
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 #define STACK_INIT_SIZE 100
6 #define STACKINCREMENT 10
7 #define OVERFLOW -2
8 #define OK 1
9 #define ERROR 0
10
11 typedef char SElemType;
12 typedef int ElemType;
13
14 //
15 typedef struct {
16 SElemType *base;
17 SElemType *top;
18 int stacksize;
19 }SqStackOptr;//
20
21 typedef struct {
22 ElemType *base;
23 ElemType *top;
24 int stacksize;
25 }SqStackOpnd;//
26
27 //
28 int InitStackOptr(SqStackOptr *S);//
29 SElemType GetTopOptr(SqStackOptr *S);//
30 int PushOptr(SqStackOptr *S,SElemType e);//
31 int PopOptr(SqStackOptr *S,SElemType *e);//
32 int DestoryStackOptr(SqStackOptr *S);//
33 //
34 int InitStackOpnd(SqStackOpnd *S);//
35 ElemType GetTopOpnd(SqStackOpnd *S);//
36 int PushOpnd(SqStackOpnd *S,SElemType e);//
37 int PopOpnd(SqStackOpnd *S,SElemType *e);//
38 int DestoryStackOpnd(SqStackOpnd *S);//
39 //
40 ElemType EvaluateExpression(SqStackOptr *OPTR,SqStackOpnd *OPND);//
41 SElemType Precede(char topc,char c);//
42 ElemType Operate(SElemType a,SElemType theta,SElemType b);//
43 ElemType In(char c,char op[]);//
44
45 //
46 int InitStackOptr(SqStackOptr *S) {
47 S->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
48 if(!S->base) {
49 exit(OVERFLOW);
50 }
51 S->top = S->base;
52 S->stacksize = STACK_INIT_SIZE;
53 return OK;
54 }
55
56 int InitStackOpnd(SqStackOpnd *S) {
57 S->base = (ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
58 if(!S->base) {
59 exit(OVERFLOW);
60 }
61 S->top = S->base;
62 S->stacksize = STACK_INIT_SIZE;
63 return OK;
64 }
65
66 //
67 SElemType GetTopOptr(SqStackOptr *S) {
68 if(S->top == S->base) {
69 return ERROR;
70 }
71 return *(S->top-1);
72 }
73 ElemType GetTopOpnd(SqStackOpnd *S) {
74 if(S->top == S->base) {
75 return ERROR;
76 }
77 return *(S->top-1);
78 }
79
80 //
81 int PushOptr(SqStackOptr *S,SElemType e) {
82 if((S->top-S->base)>=S->stacksize) {
83 S->base = (SElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(SElemType));
84 if(!S->base) exit(OVERFLOW);
85 S->top = S->base + S->stacksize;
86 S->stacksize += STACKINCREMENT;
87 }
88 *S->top++ = e;
89 return OK;
90 }
91 int PushOpnd(SqStackOpnd *S,ElemType e) {
92 if((S->top-S->base)>=S->stacksize) {
93 S->base = (ElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType));
94 if(!S->base) exit(OVERFLOW);
95 S->top = S->base + S->stacksize;
96 S->stacksize += STACKINCREMENT;
97 }
98 *S->top++ = e;
99 return OK;
100 }
101
102 //
103 int PopOptr(SqStackOptr *S,SElemType *e) {
104 if(S->top == S->base) return ERROR;
105 *e = *--S->top;
106 return OK;
107 }
108 int PopOpnd(SqStackOpnd *S,ElemType *e) {
109 if(S->top == S->base) return ERROR;
110 *e = *--S->top;
111 return OK;
112 }
113
114 //
115 int DestoryStackOptr(SqStackOptr *S) {
116 S->top = S->base;
117 free(S->base);
118 S->top = NULL;
119 S->base = NULL;
120 return OK;
121 }
122 int DestoryStackOpnd(SqStackOpnd *S) {
123 S->top = S->base;
124 free(S->base);
125 S->top = NULL;
126 S->base = NULL;
127 return OK;
128 }
129 //
130 ElemType In(char c,char op[]) {
131 int i,f=0;
132 for(i=0; i<7; i++) {
133 if(c == op[i]) {
134 f = 1;
135 break;
136 }
137 }
138 if(f==0) return 0;
139 else return 1;
140 }
141 //
142 SElemType Precede(char topc,char c) {
143 if (topc=='+'||topc=='-') {
144 if(c=='+'||c=='-'||c==')'||c=='#') {
145 return '>';
146 } else {
147 return '<';
148 }
149 }
150
151 if (topc=='*'||topc=='/') {
152 if(c=='(') {
153 return '<';
154 } else {
155 return '>';
156 }
157 }
158
159 if (topc=='(') {
160 if(c==')') {
161 return '=';
162 } else {
163 return '<';
164 }
165 }
166
167 if (topc==')') {
168 return ')';
169 }
170
171 if (topc=='#') {
172 if(c=='#') {
173 return '=';
174 } else {
175 return '<';
176 }
177 }
178
179 }
180
181 ElemType Operate(ElemType a,SElemType theta,ElemType b) {
182 switch(theta) {
183 case '+':
184 return a+b;
185 break;
186 case '-':
187 return a-b;
188 break;
189 case '*':
190 return a*b;
191 break;
192 case '/':
193 return a/b;
194 break;
195 }
196 }
197 //
198 ElemType EvaluateExpression(SqStackOptr *OPTR,SqStackOpnd *OPND) {
199 // 。 OPTR OPND ，OP
200 SElemType c,theta,x;
201 ElemType a,b;
202 SElemType op[7] = {'+','-','*','/','(',')','#'};
203 InitStackOptr(OPTR);
204 InitStackOpnd(OPND);
205 PushOptr(OPTR,'#');
206 printf(" ：");
207 c = getchar();
208 while(c!='#'|| GetTopOptr(OPTR)!='#') {
209 if(!In(c,op)) {
210 PushOpnd(OPND,c-'0');
211 c = getchar();
212 } else {
213 switch(Precede(GetTopOptr(OPTR),c)) {
214 case '<'://
215 PushOptr(OPTR,c);
216 c = getchar();
217 break;
218 case '>'://
219 PopOptr(OPTR,&theta);
220 PopOpnd(OPND,&b);
221 PopOpnd(OPND,&a);
222 PushOpnd(OPND,Operate(a,theta,b));
223 break;
224 case '=':
225 PopOptr(OPTR,&x);
226 c = getchar();
227 break;
228 }
229 }
230 }
231 return GetTopOpnd(OPND);
232 }
233 int main()
234 {
235 SqStackOpnd OPND;
236 SqStackOptr OPTR;
237 int result;
238 result = EvaluateExpression(&OPTR,&OPND);
239 printf(" ：%d",result);
240 system("pause");
241 return 0;
242 }좋은 웹페이지 즐겨찾기
