home *** CD-ROM | disk | FTP | other *** search
/ Gold Fish 3 / goldfish_volume_3.bin / files / dev / cross / caz / src / calc.c next >
C/C++ Source or Header  |  1994-01-08  |  8KB  |  370 lines
  1. #include "defs.h"
  2. #include "calc.h"
  3.  
  4. static char *getvalue    (char *pos,int *pvalue);
  5. static int push            (struct node **pstack,int type,int value);
  6. static int convert        (char symbol);
  7. static int ishigher        (char symbol,struct node *pstack);
  8. static int pop            (struct node **pstack,int *pvalue);
  9. static struct node *makeupn    (struct listheader *plabel,char *pos);
  10. static int docalc        (struct node **pstack);
  11. static int calcupn        (struct node *pupn,u_short *pu_short);
  12.  
  13. int        calcexpr        (struct listheader *plabel,char *expr,u_short *pu_short);
  14.  
  15. static char *getvalue(char *pos,int *pvalue)
  16. {
  17.     /*
  18.      * Convert Number in Ascii to Integer format.
  19.      * Find position of following token.
  20.      *
  21.      * RC: found Number is stored in *pvalue
  22.      *     Pointer to next non blank character
  23.      */
  24.      
  25.     *pvalue=atoi(pos);
  26.     while(isdigit(*pos))
  27.         pos++;
  28.     while(isspace(*pos))
  29.         pos++;
  30.     return(pos);
  31. }
  32.  
  33. static int push(struct node **pstack,int type,int value)
  34. {
  35.     /* Push item on stack. Set 'pstack' to new top of stack .
  36.      *
  37.      * RC: NULL if all went fine,
  38.      *     ERROR if malloc() failed();
  39.      */
  40.      
  41.     struct node *pnode;
  42.     if(!(pnode=(struct node *)malloc(sizeof(struct node))))
  43.     {
  44.         printf("Can't allocate memory\n");
  45.         return(ERROR);
  46.     }
  47.     pnode->prev = *pstack;
  48.     pnode->type = type;
  49.     pnode->value= value;
  50.     *pstack     = pnode;
  51.  
  52.     return(NULL);
  53. }
  54.  
  55. static int convert(char symbol)
  56. {
  57.     /* Convert any Mathematicl Symbol to a priority.
  58.      *
  59.      * RC: Priority, or
  60.      *     ERROR if 'symbol' is not a valid mathematical operand.
  61.      */
  62.      
  63.     switch(symbol)
  64.     {
  65.         case '(' : return(10);
  66.         case '*' :
  67.         case '/' : return(8);
  68.         case '+' :
  69.         case '-' : return(6);
  70.         default  : printf("Expect any Mathematical Symbol, not '%c'\n",symbol);
  71.                    return(ERROR);
  72.     }
  73. }
  74.  
  75. static int ishigher(char symbol,struct node *pstack)
  76. {
  77.     /*
  78.      * Checks if has 'symbol' a greater priority as the topmost element
  79.      * on 'pstack'. If 'pstack' is empty so 'symbol' is always higher.
  80.      *
  81.      * RC: TRUE if 'symbol' > 'pstack->value' or if 'pstack' is empty,
  82.      *     FALSE else 
  83.      */
  84.  
  85.     int actprio,topprio;
  86.     
  87.     if(!pstack)
  88.         return(TRUE);
  89.         
  90.     if((char)pstack->value=='(')
  91.         return(TRUE);
  92.         
  93.     actprio=convert(symbol);
  94.     topprio=convert((char)pstack->value);
  95.  
  96.     return( (actprio>topprio)? TRUE : FALSE);
  97. }
  98.  
  99. static int pop(struct node **pstack,int *pvalue)
  100. {
  101.     /* Get topmost Element from stack. Set 'pstack' to new topmost element.
  102.      * Fill 'pvalue' with value of poped Element.
  103.      *
  104.      * RC: NULL if all went fine, else
  105.      *     ERROR if 'pstack' is empty.
  106.      */
  107.      
  108.     struct node *ptmp;
  109.     
  110.     if(!*pstack)
  111.         return(ERROR);
  112.  
  113.     *pvalue=(*pstack)->value;        /* get vaule */
  114.     ptmp   =(*pstack)->prev;        /* save next new element */
  115.     free(*pstack);                /* free topmost element */
  116.     *pstack=ptmp;                /* set to new topmost element */
  117.  
  118.     return(NULL);
  119. }
  120.  
  121. static struct node *makeupn(struct listheader *plabel,char *pos)
  122. {
  123.     /* Parse Mathematical expression pointed by 'pos'.
  124.      * Generate a stack in upn-order (no more brackets).
  125.      *
  126.      * RC: Pointer to upn-Stack if all went fine, else
  127.      *     ERROR
  128.      */
  129.  
  130.     struct node *argstack=NULL,*tmpstack=NULL;
  131.     int value,brackets=0,len;
  132.     u_short sval;
  133.     char buffer[BUFSIZ],tmpop[2],*pend;
  134.  
  135.     while(pos && *pos)
  136.     {
  137.             /* Is 'pos' a label ? calculate length of assumed label */
  138.         if(pend=strpbrk(pos,"+-*/() \t"))    /* find end of token */
  139.             len=pend-pos;
  140.         else
  141.             len=strlen(pos);
  142.  
  143.         if(len)
  144.         {
  145.             strncpy(buffer,pos,len);
  146.             buffer[len]='\0';
  147.  
  148.             if(!strtoint(plabel,buffer,&sval,PARSE1))    /* is the word a label ? */
  149.             {
  150.                 if(push(&argstack,VALUE,(int)sval))
  151.                     return((struct node *)ERROR);
  152.                 if(pend)
  153.                     pos=pend;
  154.                 else
  155.                     pos+=strlen(pos);
  156.                 while(isspace(*pos))
  157.                     pos++;
  158.                 continue;
  159.             }
  160.             else
  161.                 return((struct node *)ERROR);
  162.         }
  163.         else if(*pos=='(')
  164.         {
  165.             if(push(&tmpstack,SYMBOL,(int)*pos++))
  166.                 return((struct node *)ERROR);
  167.             while(isspace(*pos))    /* skip to next token */
  168.                 pos++;
  169.             brackets++;
  170.  
  171.                 /* Special case: leading minus */
  172.             if(*pos=='-')
  173.             {
  174.                 push(&argstack,VALUE,0);
  175.                 push(&tmpstack,SYMBOL,(int)'-');
  176.                 while(isspace(*++pos));
  177.             }
  178.             continue;            /* continue with next token */
  179.         }
  180.         else if(*pos==')')
  181.         {
  182.             /* move all symbols from 'tmpstack' to 'argstack, until '(' */
  183.             while(tmpstack && tmpstack->value!=(int)'(')
  184.             {
  185.                 if(pop(&tmpstack,&value))
  186.                     return((struct node *)ERROR);
  187.                 if(push(&argstack,SYMBOL,value))
  188.                     return((struct node *)ERROR);
  189.             }
  190.             if(!tmpstack)
  191.             {
  192.                 printf("Open Bracket not found\n");
  193.                 return((struct node *)ERROR);
  194.             }
  195.             if(pop(&tmpstack,&value))
  196.                 return((struct node *)ERROR);
  197.             
  198.             brackets--;                /* decrease brackets */
  199.             while(isspace(*++pos));    /* skip to next token */
  200.             continue;                /* continue with next token */
  201.         }
  202.         else /* no digit,bracket, so it must be a '*+-/' */ 
  203.         {
  204.                 /* Special case: leading minus */
  205.             if( (!argstack) && (*pos=='-'))
  206.             {
  207.                 if(push(&argstack,VALUE,0))
  208.                     return((struct node *)ERROR);
  209.                     
  210.                 if(push(&tmpstack,SYMBOL,(int)'-'))
  211.                     return((struct node *)ERROR);
  212.                 while(isspace(*++pos));
  213.                 continue;
  214.             }            
  215.  
  216.                 /* check if it is a operator */
  217.             tmpop[0]= *pos;    /* generate a string with only first char of buffer*/
  218.             tmpop[1]='\0';
  219.             if(!strpbrk(tmpop,"+-*/"))
  220.                 return((struct node *)ERROR);
  221.  
  222.                 /* It must be an operator */
  223.             if(ishigher(*pos,tmpstack))
  224.             {
  225.                 if(push(&tmpstack,SYMBOL,(int)*pos))
  226.                     return((struct node *)ERROR);
  227.                 if(*pos++=='(')        /* increase brackets */
  228.                     brackets++;
  229.                 while(isspace(*pos))    /* skip to next token */
  230.                     pos++;
  231.                 continue;            /* continue with next token */
  232.             }
  233.             else
  234.             {
  235.                 while(!ishigher(*pos,tmpstack))
  236.                 {
  237.                     if((char)tmpstack->value=='(') /* special case */
  238.                         break;
  239.  
  240.                         /* move Element from 'tmpstack' to 'argstack' */
  241.                     if(pop(&tmpstack,&value))        
  242.                         return((struct node *)ERROR);
  243.                     if(push(&argstack,SYMBOL,value))
  244.                         return((struct node *)ERROR);
  245.                 }
  246.                 if(push(&tmpstack,SYMBOL,(int)*pos)) /* push new Element */
  247.                     return((struct node *)ERROR);
  248.                 while(isspace(*++pos)) /* skip to next token */
  249.                 continue;
  250.             }
  251.         }
  252.     }
  253.     if(brackets)
  254.     {
  255.         printf("Brackets don't match\n");
  256.         return((struct node *)ERROR);
  257.     }
  258.     while(tmpstack)
  259.     {
  260.         if( pop(&tmpstack,&value) || push(&argstack,SYMBOL,value) )
  261.             return((struct node *)ERROR);
  262.     }
  263.     return(argstack);
  264. }
  265.  
  266. static int docalc(struct node **pstack)
  267. {
  268.     /* Calculate the topmost two numbers on stack.
  269.      * Push the result on stack
  270.      * If there are still two numbers on stack, recall the procedure.
  271.      *
  272.      * RC: NULL if all went fine, else
  273.      *     ERROR
  274.      */
  275.  
  276.     int val1,val2,result=0,symbol,next=TRUE;
  277.  
  278.     if( pop(pstack,&val1) || pop(pstack,&val2) || pop(pstack,&symbol) )
  279.         return(ERROR);
  280.  
  281.     if(!next)
  282.       return(NULL);
  283.       
  284.     while(next)
  285.     {
  286.         switch((char)symbol)
  287.         {
  288.             case '*': result=val1*val2; break;
  289.             case '/': result=val1/val2; break;
  290.             case '+': result=val1+val2; break;
  291.             case '-': result=val1-val2; break;
  292.             default : printf("Unknown symbol in upn-Stack\n");
  293.                     return(ERROR);
  294.         }
  295.         if(*pstack && (*pstack)->type==VALUE)
  296.         {
  297.             val1=result;
  298.             if(pop(pstack,&val2) || pop(pstack,&symbol) )
  299.                 return(ERROR);
  300.             continue;
  301.         }
  302.         else
  303.             break;
  304.     }
  305.     if( push(pstack,VALUE,result))
  306.         return(ERROR);
  307.  
  308.     return(NULL);
  309. }
  310.  
  311. static int calcupn(struct node *pupn,u_short *pu_short)
  312. {
  313.     struct node *tmpstack=NULL;
  314.     int cnt=0,tmp;
  315.     
  316.     while(pupn)
  317.     {
  318.         if(pupn->type==SYMBOL)
  319.         {
  320.             cnt=0;
  321.             if( pop(&pupn,&tmp) || push(&tmpstack,SYMBOL,tmp) )
  322.                 return(ERROR);
  323.         }
  324.         else
  325.         {
  326.             cnt++;
  327.             if( pop(&pupn,&tmp) || push(&tmpstack,VALUE,tmp) )
  328.                 return(ERROR);
  329.         }
  330.         if(cnt==2)
  331.         {
  332.             if(docalc(&tmpstack))
  333.                 return(ERROR);
  334.             cnt=1;
  335.         }
  336.     }
  337.     if(pop(&tmpstack,&tmp))
  338.         return(ERROR);
  339.  
  340.     *pu_short=(u_short)tmp;
  341.  
  342.     if(tmpstack || pupn)
  343.     {
  344.         printf("Can't solve Expression\n");
  345.         return(ERROR);
  346.     }
  347.     
  348.     return(NULL);
  349. }
  350.  
  351. int calcexpr(struct listheader *plabel,char *expr,u_short *pu_short)
  352. {
  353.     /*
  354.      * Calculate 'expression'.
  355.      *
  356.      * RC: NULL if all went fine, else
  357.      *     ERROR
  358.      */
  359.  
  360.     struct node *upnstack;
  361.     
  362.     if((struct node *)ERROR==(upnstack=makeupn(plabel,expr)))
  363.         return(ERROR);
  364.  
  365.     if(calcupn(upnstack,pu_short))
  366.         return(ERROR);
  367.  
  368.     return(NULL);
  369. }
  370.