1 /* Copyright (c) 2001 Aaron Lehmann <aaronl@vitelus.com>
3 Permission is hereby granted, free of charge, to any person obtaining
4 a copy of this software and associated documentation files (the
5 "Software"), to deal in the Software without restriction, including
6 without limitation the rights to use, copy, modify, merge, publish,
7 distribute, sublicense, and/or sell copies of the Software, and to
8 permit persons to whom the Software is furnished to do so, subject to
9 the following conditions:
11 The above copyright notice and this permission notice shall be
12 included in all copies or substantial portions of the Software.
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
15 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
16 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
17 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
18 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
19 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
20 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
23 /* This is my infix parser/evaluator. It is optimized for size, intended
24 * as a replacement for yacc-based parsers. However, it may well be faster
25 * than a comparable parser writen in yacc. The supported operators are
26 * listed in #defines below. Parens, order of operations, and error handling
27 * are supported. This code is threadsafe. */
29 /* To use the routine, call it with an expression string. It returns an
30 * integer result. You will also need to define an "error" function
31 * that takes printf arguments and _does not return_, or modify the code
32 * to use another error mechanism. */
38 typedef char operator;
40 #define tok_decl(prec,id) (((id)<<5)|(prec))
41 #define PREC(op) ((op)&0x1F)
43 #define TOK_LPAREN tok_decl(0,0)
45 #define TOK_OR tok_decl(1,0)
47 #define TOK_AND tok_decl(2,0)
49 #define TOK_BOR tok_decl(3,0)
51 #define TOK_BXOR tok_decl(4,0)
53 #define TOK_BAND tok_decl(5,0)
55 #define TOK_EQ tok_decl(6,0)
56 #define TOK_NE tok_decl(6,1)
58 #define TOK_LT tok_decl(7,0)
59 #define TOK_GT tok_decl(7,1)
60 #define TOK_GE tok_decl(7,2)
61 #define TOK_LE tok_decl(7,3)
63 #define TOK_LSHIFT tok_decl(8,0)
64 #define TOK_RSHIFT tok_decl(8,1)
66 #define TOK_ADD tok_decl(9,0)
67 #define TOK_SUB tok_decl(9,1)
69 #define TOK_MUL tok_decl(10,0)
70 #define TOK_DIV tok_decl(10,1)
71 #define TOK_REM tok_decl(10,2)
74 #define TOK_BNOT tok_decl(UNARYPREC,0)
75 #define TOK_NOT tok_decl(UNARYPREC,1)
76 #define TOK_UMINUS tok_decl(UNARYPREC,2)
78 #define TOK_NUM tok_decl(15,0)
80 #define ARITH_APPLY(op) arith_apply(op, numstack, &numstackptr)
81 #define NUMPTR (*numstackptr)
82 static short arith_apply(operator op, long *numstack, long **numstackptr)
84 if (NUMPTR == numstack) goto err;
87 else if (op == TOK_NOT)
88 NUMPTR[-1] = !(NUMPTR[-1]);
89 else if (op == TOK_BNOT)
90 NUMPTR[-1] = ~(NUMPTR[-1]);
92 /* Binary operators */
94 if (NUMPTR-1 == numstack) goto err;
97 NUMPTR[-1] |= *NUMPTR;
98 else if (op == TOK_OR)
99 NUMPTR[-1] = *NUMPTR || NUMPTR[-1];
100 else if (op == TOK_BAND)
101 NUMPTR[-1] &= *NUMPTR;
102 else if (op == TOK_AND)
103 NUMPTR[-1] = NUMPTR[-1] && *NUMPTR;
104 else if (op == TOK_EQ)
105 NUMPTR[-1] = (NUMPTR[-1] == *NUMPTR);
106 else if (op == TOK_NE)
107 NUMPTR[-1] = (NUMPTR[-1] != *NUMPTR);
108 else if (op == TOK_GE)
109 NUMPTR[-1] = (NUMPTR[-1] >= *NUMPTR);
110 else if (op == TOK_RSHIFT)
111 NUMPTR[-1] >>= *NUMPTR;
112 else if (op == TOK_LSHIFT)
113 NUMPTR[-1] <<= *NUMPTR;
114 else if (op == TOK_GT)
115 NUMPTR[-1] = (NUMPTR[-1] > *NUMPTR);
116 else if (op == TOK_LT)
117 NUMPTR[-1] = (NUMPTR[-1] < *NUMPTR);
118 else if (op == TOK_LE)
119 NUMPTR[-1] = (NUMPTR[-1] <= *NUMPTR);
120 else if (op == TOK_MUL)
121 NUMPTR[-1] *= *NUMPTR;
122 else if (op == TOK_DIV) {
125 NUMPTR[-1] /= *NUMPTR;
127 else if (op == TOK_REM) {
130 NUMPTR[-1] %= *NUMPTR;
132 else if (op == TOK_ADD)
133 NUMPTR[-1] += *NUMPTR;
134 else if (op == TOK_SUB)
135 NUMPTR[-1] -= *NUMPTR;
141 extern long arith (const char *startbuf, int *errcode)
143 register char arithval;
144 const char *expr = startbuf;
146 operator lasttok = TOK_MUL, op;
147 size_t datasizes = strlen(startbuf);
150 long *numstack, *numstackptr;
151 operator *stack = alloca(datasizes * sizeof(operator)), *stackptr = stack;
154 numstack = alloca((datasizes/2+1)*sizeof(long)), numstackptr = numstack;
156 while ((arithval = *expr)) {
157 if (arithval == ' ' || arithval == '\n' || arithval == '\t')
159 if ((unsigned)arithval-'0' <= 9) /* isdigit */ {
160 *numstackptr++ = strtol(expr, (char **) &expr, 10);
163 } if (arithval == '(') {
164 *stackptr++ = TOK_LPAREN;
165 lasttok = TOK_LPAREN;
167 } if (arithval == ')') {
169 while (stackptr != stack) {
171 if (op == TOK_LPAREN)
173 *errcode = ARITH_APPLY(op);
174 if(*errcode) return *errcode;
176 goto err; /* Mismatched parens */
177 } if (arithval == '|') {
184 } else if (arithval == '&') {
191 } else if (arithval == '=') {
192 if (*++expr != '=') goto err; /* Unknown token */
194 } else if (arithval == '!') {
201 } else if (arithval == '>') {
213 } else if (arithval == '<') {
225 } else if (arithval == '*')
227 else if (arithval == '/')
229 else if (arithval == '%')
231 else if (arithval == '+') {
232 if (lasttok != TOK_NUM) goto prologue; /* Unary plus */
234 } else if (arithval == '-')
235 op = (lasttok == TOK_NUM) ? TOK_SUB : TOK_UMINUS;
236 else if (arithval == '~')
238 else goto err; /* Unknown token */
241 if (prec != UNARYPREC)
242 while (stackptr != stack && PREC(stackptr[-1]) >= prec) {
243 *errcode = ARITH_APPLY(*--stackptr);
244 if(*errcode) return *errcode;
251 while (stackptr != stack) {
252 *errcode = ARITH_APPLY(*--stackptr);
253 if(*errcode) return *errcode;
255 if (numstackptr != numstack+1) {