Expr.cc Source File

00001 /*
00002     File:       Expr.cc
00003  
00004     Function:   
00005  
00006     Authors:    Paul Heckbert, Andrew Willmott
00007  
00008     Notes:      
00009 */
00010 
00011 #include "cl/Expr.h"
00012 
00013 /*
00014  * expr_eval: expression evaluator - converts ascii string to floating point
00015  * Works by top-down predictive parsing.
00016  * Most of the routines gobble characters and advance global string pointer s.
00017  * Sets global expr_err if an error occurs.
00018  *
00019  * supports: parentheses, % for mod, ^ for pow, elementary functions,
00020  * constants pi and e, variable base constants
00021  *
00022  * Paul Heckbert    18 April 1988
00023  * converted to ANSI C, ajw 1999
00024  */
00025 
00026 
00027 #include <ctype.h>
00028 #include <math.h>
00029 #include <limits.h>
00030 
00031 inline Double DegsToRads(Double degrees)    
00032 { return(degrees * (M_PI / 180.0)); }
00033 inline Double RadsToDegs(Double rads)       
00034 { return(rads * (180.0 / M_PI)); }
00035 
00036 static Double expr();
00037 static Double term();
00038 static Double factor();
00039 static Double signednumber();
00040 static Double number();
00041 static Double paren();
00042 static Double posconst();
00043 static Double expt(Int a, Int n);
00044 static void paren2(Double *x, Double *y);
00045 static Int eq(Int n, const Char *a, const Char *b);
00046 static void error(const Char *s, Int len, const Char *err);
00047 static void prints(Int n, const Char *s);
00048 static Int digit(Int c);
00049 
00050 static const Char *s0, *s;
00051 Int expr_error;
00052 
00053 inline space()
00054 { for (; isspace(*s); s++); };
00055 
00056 #ifdef MAIN
00057 main(Int ac, Char **av)
00058 {
00059     Double x;
00060 
00061     if (ac != 2) exit(1);
00062     x = expr_eval(av[1]);
00063     printf("%g\n", x);
00064 }
00065 #endif
00066 
00067 Int expr_eval_int(StrConst str)
00068 {
00069     Double x;
00070 
00071     x = expr_eval(str);
00072     /* do unsigned Double to signed Int conversion: */
00073 
00074     if (x > INT_MAX)
00075         return(Int(x + 2.0 * INT_MIN));
00076     else
00077         return(Int(x));
00078 }
00079 
00080 Long expr_eval_long(StrConst str)
00081 {
00082     Double x;
00083 
00084     x = expr_eval(str);
00085     /* do unsigned Double to signed Long conversion: */
00086     if (x > LONG_MAX)
00087         return(Long(x + 2.0 * LONG_MIN));
00088     else
00089         return(Long(x));
00090 }
00091 
00092 Double expr_eval(StrConst str)
00093 {
00094     Double x;
00095 
00096     s0 = s = str;
00097     expr_error = EXPR_GOOD;
00098     x = expr();
00099     if (*s)
00100     {
00101         error(s, 1, "garbage in expression");
00102         expr_error = s == s0 ? EXPR_BAD : EXPR_SOSO;
00103     }
00104     return x;
00105 }
00106 
00107 static Double expr()
00108 {
00109     Double x;
00110 
00111     for (x = term(); ; )
00112     {
00113         space();
00114         switch (*s)
00115         {
00116         case '+':
00117             s++;
00118             x += term(); break;
00119         case '-': s++; x -= term(); break;
00120         default: return x;
00121         }
00122     }
00123 }
00124 
00125 static Double term()
00126 {
00127     Double x, y;
00128 
00129     for (x = factor(); ; )
00130     {
00131         space();
00132         switch (*s)
00133         {
00134         case '*':
00135             s++;
00136             x *= factor(); break;
00137         case '/': s++; x /= factor(); break;
00138         case '%': s++; y = factor(); x = x - floor(x / y) * y; break;
00139         default: return x;
00140         }
00141     }
00142 }
00143 
00144 static Double factor()
00145 {
00146     Double x;
00147 
00148     for (x = signednumber(); ; )
00149     {
00150         space();
00151         switch (*s)
00152         {
00153         case '^':
00154             s++;
00155             return pow(x, factor());    /* right-associative */
00156         default: return x;
00157         }
00158     }
00159 }
00160 
00161 static Double signednumber()
00162 {
00163     space();
00164     switch (*s)
00165     {
00166     case '-':
00167         s++;
00168         return - signednumber();
00169     case '+': s++; return signednumber();
00170     default: return number();
00171     }
00172 }
00173 
00174 static Double number()
00175 {
00176     const Char *func;
00177     Int n;
00178     Double x, y;
00179 
00180     space();
00181     if (isdigit(*s) || *s == '.') return posconst();
00182     if (*s == '(') return paren();
00183 
00184     if (isalpha(*s))
00185     {
00186         func = s;
00187         for (s++; isalpha(*s) || isdigit(*s); s++);
00188         n = s - func;   /* length of funcname */
00189 
00190         if (eq(n, func, "pi"))  return M_PI;
00191         if (eq(n, func, "e"))   return exp(1.);
00192 
00193         if (eq(n, func, "sqrt"))    return sqrt(paren());
00194         if (eq(n, func, "exp")) return exp(paren());
00195         if (eq(n, func, "log")) return log(paren());
00196         if (eq(n, func, "pow"))
00197         {
00198             paren2(&x, &y);
00199             return pow(x, y);
00200         }
00201 
00202         if (eq(n, func, "sin")) return sin(paren());
00203         if (eq(n, func, "cos")) return cos(paren());
00204         if (eq(n, func, "tan")) return tan(paren());
00205         if (eq(n, func, "asin"))    return asin(paren());
00206         if (eq(n, func, "acos"))    return acos(paren());
00207         if (eq(n, func, "atan"))    return atan(paren());
00208         if (eq(n, func, "atan2"))
00209         {
00210             paren2(&x, &y);
00211             return atan2(x, y);
00212         }
00213 
00214         if (eq(n, func, "sind"))    return sin(DegsToRads(paren()));
00215         if (eq(n, func, "cosd"))    return cos(DegsToRads(paren()));
00216         if (eq(n, func, "tand"))    return tan(DegsToRads(paren()));
00217         if (eq(n, func, "dasin"))   return RadsToDegs(asin(paren()));
00218         if (eq(n, func, "dacos"))   return RadsToDegs(acos(paren()));
00219         if (eq(n, func, "datan"))   return RadsToDegs(atan(paren()));
00220         if (eq(n, func, "datan2"))
00221         {
00222             paren2(&x, &y);
00223             return RadsToDegs(atan2(x, y));
00224         }
00225 
00226         if (eq(n, func, "floor"))   return floor(paren());
00227         if (eq(n, func, "ceil"))    return ceil(paren());
00228 
00229         error(func, n, "bad numerical expression");
00230         return 0.;
00231     }
00232 
00233     error(s, 1, "syntax error");
00234     return 0.;
00235 }
00236 
00237 /* paren: '(' expr ')' */
00238 
00239 static Double paren()
00240 {
00241     Double x;
00242 
00243     space();
00244     if (*s != '(') error(s, 1, "expected '('");
00245     s++;
00246     x = expr();
00247     space();
00248     if (*s != ')') error(s, 1, "expected ')'");
00249     s++;
00250     return x;
00251 }
00252 
00253 /* paren2: '(' expr ',' expr ')' */
00254 
00255 static void paren2(Double *x, Double *y)
00256 {
00257     space();
00258     if (*s != '(') error(s, 1, "expected '('");
00259     s++;
00260     *x = expr();
00261     space();
00262     if (*s != ',') error(s, 1, "expected ','");
00263     s++;
00264     *y = expr();
00265     space();
00266     if (*s != ')') error(s, 1, "expected ')'");
00267     s++;
00268 }
00269 
00270 /*
00271  * posconst: given a string beginning at s, return floating point value.
00272  * like atof but it uses and modifies the global ptr s
00273  */
00274 
00275 static Double posconst()
00276 {
00277     Int base, exp, pos, d;
00278     Double x, y;
00279 
00280     space();
00281     if (*s == '0')
00282     {       /* change base: 10 = 012 = 0xa = 0b2:1010 */
00283         s++;
00284         switch (*s)
00285         {
00286         case 'b':
00287             s++;
00288             for (base = 0; isdigit(*s); s++)
00289                 base = base * 10 + *s - '0';    /* base is in base 10! */
00290             if (*s != ':') error(s, 1, "expecting ':'");
00291             s++;
00292             break;
00293         case 'x':
00294             s++;
00295             base = 16;
00296             break;
00297         case 't':
00298             s++;
00299             base = 10;
00300             break;
00301         case '.':
00302             base = 10;
00303             break;          /* a float, e.g.: 0.123 */
00304         default:
00305             base = 8;
00306             break;
00307         }
00308     }
00309     else base = 10;
00310 
00311     x = 0.;
00312     for (; d = digit(*s), d >= 0 && d < base; s++)
00313         x = x * base + d;
00314     if (*s == '.')
00315     {
00316         s++;
00317         for (y = 1.; d = digit(*s), d >= 0 && d < base; s++)
00318         {
00319             x = x * base + d;       /* fraction is in variable base */
00320             y *= base;
00321         }
00322         x /= y;
00323     }
00324     if (*s == 'e' || *s == 'E')
00325     {
00326         s++;
00327         if (*s == '-')
00328         {
00329             s++;
00330             pos = 0;
00331         }
00332         else if (*s == '+')
00333         {
00334             s++;
00335             pos = 1;
00336         }
00337         else pos = 1;
00338         for (exp = 0; isdigit(*s); s++)
00339             exp = exp * 10 + *s - '0';      /* exponent is in base 10 */
00340         y = expt(base, exp);
00341         if (pos) x *= y;
00342         else x /= y;
00343     }
00344     return x;
00345 }
00346 
00347 static Int digit(Int c)
00348 {
00349     return isdigit(c) ? c - '0' :
00350            c >= 'a' && c <= 'z' ? c - 'a' + 10 : c >= 'A' && c <= 'Z' ? c - 'A' + 10 : -1;
00351 }
00352 
00353 /* expt: a^n for n>=0 */
00354 
00355 static Double expt(Int a, Int n)
00356 {
00357     Double t, x;
00358 
00359     if (n < 0)
00360     {
00361         fprintf(stderr, "expt: can't do negative exponents\n");
00362         return 1.;
00363     }
00364     if (n == 0) return 1.;
00365     for (t = a, x = 1.; n > 0; n >>= 1)
00366     {
00367         if (n&1) x *= t;
00368         t *= t;
00369     }
00370     return x;
00371 }
00372 
00373 /* eq: test equality of string a, of length n, with null-terminated string b */
00374 
00375 static Int eq(Int n, const Char *a, const Char *b)
00376 {
00377     Char c, *nca = (Char *) a;
00378     Int ret;
00379 
00380     c = a[n];
00381     nca[n] = 0;
00382     ret = (strcmp(a, b) == 0);
00383     nca[n] = c;
00384     return ret;
00385 }
00386 
00387 static void error(const Char *s, Int len, const Char *err)
00388 {
00389 //    if (*s == 0) s[len] = 0;      /* just in case */
00390     printf("expr: %s: ", err);
00391     prints(s - s0, s0);
00392     printf("[");
00393     prints(len, s);
00394     printf("]");
00395     prints(s + strlen(s) - s0 - len, s + len);
00396     printf("\n");
00397     if (expr_error != EXPR_BAD)
00398         expr_error = s == s0 ? EXPR_BAD : EXPR_SOSO;
00399 }
00400 
00401 /* prints: print string s of length n */
00402 
00403 static void prints(Int n, const Char *s)
00404 {
00405     Char c, *ncs = (Char *) s;
00406 
00407     c = s[n];
00408     ncs[n] = 0;
00409     printf("%s", s);
00410     ncs[n] = c;
00411 }