home *** CD-ROM | disk | FTP | other *** search
/ World of A1200 / World_Of_A1200.iso / programs / misc / eval / source / src.lha / parse.c < prev   
C/C++ Source or Header  |  1993-04-13  |  16KB  |  618 lines
  1. /*
  2. **
  3. ** PARSE.C     Divides an input string into tokens and evaluates an
  4. **             expression.
  5. **
  6. ** Originally written 5/89 in ANSI C
  7. **
  8. ** Eval is a floating point expression evaluator.
  9. ** This file last updated in version 1.10
  10. ** For the version number, see eval.h
  11. ** Copyright (C) 1993  Will Menninger
  12. **
  13. ** This program is free software; you can redistribute it and/or modify it
  14. ** under the terms of the GNU General Public License as published by the
  15. ** Free Software Foundation; either version 2 of the License, or any
  16. ** later version.
  17. **
  18. ** This program is distributed in the hope that it will be useful, but
  19. ** WITHOUT ANY WARRANTY; without even the implied warranty of
  20. ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  21. ** General Public License for more details.
  22. **
  23. ** You should have received a copy of the GNU General Public License along
  24. ** with this program; if not, write to the Free Software Foundation, Inc.,
  25. ** 675 Mass Ave, Cambridge, MA 02139, USA.
  26. **
  27. ** The author until 9/93 can be contacted at:
  28. ** e-mail:     willus@ilm.pfc.mit.edu
  29. ** U.S. mail:  Will Menninger, 45 River St., #2, Boston, MA 02108-1124
  30. **
  31. **
  32. */
  33.  
  34. #include   "eval.h"
  35.  
  36.  
  37. /* modes */
  38. #define     M_UNARY     1
  39. #define     M_BINARY    2
  40. #define     M_FUNCTION  3
  41.  
  42. static double   last_value=0.0;
  43. static int      base;
  44.  
  45. static int     is_binary     (char *s);
  46. static int     is_unary      (char c);
  47. static int     instr         (char c,char *s);
  48. static BOOLEAN legal         (char *s);
  49. static BOOLEAN is_digit      (char c);
  50. static BOOLEAN is_exp        (char c);
  51. static BOOLEAN get_token     (int mode,char *s,int *n,TOKENPTR t,VARPTR vlist,
  52.                               VARPTR clist,char *newname);
  53. static BOOLEAN assign_as_var (char *s,int *n,TOKENPTR t,VARPTR vlist,
  54.                               VARPTR clist,char *newname);
  55. static BOOLEAN assign_as_num (char *s,int *n,TOKENPTR t,int max,int base);
  56. static BOOLEAN get_value     (char *s,VARPTR vlist,VARPTR clist,
  57.                               double *ret_val);
  58. static int     base_override (char *s,int *n);
  59. static int     rank          (int operator);
  60.  
  61.  
  62. static int is_binary(char *s)
  63.  
  64.     {
  65.     if (s[0]=='<' && s[1]=='<')
  66.         return(SHLEFT);
  67.     if (s[0]=='>' && s[1]=='>')
  68.         return(SHRIGHT);
  69.     return(instr(s[0],BSTRING));
  70.     }
  71.  
  72.  
  73. static int is_unary(char c)
  74.  
  75.     {
  76.     return(instr(c,USTRING));
  77.     }
  78.  
  79.  
  80. static int instr(char c,char *s)
  81.  
  82.     {
  83.     int    i;
  84.  
  85.     for (i=0;s[i]!=EOS && s[i]!=c;i++);
  86.     return(s[i]==EOS ? 0 : i+1);
  87.     }
  88.  
  89.  
  90. static BOOLEAN legal(char *s)
  91.  
  92.     {
  93.     int     c;
  94.  
  95.     c=s[0];
  96.     return(c!=EOS && c!='(' && c!=')' && c!=','
  97.             && c!='=' && !isspace(c) && !is_binary(s));
  98.     }
  99.  
  100.  
  101. static BOOLEAN is_digit(char c)
  102.  
  103.     {
  104.     c=tolower((int)c);
  105.     if (base>10)
  106.         return((c>='0' && c<='9') || (c>='a' && c<='a'+base-11));
  107.     return(c>='0' && c<='0'+base-1);
  108.     }
  109.  
  110.  
  111. static BOOLEAN is_exp(char c)
  112.  
  113.     {
  114.     return((base > 14) ? (c=='\\') : (c=='\\' || c=='e' || c=='E'));
  115.     }
  116.  
  117. /*
  118. ** get_token(int mode,char *s,int *n,TOKENPTR t,VARPTR vlist,
  119. **           VARPTR clist,char *newname)
  120. **
  121. ** Figures out what the next token in the string s is, starting at (*n).
  122. ** (*n) is returned pointing to the part of the string just after the
  123. ** evaluated token.  vlist and clist are used to search through in case
  124. ** the token is a variable or constant.  newname is assigned if the token
  125. ** is a variable name not found in any of the lists.
  126. **
  127. ** Returns 0 for end of string, 1 for valid token found
  128. **
  129. */
  130.  
  131. static BOOLEAN get_token(int mode,char *s,int *n,TOKENPTR t,VARPTR vlist,
  132.                          VARPTR clist,char *newname)
  133.  
  134.     {
  135.     int     i,c,h;
  136.  
  137.     t->type=0;
  138.     t->code=0;
  139.     t->value=0;
  140.     for (i=(*n);isspace(s[i]);i++);
  141.     (*n)=i;
  142.     if (s[i]==EOS)
  143.         {
  144.         (*n)=i;
  145.         return(0);
  146.         }
  147.     t->type=0;
  148.     if (mode==M_UNARY && is_unary(s[i]))
  149.         {
  150.         t->type=UNARY;
  151.         t->code=is_unary(s[i]);
  152.         (*n)=(*n)+1;
  153.         return(1);
  154.         }
  155.     if (is_binary(&s[i]) && (mode!=M_UNARY || s[i]!='&'))
  156.         {
  157.         t->type=BINARY;
  158.         t->code=is_binary(&s[i]);
  159.         if (t->code==SHLEFT || t->code==SHRIGHT)
  160.             (*n)=(*n)+1;
  161.         }
  162.     else
  163.         {
  164.         t->type=instr(s[i],"(),=");
  165.         if (t->type>0)
  166.                 t->type+=LEFT_PAREN-1;
  167.         }
  168.     if (t->type!=0)
  169.         {
  170.         (*n)=(*n)+1;
  171.         return(1);
  172.         }
  173.     if (s[i]=='!')
  174.         return(assign_as_var(s,n,t,vlist,clist,newname));
  175.     base=getibase();
  176.     c=base_override(&s[i],&h);
  177.     if (c)
  178.         {
  179.         base=c;
  180.         i+=h;
  181.         }
  182.     if (!is_digit(s[i]) && s[i]!='.')
  183.         return(assign_as_var(s,n,t,vlist,clist,newname));
  184.     if (s[i]=='.' && !is_digit(s[i+1]))
  185.         return(assign_as_var(s,n,t,vlist,clist,newname));
  186.     for (;legal(&s[i]);i++)
  187.         {
  188.         if (s[i]=='.' || is_exp(s[i]))
  189.             break;
  190.         if (!is_digit(s[i]))
  191.                 return(assign_as_var(s,n,t,vlist,clist,newname));
  192.         }
  193.     if (!legal(&s[i]))
  194.         {
  195.         (*n)=(*n)+h;
  196.         return(assign_as_num(s,n,t,i,base));
  197.         }
  198.     if (s[i]=='.')
  199.         for (i++;legal(&s[i]);i++)
  200.                 {
  201.                 if (is_exp(s[i]))
  202.                     break;
  203.                 if (!is_digit(s[i]))
  204.                     return(assign_as_var(s,n,t,vlist,clist,newname));
  205.                 }
  206.     if (!legal(&s[i]))
  207.         {
  208.         (*n)=(*n)+h;
  209.         return(assign_as_num(s,n,t,i,base));
  210.         }
  211.     if (s[i+1]=='+' || s[i+1]=='-')
  212.         i++;
  213.     if (!is_digit(s[i+1]))
  214.         return(assign_as_var(s,n,t,vlist,clist,newname));
  215.     for (i++;legal(&s[i]);i++)
  216.         {
  217.         if (!is_digit(s[i]))
  218.                 return(assign_as_var(s,n,t,vlist,clist,newname));
  219.         }
  220.     (*n)=(*n)+h;
  221.     return(assign_as_num(s,n,t,i,base));
  222.     }
  223.  
  224.  
  225. static BOOLEAN assign_as_var(char *s,int *n,TOKENPTR t,VARPTR vlist,
  226.                              VARPTR clist,char *newname)
  227.  
  228.     {
  229.     VAR     v;
  230.     char    vname[MAXINPUT+1];
  231.     int     l,i,j;
  232.  
  233.     i=(*n);
  234.     l=(s[i]=='!');
  235.     if (l)
  236.         i++;
  237.     for (j=0;legal(&s[i]) || (!j && s[i]=='&');i++,j++)
  238.         vname[j]=s[i];
  239.     if (!j && l)
  240.         vname[j++]='!';
  241.     (*n)=i;
  242.     vname[j]=EOS;
  243.     if (strlen(vname)>MAXNAMELEN)
  244.         vname[MAXNAMELEN]=EOS;
  245.     strcpy(newname,vname);
  246.     if (vname[0]=='\"' && vname[1]==EOS)
  247.         {
  248.         t->value=last_value;
  249.         t->type=QUOTE;
  250.         return(1);
  251.         }
  252.     if (strlen(vname)<=MAXFLEN && (i=func_code(vname))!=0)
  253.         {
  254.         t->code=i;
  255.         t->type=FUNCTION;
  256.         }
  257.     else
  258.         {
  259.         strcpy(v.name,vname);
  260.         if (search_varlist(&v,clist,&i,MAXC))
  261.                 {
  262.                 t->code=i;
  263.                 t->type=CONSTANT;
  264.                 t->value=clist[i].value;
  265.                 }
  266.         else
  267.                 {
  268.                 t->type=VARIABLE;
  269.                 if (search_varlist(&v,vlist,&i,MAXV))
  270.                     {
  271.                     t->code=i;
  272.                     t->value=vlist[i].value;
  273.                     }
  274.                 else
  275.                     t->code=-1;
  276.                 }
  277.         }
  278.     return(1);
  279.     }
  280.  
  281.  
  282. static BOOLEAN assign_as_num(char *s,int *n,TOKENPTR t,int max,int base)
  283.  
  284.     {
  285.     char    num[MAXINPUT+1];
  286.     int     i,j;
  287.  
  288.     for (i=(*n),j=0;i<max;i++,j++)
  289.         num[j]=s[i];
  290.     (*n)=i;
  291.     num[j]=EOS;
  292.     t->type=NUMBER;
  293.     t->value=asciiconv(base,num);
  294.     return(1);
  295.     }
  296.  
  297.  
  298. /*
  299. ** evaluate(char *s,int showout,VARPTR vlist,VARPTR clist)
  300. **
  301. ** Evaluate parses the input string looking for help queries or an "equals"
  302. ** sign that divides the string into an assignment variable and its
  303. ** assigned expression.  To evaluate the actual expression, get_value is
  304. ** called.
  305. **
  306. ** Returns nothing
  307. **
  308. */
  309.  
  310. void evaluate(char *s,int showout,VARPTR vlist,VARPTR clist)
  311.  
  312.     {
  313.     char    varname[MAXINPUT+1];
  314.     int     i,j,n,vn;
  315.     VAR     x;
  316.     TOKEN   t;
  317.     int     checked,outbase,oldbase;
  318.     char    bigbuf[MAXOUTLEN];
  319.  
  320.  
  321.     oldbase=getobase();
  322.     outbase=base_override(s,&j);
  323.     checked=0;
  324.     if (outbase && isspace(s[j]))
  325.         {
  326.         j++;
  327.         checked=1;
  328.         }
  329.     else
  330.         {
  331.         j=0;
  332.         outbase=oldbase;
  333.         }
  334.     for (i=j;s[i]!=EOS && s[i]!='=';i++);
  335.     if (s[i]!=EOS)
  336.         {
  337.         strcpy(varname,&s[j]);
  338.         varname[i++]=EOS;
  339.         fixup(varname);
  340.         n=0;
  341.         j=get_token(M_UNARY,varname,&n,&t,vlist,clist,x.name);
  342.         if (!j)
  343.                 {
  344.                 printf("There must be valid variable name on the left side of the '='.\n");
  345.                 return;
  346.                 }
  347.         if (varname[n]!=EOS || t.type!=VARIABLE && t.type!=CONSTANT)
  348.                 {
  349.                 printf("\"%s\" is not a valid variable name.\n",varname);
  350.                 return;
  351.                 }
  352.         if (t.type==CONSTANT)
  353.                 {
  354.                 printf("\"%s\" is a pre-assigned constant.  It cannot be reassigned.\n",x.name);
  355.                 return;
  356.                 }
  357.         vn=(t.type==VARIABLE);
  358.         }
  359.     else
  360.         {
  361.         vn=0;
  362.         i=j;
  363.         }
  364.     if (!checked)
  365.         {
  366.         outbase=base_override(&s[i],&j);
  367.         if (outbase && isspace(s[i+j]))
  368.             j++;
  369.         else
  370.             {
  371.             j=0;
  372.             outbase=oldbase;
  373.             }
  374.         i+=j;
  375.         }
  376.     if (!get_value(&s[i],vlist,clist,&x.value))
  377.         return;
  378.     last_value=x.value;
  379.     if (outbase!=oldbase)
  380.         setobase(outbase);
  381.     baseconv(x.value,bigbuf);
  382.     if (showout)
  383.         printf("%s\n",bigbuf);
  384.     if (outbase!=oldbase)
  385.         setobase(oldbase);
  386.     if (vn)
  387.         {
  388.         if (!insert_var(&x,vlist))
  389.             printf("No more variables can be assigned!  Limit = %d.\n",MAXV);
  390.         }
  391.     }
  392.  
  393.  
  394. /*
  395. ** get_value(char *s,VARPTR vlist,VARPTR clist)
  396. **
  397. ** get_value evaluates an expression string by parsing it into tokens
  398. ** (using get_token) and converting the string of tokens to a table that
  399. ** contains tokens in reverse polish order.  table_value is then called
  400. ** to evaluate the final value of the reverse polish table of tokens.
  401. ** That value is returned by get_value.
  402. **
  403. */
  404.  
  405. static BOOLEAN get_value(char *s,VARPTR vlist,VARPTR clist,double *ret_val)
  406.  
  407.     {
  408.     char    nn[MAXNAMELEN+1];
  409.     TOKEN   t,t2,t3;
  410.     int     spos,mode;
  411.     char    argcount[MAXINPUT+1];
  412.     int     argptr;
  413.  
  414.     clear_stack();
  415.     clear_table();
  416.     spos=0;
  417.     argptr=-1;
  418.     mode=M_UNARY;
  419.     while (get_token(mode,s,&spos,&t,vlist,clist,nn))
  420.         {
  421.         if (t.type==ILLEGAL)
  422.             return(eerror("The '=' character is not allowed in expressions."));
  423.         if (mode==M_UNARY && (t.type==BINARY || t.type==COMMA ||
  424.                               t.type==RIGHT_PAREN))
  425.             return(eerror("Operand expected in expression."));
  426.         if (mode==M_BINARY && (t.type==UNARY || t.type==CONSTANT ||
  427.                                t.type==VARIABLE || t.type==FUNCTION ||
  428.                                t.type==NUMBER || t.type==LEFT_PAREN ||
  429.                                t.type==QUOTE))
  430.             return(eerror("Operator expected in expression."));
  431.         if (t.type==VARIABLE && t.code<0)
  432.             {
  433.             printf("\"%s\" is an unassigned variable.\n",nn);
  434.             return(0);
  435.             }
  436.         if (mode==M_FUNCTION && t.type!=LEFT_PAREN)
  437.             return(eerror("Function names must be immediately followed "
  438.                           "by a left parenthesis."));
  439.         switch(t.type)
  440.             {
  441.             case NUMBER:
  442.             case VARIABLE:
  443.             case CONSTANT:
  444.             case QUOTE:
  445.                 if (!add_token(&t))
  446.                     return(0);
  447.                 mode=M_BINARY;
  448.                 break;
  449.             case LEFT_PAREN:
  450.                 if (!push_token(&t))
  451.                     return(0);
  452.                 mode=M_UNARY;
  453.                 break;
  454.             case UNARY:
  455.                 if (!push_token(&t))
  456.                     return(0);
  457.                 mode=M_UNARY;
  458.                 break;
  459.             case BINARY:
  460.                 while (top_of_stack(&t2))
  461.                     {
  462.                     if (t2.type==BINARY && rank(t.code) > rank(t2.code))
  463.                         break;
  464.                     if (t2.type==LEFT_PAREN)
  465.                         break;
  466.                     pop_token(&t2);
  467.                     if (!add_token(&t2))
  468.                         return(0);
  469.                     }
  470.                 if (!push_token(&t))
  471.                     return(0);
  472.                 mode=M_UNARY;
  473.                 break;
  474.             case FUNCTION:
  475.                 if (!push_token(&t))
  476.                     return(0);
  477.                 argptr++;
  478.                 argcount[argptr]=0;
  479.                 mode=M_FUNCTION;
  480.                 break;
  481.             case RIGHT_PAREN:
  482.                 while (pop_token(&t2) && t2.type!=LEFT_PAREN)
  483.                     if (!add_token(&t2))
  484.                         return(0);
  485.                 if (t2.type!=LEFT_PAREN)
  486.                     return(eerror("Unmatched parentheses in expression."));
  487.                 if (top_of_stack(&t2) && t2.type==FUNCTION)
  488.                     {
  489.                     pop_token(&t2);
  490.                     if (!add_token(&t2))
  491.                         return(0);
  492.                     if (func_nargs(t2.code)!=argcount[argptr]+1)
  493.                         {
  494.                         printf("Incorrect number of arguments "
  495.                                "specified for function %s.\n",
  496.                                func_name(t2.code));
  497.                         return(0);
  498.                         }
  499.                     argptr--;
  500.                     }
  501.                 mode=M_BINARY;
  502.                 break;
  503.             case COMMA:
  504.                 while (pop_token(&t2) && t2.type!=LEFT_PAREN)
  505.                     if (!add_token(&t2))
  506.                         return(0);
  507.                 if (t2.type!=LEFT_PAREN || !top_of_stack(&t3) ||
  508.                     t3.type!=FUNCTION)
  509.                     return(eerror("Misplaced comma in expression."));
  510.                 if (!push_token(&t2))
  511.                     return(0);
  512.                 mode=M_UNARY;
  513.                 argcount[argptr]++;
  514.                 break;
  515.             }
  516.         }
  517.     if (mode==M_UNARY)
  518.         return(eerror("Expression is improperly terminated."));
  519.     while (pop_token(&t2))
  520.         {
  521.         if (t2.type==LEFT_PAREN)
  522.             return(eerror("Unmatched parentheses in expression."));
  523.         if (!add_token(&t2))
  524.             return(0);
  525.         }
  526.     return(table_value(ret_val));
  527.     }
  528.  
  529.  
  530. BOOLEAN eerror(char *message)
  531.  
  532.     {
  533.     printf("%s\n",message);
  534.     return(0);
  535.     }
  536.  
  537.  
  538. static int rank(int operator)
  539.  
  540.     {
  541.     switch (operator)
  542.         {
  543.         case POWER:
  544.             return(10);
  545.         case DIVIDE:
  546.         case MULTIPLY:
  547.         case MOD:
  548.             return(9);
  549.         case ADD:
  550.         case SUBTRACT:
  551.             return(8);
  552.         case SHRIGHT:
  553.         case SHLEFT:
  554.             return(7);
  555.         case AND:
  556.             return(6);
  557.         case XOR:
  558.             return(5);
  559.         case OR:
  560.             return(4);
  561.         }
  562.     return(0);
  563.     }
  564.  
  565.  
  566. static int base_override(char *s,int *n)
  567.  
  568.     {
  569.     int     base;
  570.     int     c;
  571.  
  572.     (*n)=0;
  573.     base=0;
  574.     if (s[0]=='&')
  575.         {
  576.         if (s[1]!=EOS)
  577.             {
  578.             c=tolower((int)s[1]);
  579.             if (c=='h' || c=='o' || c=='b' || c=='d')
  580.                 {
  581.                 base= c=='h' ? 16 : (c=='o' ? 8 :(c=='b' ? 2 : 10));
  582.                 (*n)=2;
  583.                 }
  584.             }
  585.         }
  586.     else if (s[0]=='0' && (s[1]=='x' || s[1]=='X'))
  587.         {
  588.         base=16;
  589.         (*n)=2;
  590.         }
  591. /* Assuming base 8 for a leading zero removed because of
  592.    confusion with floating point numbers */
  593.     else if (s[0]=='\\')
  594.         {
  595.         c=tolower((int)s[1]);
  596.         if (c=='0' || (c>='2' && c<='9') || (c>='a' && c<='z'))
  597.             {
  598.             base= c=='0' ? 10:((c>='2'&&c<='9')?c-'0':c-'a'+11);
  599.             (*n)=2;
  600.             }
  601.         }
  602.     else if (s[0]=='$')
  603.         {
  604.         base=16;
  605.         (*n)=1;
  606.         }
  607.     return(base);
  608.     }
  609.  
  610.  
  611. void tokcpy(TOKENPTR dest,TOKENPTR source)
  612.  
  613.     {
  614.     dest->type=source->type;
  615.     dest->code=source->code;
  616.     dest->value=source->value;
  617.     }
  618.