Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #112246 > unrolled thread

composition of math expressions in C Language

Back to article view | Back to comp.lang.c

Contents

  composition of math expressions in C Language Rosario19 <Ros@invalid.invalid> - 2017-06-15 12:05 +0200
    Re: composition of math expressions in C Language John Bode <jfbode1029@gmail.com> - 2017-06-15 08:04 -0700
      Re: composition of math expressions in C Language Rosario19 <Ros@invalid.invalid> - 2017-06-16 12:26 +0200
    Re: composition of math expressions in C Language Richard Fateman <fateman@cs.berkeley.edu> - 2017-06-15 09:42 -0700
    Re: composition of math expressions in C Language Keith Thompson <kst-u@mib.org> - 2017-06-15 09:59 -0700

#112246 — composition of math expressions in C Language

/*
Do you like this
function that would find sub expression for composition of math
expressions?

for example:
     Input                output 
[3*(x+4)^2+3*(x+4)^3] [3*y_^2+3*y_^3] [(x+4)]
[3*(x+4)  +3*(x+4)+2] [y_+y_+2] [3*(x+4)]
[3*(x+4)*(x+4)+3] [3*y_*y_+3] [(x+4)]
[3*(x+4)+(x+4)^3] [3*y_+y_^3] [(x+4)]
[x^3+4^2+x^3+4+7] [y_+4^2+y_+4+7] [x^3]
[x^3+4^2+x^3+4^2] [y_+y_] [x^3+4^2]
[x^3+(4)^2+x^3+(4)^3] [y_+(4)^2+y_+(4)^3] [x^3]
[x^3+4444^2+x^3+4444^3] [y_+4444^2+y_+4444^3] [x^3]
[3*(x+4*x^3)^2+3*(x+4*x^3)^3] [3*y_^2+3*y_^3] [(x+4*x^3)]
[3*(x^2+4*x)  +3*(x^2+4*x)+2] [y_+y_+2] [3*(x^2+4*x)]
[3*(x+4*x)+(x+4*x)^3] [3*y_+y_^3] [(x+4*x)]
[x^3+x^9+4^2+x^3+x^9+4+7] [y_+4^2+y_+4+7] [x^3+x^9]
[x^3+4^2+x^3+4^2] [y_+y_] [x^3+4^2]
[x^3+(4)^2+x^3+(4)^3] [y_+(4)^2+y_+(4)^3] [x^3]
[x^3+4444^2+x^3+4444^3] [y_+4444^2+y_+4444^3] [x^3]
[sin(x)^2+9+sin(x)^2] [y_+9+y_] [sin(x)^2]
[3*sin(x)^2+9+3*sin(x)^2+9+1] [y_+y_+1] [3*sin(x)^2+9]

where it would find the max lenght decomposition of the string in
input where
appear x with such decompositio different from x itself
["x^2+x" can not have the valid for me, decomposition "y_^2+y_", "x"]

can you suggest some math expression where this little function fail?
can you show some C language error [or some logic error]?

it is only one little try, possible the way of see the problem is
wrong...

thank you
*/


#define F      for
#define R      return
#define G(a,b) if(a)goto b

int a[256];
void init(void)
{int  i;
 F(i='0';i<='9';++i)a[i]=1;
 F(i='A';i<='Z';++i)a[i|32]=2,a[i]=3;
 a['_']=4;
 a['?']=5;
// a['<']=a['>']=a['=']=6; //l'espressione non e' una uguaglianza ma
l'espressione di una funzione
 a['&']=a['|']=7;
 a['+']=a['-']=8;
 a['*']=a['/']=a['%']=a[':']=9;
 a['^']=10;
 a['~']=11;a['!']=12;
 a[')']=13; // 13+3=16=a['(']
 a[']']=14; // 14+3=17=a['[']
 a['}']=15; // 15+3=18=a['{']
 a['(']=16;
 a['[']=17;
 a['{']=18;
}

int isOpr(int x){R a[x]<13&&a[x]>4;}
int isAlphaNum(int x){R a[x]<5;}

/*

 Input: 
       # ww == una stringa espressione matematica
         con i seguenti operatori matematici e parentesi
         /+-(){}[]:%* [^ inteso come elevamento a potenza]sin() cos()
tan() e 
         tutti gli operatori matematici con la loro precedenza nelle
espressioni matematiche

       # xx == una stringa che contiene il valore di una variabile
dell'espressione
         
 output:
       # return -1 se il processo individua un errore oppure non c'e
altra sostituzione da fare
         che g==x per esempio come in xx="x" ed "sin(x)+cos(x)+x^3"
       
       # return +1 il processo individua la massima sottostringa di ww
che contiene la varabile in xx
         che e' espressione matematica, posta in g
         un altra espressione matematica posta in f
         tali che: in f non compare la variabile in xx
                   in f     compare la sottostringa[variabile] "y_"
                   che sostituendo ad y_, g in f si ottiene ww
ww=f(g(x))

Assegna puntatori ad ogni x
scorre a destra e a sinistra per vedere il massimo che si puo'
prendere
     fa considerazioni sulla massima stringa ottenuta e sull'ultimo
operatore trovato
leva tale stringa dalla string ww
se la stringa differenza non ha x allora la decomposizione e' valida
altrimenti fail
*/
int doComp(char**f, char**g, char*ww,char*xx)
{static char
Ff[10000],Gg[10000],*pt[1024],pl[1024],pr[1024],w[10000],led;
 int i,j,k,pwlen,h,gstart,gend,c,d,lastOpr,kSup,ld;
 char *p,*we,*pp,*g1,*p1,*p2;

 if(led==0){led=1;init();}
 if(f==0||g==0||w==0) R -1;

 // toglie gli spazi e tutti i caratteri non riconosciuti dalla
stringa di partenza
 F(j=i=0;ww[i]&&i<10000;++i)
     if(a[ww[i]])w[j++]=ww[i];  // non e' ammesso altro tipo di
carattere
 if(j>=10000)R-1;
 w[j]=0;

 // Trova le stringhe variablile e mette un puntatore all'inizio
 F(k=i=0; w[i];++i)
     {F(j=0;xx[j]&&w[i+j];++j)
            if(xx[j]!=w[i+j])break;
      if(xx[j]==0)
            {if(k>=1024)R-1;
             pt[k++]=w+i;
            }
     }

 g1=Gg+5000; pwlen=k; we=w+i;
 F(i=0;i<pwlen;++i)pl[i]=1;  // array associato che ricorda quali x
vanno bene

 //Copia la variabile in g1
 F(h=0;(g1[h]=xx[h])&&h<4990;++h);
 if(h>=4990)R-1;

 p=pt[0];
  // max in the left
 F(k=-1;p+k>=w&&k>-4990;--k)
   {c=p[k];
    F(i=1;i<pwlen&&p+k>=w;++i)
            if(pl[i]&&c!=pt[i][k])pl[i]=0;
    F(i=1,d=0;i<pwlen;++i) d+=pl[i];
    G(d==0,e);
    g1[k]=c;
   }
e:
 if(k<=-4990)R-1;
 F(i=0;i<pwlen;++i)pr[i]=1;  // array associato che ricorda quali x
vanno bene

 //in k there is the start of the string
 gstart=     k;
 pp    =g1+k+1; // in pp vi e' la stringa da cui si ottiene g

 // max in the right
 F(k=h;p+k<we&&k<4990;++k)
   {c=p[k];
    F(i=1;i<pwlen&&p+k<we;++i)
         if(pr[i]&&c!=pt[i][k])
                   pr[i]=0;
    F(i=1,d=0;i<pwlen;++i)
                  d+=pr[i];
    G(d==0,v);
    g1[k]=c;
   }
v:
 if(k>=4990)R-1;
 g1[k]=0;

 gend=-gstart+k-1;
 if(k==1&&gstart==0){*f=0;*g=0;R -1;}
 //F(h=0;h<pwlen;++h)   // la stringa massima deve essere la stessa
 //       if(pr[h]!=pl[h])R-1;

 //in pp da 0..gend c'e' la stringa g senza aggiustamenti
 //cerchiamo di aggiustare la stringa g [cambiando gend e pp]

 lastOpr=0;ld=0;  // se c'e' qualche operatore finale ^*+- cambia
lastOpr secondo il valore dell'opeatore
                  // poiche' in tale caso la sostituzione sara' +
piccola
 if(isOpr(pt[0][k]))
    F(i=0;i<pwlen&&p+k<we ;++i)
       {c=a[pt[0][k]];
        if(c>4 && c<13 && c>lastOpr)lastOpr=c;
       }
 else if(isOpr(pt[0][k-1])) // assegna il valore di lastOpr
    F(ld=1,i=0;i<pwlen&&p+k<we ;++i)
       {c=a[pt[0][k-1]];
        if(c>4 && c<13 && c>lastOpr)lastOpr=c;
       }
 // assegna i puntatori ad ogni elemento distinto della stringa g
 pt[0]=pp; c=a[pp[0]];
 F(k=i=1;i<gend; ++i)   // se e' una parentesi considera come unita'
se invece sono + simboli operatori unico operatore
     if(c!=a[pp[i]]||(c>12&&c<19))
          {if(k>=1024)R-1;c=a[pp[i]];pt[k++]=pp+i;}
 kSup=k;
 // 3*(x+4)^  =>   x+4
 // controlla l'eventuale ultimo operatore con l'altro operatore

 if(lastOpr)
    {if(ld&&k>1)      {pt[k-1][0]=0;gend-=1;--kSup;k-=2;}
     else if(k<=1)R-1;
     else             {                            k-=1;}
     p1=pt[0]; p2=pt[k];     // p1..p2 la string pp
     c=a[pt[k][0]];
     if(c==13||c==14||c==15) // c'e' una parentesi chiusa
        {
         F(--k;k>=0;--k)          // cerca una parentesi aperta dello
stesso tipo
             if(c+3==a[pt[k][0]])break;
         if(k<0)R-1;
         G(k==0,a3);
         // cerca l'altro operando
         if(!isOpr(pt[k][0]))
            F(--k;k>=0;--k)
                if(isOpr(pt[k][0]))break;
         if(k<0)R-1;
         if(a[pt[k][0]]<lastOpr)
            {p2=pt[kSup-1]; // leva l'ultima parentesi
             if(pt[k+1]<g1) 
                  p1=pt[k+1];    // parte dall'ultima parentesi
interna
             else if(k>=1) p2=pt[k-1];       // caso
[x^3+(4)^2+x^3+(4)^3] [y_+(4)^2+y_+(4)^3] [x^3]
            }
        }
     else
        {//cerca l'operatore precedente
         if(!isOpr(pt[k][0]))
            F(--k;k>=0;--k)
                if(isOpr(pt[k][0]))break;
         if(k<0)R-1;
         if(a[pt[k][0]]<lastOpr)
            {p2=pt[k-1];
            }
         else p2=pt[kSup-1];
        }
a3:  if(isOpr(pt[0][0])) p1=pt[1];
     pp=p1;
     p2[1]=0;
     gend=p2-p1+1;
    }

 // 3*(x+4)+  =>3*(x+4)
 //(3*(x+4))  =>3*(x+4)
 //  |x^3+5|^2 + x^3+5^4  => x^3
 //  x^3+5+2 + x^3+5+4  => x^3+5
 //  |x^3+5|*2 + x^3+5+4  => x^3
 //  |x^3+5|-2 + x^3+5+4  => x^3+5
 // 3*(x+4)   =>3*(x+4) se tutti gli operatori seguenti sono +-*/ mai
^ [precedenza]
 //           =>   x+4    
 *g=pp;

 F(j=i=0,c=pp[0];w[i]&&j<9990;++i)
   {d=w[i];
    if(d==c)
       {F(k=0;k<gend&&w+i+k<we&&w[i+k]==pp[k];++k);
        if(k==gend)
          {i=i+k-1;Ff[j++]='y';Ff[j++]='_';continue;}
       }
    Ff[j++]=d;
   }
 Ff[j]=0;
 *f=Ff;
 if(strstr(Ff,xx)){*f=0;*g=0;R -1;}
 R 1;
}



int main()
{int  i,j;
 char *w="3*(x+4)^2+3*(x+4)^3", *x="x",*f, *g;
 char*cases[]={"3*(x+4)^2+3*(x+4)^3",
                "3*(x+4)  +3*(x+4)+2",
                "3*(x+4)*(x+4)+3",
                "3*(x+4)+(x+4)^3",
                "x^3+4^2+x^3+4+7",
                "x^3+4^2+x^3+4^2",
                "x^3+(4)^2+x^3+(4)^3",
                "x^3+4444^2+x^3+4444^3",
                "3*(x+4*x^3)^2+3*(x+4*x^3)^3",
                "3*(x^2+4*x)  +3*(x^2+4*x)+2",
                "3*(x^3+4*x^2)*(x^3+4*x^8)+3",
                "3*(x+4*x)+(x+4*x)^3",
                "x^3+x^9+4^2+x^3+x^9+4+7",
                "x^3+4^2+x^3+4^2",
                "x^3+(4)^2+x^3+(4)^3",
                "x^3+4444^2+x^3+4444^3",
                "sin(x)^2+9+sin(x)",
                "sin(x)^2+9+sin(x)^2",
                "3*sin(x)^2+9+3*sin(x)^2+9+1",
                "sin(x)+cos(x)+x^3"
                };

 F(j=0;j<20;++j)
    {i=doComp(&f,&g,cases[j],x);
     if(i!=-1&&f&&g)
     printf("[%s] [%s] [%s]\n", cases[j], f, g);
    }

 R 0;
}

[toc] | [next] | [standalone]

#112264

On Thursday, June 15, 2017 at 5:05:48 AM UTC-5, Rosario19 wrote:
> /*
> Do you like this

[snip remainder]

That has to be some of the *least* readable code I've ever seen outside of
the IOCCC.  Bravo.  I especially like how you hide gotos behind a macro -
that's extra sneaky and evil.  

gcc does throw up some warnings on it - implicit declaration of strstr and
printf, some bitching about using a char as an array subscript.  

Can't comment on the logic because there is no way in *hell* that I would
spend any time trying to detangle that mess.  Trying to read it is literally
giving me a headache.

[toc] | [prev] | [next] | [standalone]

#112331

On Thu, 15 Jun 2017 08:04:40 -0700 (PDT), John Bode wrote:
>On Thursday, June 15, 2017 at 5:05:48 AM UTC-5, Rosario19 wrote:
>> /*
>> Do you like this
>
>[snip remainder]
>
>That has to be some of the *least* readable code I've ever seen outside of
>the IOCCC.  Bravo.  I especially like how you hide gotos behind a macro -
>that's extra sneaky and evil.  
>
>gcc does throw up some warnings on it - implicit declaration of strstr and
>printf, some bitching about using a char as an array subscript.  
>
>Can't comment on the logic because there is no way in *hell* that I would
>spend any time trying to detangle that mess.  Trying to read it is literally
>giving me a headache.

it would be implement in a pc the way we search in one math furmula
the sub formula that contain the variable x that has max lenght

it fail in "(x+4)*(x-4)+3" infact return g=(x+4) instead of
g=(x+4)*(x+4) 

if code seems a little difficult possible it is because operations are
not so easy

[toc] | [prev] | [next] | [standalone]

#112274

I think that you are trying to do  functional decomposition, which
has been investigated before.
See
https://en.wikipedia.org/wiki/Polynomial_decomposition

Writing a program using a computer algebra system, or
in Lisp, would probably allow you to work on the essential
algorithms rather than writing a stand-alone parser + stuff.

RJF

On 6/15/2017 3:05 AM, Rosario19 wrote:
> /*
> Do you like this
> function that would find sub expression for composition of math
> expressions?
> 

[toc] | [prev] | [next] | [standalone]

#112276

Rosario19 <Ros@invalid.invalid> writes:
> /*
> Do you like this
> function that would find sub expression for composition of math
> expressions?
[...]
> #define F      for
> #define R      return
> #define G(a,b) if(a)goto b

No.

(I see you've changed your "From:" header again.  Time for another entry
in my killfile.)

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web