Download code

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 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Shunting_yard_algorithm_(C)?oldid=18970
 14 */
 15 
 16 
 17 #include<stdlib.h>
 18 #include<stdio.h>
 19 #include<ctype.h>
 20 
 21 #define MAXOPSTACK 64
 22 #define MAXNUMSTACK 64
 23 
 24 int eval_uminus(int a1, int a2) 
 25 {
 26 	return -a1;
 27 }
 28 int eval_exp(int a1, int a2)
 29 {
 30 	return a2<0 ? 0 : (a2==0?1:a1*eval_exp(a1, a2-1));
 31 }
 32 int eval_mul(int a1, int a2) 
 33 {
 34 	return a1*a2;
 35 }
 36 int eval_div(int a1, int a2) 
 37 {
 38 	if(!a2) {
 39 		fprintf(stderr, "ERROR: Division by zero\n");
 40 		exit(EXIT_FAILURE);
 41 	}
 42 	return a1/a2;
 43 }
 44 int eval_mod(int a1, int a2) 
 45 {
 46 	if(!a2) {
 47 		fprintf(stderr, "ERROR: Division by zero\n");
 48 		exit(EXIT_FAILURE);
 49 	}
 50 	return a1%a2;
 51 }
 52 int eval_add(int a1, int a2) 
 53 {
 54 	return a1+a2;
 55 }
 56 int eval_sub(int a1, int a2) 
 57 {
 58 	return a1-a2;
 59 }
 60 
 61 
 62 enum {ASSOC_NONE=0, ASSOC_LEFT, ASSOC_RIGHT};
 63 
 64 struct op_s {
 65 	char op;
 66 	int prec;
 67 	int assoc;
 68 	int unary;
 69 	int (*eval)(int a1, int a2);
 70 } ops[]={
 71 	{'_', 10, ASSOC_RIGHT, 1, eval_uminus},
 72 	{'^', 9, ASSOC_RIGHT, 0, eval_exp},
 73 	{'*', 8, ASSOC_LEFT, 0, eval_mul},
 74 	{'/', 8, ASSOC_LEFT, 0, eval_div},
 75 	{'%', 8, ASSOC_LEFT, 0, eval_mod},
 76 	{'+', 5, ASSOC_LEFT, 0, eval_add},
 77 	{'-', 5, ASSOC_LEFT, 0, eval_sub},
 78 	{'(', 0, ASSOC_NONE, 0, NULL},
 79 	{')', 0, ASSOC_NONE, 0, NULL}
 80 };
 81 
 82 struct op_s *getop(char ch)
 83 {
 84 	int i;
 85 	for(i=0; i<sizeof ops/sizeof ops[0]; ++i) {
 86 		if(ops[i].op==ch) return ops+i;
 87 	}
 88 	return NULL;
 89 }
 90 
 91 struct op_s *opstack[MAXOPSTACK];
 92 int nopstack=0;
 93 
 94 int numstack[MAXNUMSTACK];
 95 int nnumstack=0;
 96 
 97 void push_opstack(struct op_s *op)
 98 {
 99 	if(nopstack>MAXOPSTACK-1) {
100 		fprintf(stderr, "ERROR: Operator stack overflow\n");
101 		exit(EXIT_FAILURE);
102 	}
103 	opstack[nopstack++]=op;
104 }
105 
106 struct op_s *pop_opstack()
107 {
108 	if(!nopstack) {
109 		fprintf(stderr, "ERROR: Operator stack empty\n");
110 		exit(EXIT_FAILURE);
111 	}
112 	return opstack[--nopstack];
113 }
114 
115 void push_numstack(int num)
116 {
117 	if(nnumstack>MAXNUMSTACK-1) {
118 		fprintf(stderr, "ERROR: Number stack overflow\n");
119 		exit(EXIT_FAILURE);
120 	}
121 	numstack[nnumstack++]=num;
122 }
123 
124 int pop_numstack()
125 {
126 	if(!nnumstack) {
127 		fprintf(stderr, "ERROR: Number stack empty\n");
128 		exit(EXIT_FAILURE);
129 	}
130 	return numstack[--nnumstack];
131 }
132 
133 
134 void shunt_op(struct op_s *op)
135 {
136 	struct op_s *pop;
137 	int n1, n2;
138 	if(op->op=='(') {
139 		push_opstack(op);
140 		return;
141 	} else if(op->op==')') {
142 		while(nopstack>0 && opstack[nopstack-1]->op!='(') {
143 			pop=pop_opstack();
144 			n1=pop_numstack();
145 			if(pop->unary) push_numstack(pop->eval(n1, 0));
146 			else {
147 				n2=pop_numstack();
148 				push_numstack(pop->eval(n2, n1));
149 			}
150 		}
151 		if(!(pop=pop_opstack()) || pop->op!='(') {
152 			fprintf(stderr, "ERROR: Stack error. No matching \'(\'\n");
153 			exit(EXIT_FAILURE);
154 		}
155 		return;
156 	}
157 
158 	if(op->assoc==ASSOC_RIGHT) {
159 		while(nopstack && op->prec<opstack[nopstack-1]->prec) {
160 			pop=pop_opstack();
161 			n1=pop_numstack();
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 	} else {
169 		while(nopstack && op->prec<=opstack[nopstack-1]->prec) {
170 			pop=pop_opstack();
171 			n1=pop_numstack();
172 			if(pop->unary) push_numstack(pop->eval(n1, 0));
173 			else {
174 				n2=pop_numstack();
175 				push_numstack(pop->eval(n2, n1));
176 			}
177 		}
178 	}
179 	push_opstack(op);
180 }
181 
182 
183 int main(int argc, char *argv[])
184 {
185 	char *expr;
186 	char *tstart=NULL;
187 	struct op_s startop={'X', 0, ASSOC_NONE, 0, NULL};	/* Dummy operator to mark start */
188 	struct op_s *op=NULL;
189 	int n1, n2;
190 	struct op_s *lastop=&startop;
191 
192 	if(argc<2) {
193 		fprintf(stderr, "Usage: %s <expression>\n", argv[0]);
194 		return EXIT_FAILURE;
195 	}
196 
197 	for(expr=argv[1]; *expr; ++expr) {
198 		if(!tstart) {
199 
200 			if((op=getop(*expr))) {
201 				if(lastop && (lastop==&startop || lastop->op!=')')) {
202 					if(op->op=='-') op=getop('_');
203 					else if(op->op!='(') {
204 						fprintf(stderr, "ERROR: Illegal use of binary operator (%c)\n", op->op);
205 						exit(EXIT_FAILURE);
206 					}
207 				}
208 				shunt_op(op);
209 				lastop=op;
210 			} else if(isdigit(*expr)) tstart=expr;
211 			else if(!isspace(*expr)) {
212 				fprintf(stderr, "ERROR: Syntax error\n");
213 				return EXIT_FAILURE;
214 			}
215 		} else {
216 			if(isspace(*expr)) {
217 				push_numstack(atoi(tstart));
218 				tstart=NULL;
219 				lastop=NULL;
220 			} else if((op=getop(*expr))) {
221 				push_numstack(atoi(tstart));
222 				tstart=NULL;
223 				shunt_op(op);
224 				lastop=op;
225 			} else if(!isdigit(*expr)) {
226 				fprintf(stderr, "ERROR: Syntax error\n");
227 				return EXIT_FAILURE;
228 			}
229 		}
230 	}
231 	if(tstart) push_numstack(atoi(tstart));
232 
233 	while(nopstack) {
234 		op=pop_opstack();
235 		n1=pop_numstack();
236 		if(op->unary) push_numstack(op->eval(n1, 0));
237 		else {
238 			n2=pop_numstack();
239 			push_numstack(op->eval(n2, n1));
240 		}
241 	}
242 	if(nnumstack!=1) {
243 		fprintf(stderr, "ERROR: Number stack has %d elements after evaluation. Should be 1.\n", nnumstack);
244 		return EXIT_FAILURE;
245 	}
246 	printf("%d\n", numstack[0]);
247 
248 	return EXIT_SUCCESS;
249 }
250 
251 


hijacker
hijacker
hijacker
hijacker