home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS - Coast to Coast / simteldosarchivecoasttocoast2.iso / calculat / meval113.zip / SRC / PARSE.C < prev   
Text File  |  1993-04-11  |  14KB  |  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.