Download code

From LiteratePrograms

Jump to: navigation, search

Back to Shunting_yard_algorithm_(C)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

shunt.c

  1 /* Copyright (c) 2010 the authors listed at the following URL, and/or
  2 the authors of referenced articles or incorporated external code:
  3 http://en.literateprograms.org/Shunting_yard_algorithm_(C)?action=history&offset=20080201043325
  4 
  5 Permission is hereby granted, free of charge, to any person obtaining
  6 a copy of this software and associated documentation files (the
  7 "Software"), to deal in the Software without restriction, including
  8 without limitation the rights to use, copy, modify, merge, publish,
  9 distribute, sublicense, and/or sell copies of the Software, and to
 10 permit persons to whom the Software is furnished to do so, subject to
 11 the following conditions:
 12 
 13 The above copyright notice and this permission notice shall be
 14 included in all copies or substantial portions of the Software.
 15 
 16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 17 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 18 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 19 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 20 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 21 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 22 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 23 
 24 Retrieved from: http://en.literateprograms.org/Shunting_yard_algorithm_(C)?oldid=12454
 25 */
 26 
 27 
 28 #include<stdlib.h>

 29 #include<stdio.h>

 30 #include<ctype.h>

 31 
 32 #define MAXOPSTACK 64

 33 #define MAXNUMSTACK 64

 34 
 35 int eval_uminus(int a1, int a2) 
 36 {
 37 	return -a1;
 38 }
 39 int eval_exp(int a1, int a2)
 40 {
 41 	return a2<0 ? 0 : (a2==0?1:a1*eval_exp(a1, a2-1));
 42 }
 43 int eval_mul(int a1, int a2) 
 44 {
 45 	return a1*a2;
 46 }
 47 int eval_div(int a1, int a2) 
 48 {
 49 	if(!a2) {
 50 		fprintf(stderr, "ERROR: Division by zero\n");
 51 		exit(EXIT_FAILURE);
 52 	}
 53 	return a1/a2;
 54 }
 55 int eval_mod(int a1, int a2) 
 56 {
 57 	if(!a2) {
 58 		fprintf(stderr, "ERROR: Division by zero\n");
 59 		exit(EXIT_FAILURE);
 60 	}
 61 	return a1%a2;
 62 }
 63 int eval_add(int a1, int a2) 
 64 {
 65 	return a1+a2;
 66 }
 67 int eval_sub(int a1, int a2) 
 68 {
 69 	return a1-a2;
 70 }
 71 
 72 
 73 
 74 enum {ASSOC_NONE=0, ASSOC_LEFT, ASSOC_RIGHT};
 75 
 76 struct op_s {
 77 	char op;
 78 	int prec;
 79 	int assoc;
 80 	int unary;
 81 	int (*eval)(int a1, int a2);
 82 } ops[]={
 83 	{'_', 10, ASSOC_RIGHT, 1, eval_uminus},
 84 	{'^', 9, ASSOC_RIGHT, 0, eval_exp},
 85 	{'*', 8, ASSOC_LEFT, 0, eval_mul},
 86 	{'/', 8, ASSOC_LEFT, 0, eval_div},
 87 	{'%', 8, ASSOC_LEFT, 0, eval_mod},
 88 	{'+', 5, ASSOC_LEFT, 0, eval_add},
 89 	{'-', 5, ASSOC_LEFT, 0, eval_sub},
 90 	{'(', 0, ASSOC_NONE, 0, NULL},
 91 	{')', 0, ASSOC_NONE, 0, NULL}
 92 };
 93 
 94 struct op_s *getop(char ch)
 95 {
 96 	int i;
 97 	for(i=0; i<sizeof ops/sizeof ops[0]; ++i) {
 98 		if(ops[i].op==ch) return ops+i;
 99 	}
100 	return NULL;
101 }
102 
103 
104 struct op_s *opstack[MAXOPSTACK];
105 int nopstack=0;
106 
107 int numstack[MAXNUMSTACK];
108 int nnumstack=0;
109 
110 void push_opstack(struct op_s *op)
111 {
112 	if(nopstack>MAXOPSTACK-1) {
113 		fprintf(stderr, "ERROR: Operator stack overflow\n");
114 		exit(EXIT_FAILURE);
115 	}
116 	opstack[nopstack++]=op;
117 }
118 
119 struct op_s *pop_opstack()
120 {
121 	if(!nopstack) {
122 		fprintf(stderr, "ERROR: Operator stack empty\n");
123 		exit(EXIT_FAILURE);
124 	}
125 	return opstack[--nopstack];
126 }
127 
128 void push_numstack(int num)
129 {
130 	if(nnumstack>MAXNUMSTACK-1) {
131 		fprintf(stderr, "ERROR: Number stack overflow\n");
132 		exit(EXIT_FAILURE);
133 	}
134 	numstack[nnumstack++]=num;
135 }
136 
137 int pop_numstack()
138 {
139 	if(!nnumstack) {
140 		fprintf(stderr, "ERROR: Number stack empty\n");
141 		exit(EXIT_FAILURE);
142 	}
143 	return numstack[--nnumstack];
144 }
145 
146 
147 
148 void shunt_op(struct op_s *op)
149 {
150 	struct op_s *pop;
151 	int n1, n2;
152 
153 	if(op->op=='(') {
154 		push_opstack(op);
155 		return;
156 
157 	} else if(op->op==')') {
158 		while(nopstack>0 && opstack[nopstack-1]->op!='(') {
159 			pop=pop_opstack();
160 			n1=pop_numstack();
161 
162 			if(pop->unary) push_numstack(pop->eval(n1, 0));
163 			else {
164 				n2=pop_numstack();
165 				push_numstack(pop->eval(n2, n1));
166 			}
167 		}
168 
169 		if(!(pop=pop_opstack()) || pop->op!='(') {
170 			fprintf(stderr, "ERROR: Stack error. No matching \'(\'\n");
171 			exit(EXIT_FAILURE);
172 		}
173 		return;
174 	}
175 
176 	if(op->assoc==ASSOC_RIGHT) {
177 		while(nopstack && op->prec<opstack[nopstack-1]->prec) {
178 			pop=pop_opstack();
179 			n1=pop_numstack();
180 			if(pop->unary) push_numstack(pop->eval(n1, 0));
181 			else {
182 				n2=pop_numstack();
183 				push_numstack(pop->eval(n2, n1));
184 			}
185 		}
186 	} else {
187 		while(nopstack && op->prec<=opstack[nopstack-1]->prec) {
188 			pop=pop_opstack();
189 			n1=pop_numstack();
190 			if(pop->unary) push_numstack(pop->eval(n1, 0));
191 			else {
192 				n2=pop_numstack();
193 				push_numstack(pop->eval(n2, n1));
194 			}
195 		}
196 	}
197 	push_opstack(op);
198 }
199 
200 
201 
202 int main(int argc, char *argv[])
203 {
204 	char *expr;
205 	char *tstart=NULL;
206 	struct op_s startop={'X', 0, ASSOC_NONE, 0, NULL};	/* Dummy operator to mark start */
207 	struct op_s *op=NULL;
208 	int n1, n2;
209 	struct op_s *lastop=&startop;
210 
211 	if(argc<2) {
212 		fprintf(stderr, "Usage: %s <expression>\n", argv[0]);
213 		return EXIT_FAILURE;
214 	}
215 
216 	for(expr=argv[1]; *expr; ++expr) {
217 		if(!tstart) {
218 
219 			if((op=getop(*expr))) {
220 
221 				if(lastop && (lastop==&startop || lastop->op!=')')) {
222 					if(op->op=='-') op=getop('_');
223 					else if(op->op!='(') {
224 						fprintf(stderr, "ERROR: Illegal use of binary operator (%c)\n", op->op);
225 						exit(EXIT_FAILURE);
226 					}
227 				}
228 				shunt_op(op);
229 				lastop=op;
230 			} else if(isdigit(*expr)) tstart=expr;
231 			else if(!isspace(*expr)) {
232 				fprintf(stderr, "ERROR: Syntax error\n");
233 				return EXIT_FAILURE;
234 			}
235 		} else {
236 			if(isspace(*expr)) {
237 				push_numstack(atoi(tstart));
238 				tstart=NULL;
239 				lastop=NULL;
240 			} else if((op=getop(*expr))) {
241 				push_numstack(atoi(tstart));
242 				tstart=NULL;
243 				shunt_op(op);
244 				lastop=op;
245 			} else if(!isdigit(*expr)) {
246 				fprintf(stderr, "ERROR: Syntax error\n");
247 				return EXIT_FAILURE;
248 			}
249 		}
250 	}
251 	if(tstart) push_numstack(atoi(tstart));
252 
253 
254 	while(nopstack) {
255 		op=pop_opstack();
256 		n1=pop_numstack();
257 		if(op->unary) push_numstack(op->eval(n1, 0));
258 		else {
259 			n2=pop_numstack();
260 			push_numstack(op->eval(n2, n1));
261 		}
262 	}
263 
264 	if(nnumstack!=1) {
265 		fprintf(stderr, "ERROR: Number stack has %d elements after evaluation. Should be 1.\n", nnumstack);
266 		return EXIT_FAILURE;
267 	}
268 	printf("%d\n", numstack[0]);
269 
270 	return EXIT_SUCCESS;
271 }
272 
273 
274 
275


Retrieved from "http://en.literateprograms.org/Special:Downloadcode"
Views
Personal tools