Backtracking.
By SalimMeghani
- 385 reads
Backtracking.
By Salim Shahbudeen Meghani.
Suppose in a worksheet, you have the numbers 1,2,3 in cells a1,a2,a3. In cell a5 you have the formula =a1+a2*a3, and in cell a6 you have =a5/2. The point is this how is a6 evaluated?
Well I do it like this (in my Spreadsheet program):-
We say a6 is dependent on a5.
a6, (contains, =a5/2) is a formula referring to a formula in cell a5, .
=a1+a2*a3, so, to solve a formula dependency you add brackets, and copy the formula over.
Like this: =(a1+a2*a3)/2.
We stop at this point, because all that is now being referred to are numbers in a1, a2 & a3.
So, this formula, is the lowest level algebraic formula for a6.
When we solve formula dependency in this way, we are saying that each bracketed formula expression is an unique entity. Therefore by looking at the original formula, and comparing it to its backtrace we can derive mathematical entity relationships.
I say this is 'genetic' because the formula is always broken down to its basic numerical values. Like this : (1+2*3)/2.
In my Spreadsheet program, I convert to numbers (in the way described above), then, I use a Reverse Polish Parser to solve the problems of precedence. The following two functions, create a lowest level algebraic formula. Within the Parser (the second function (not reverse polish) function, when uniq=0, then the lowest level algebraic formula is returned. When uniq=1, then numerical values are returned.
// Convert a formula to its raw native numeric form (including brackets).
double expr_p(int *error, char *form, int qol, int rw)
{
char *source=NULL, *form9=NULL,
*dest=NULL;
int start=0,
pvalue=0, end=0,
bracket=0,
length=0;
double answer=0;
source=(char *) calloc((unsigned long) 32767, sizeof(char));
dest=(char *) calloc((unsigned long) 32767, sizeof(char));
form9=(char *) calloc((unsigned long) 32767, sizeof(char));
strcpy(source, form);
strcpy(form9, form);
clr_str(genetic);
while ((fcat)&&(*error==0))
{
fcat=0;
parser(error, form9,dest,qol,rw,0);
strcpy(form9,dest);
strcat(form9,"#");
free(dest);
dest=(char *) calloc((unsigned long) 32767, sizeof(char));
}
strcpy(genetic,form9);
fcat=1;
while ((fcat)&&(*error==0))
{
fcat=0;
parser(error, source,dest,qol,rw,1);
strcpy(source,dest);
strcat(source,"#");
free(dest);
dest=(char *) calloc((unsigned long) 32767, sizeof(char));
}
fcat=1;
//
if ((!*error) && (preced==1))
{
newyk=(char *) calloc((unsigned long) 32767, sizeof(char));
length=strlen(source)-1;
source[length]='\0';
clr_str(newyk);
strcpy(newyk,"%");
strcat(newyk,source);
if ((!isdigit(source[length-1])) && (!(source[length-1]==')'))) *error=1;
else strcat(newyk,"%\0");
if ((source[length-1]=='+') || (source[length-1]=='-')) *error=1;
length=0;
if (!*error) ans=eval_parser(newyk, error);
free(newyk);
clear_vars();
}
else
ans=0;
free(source);
free(dest);
free(form9);
if (*error==0)
{
*rtype='F';
return (ans);
}
else
return (0);
}
// This function does the conversion from formula to a string of numbers.
void parser(int *error, char *source, char *dest, int qol, int rw, int uniq)
{
int gloop=0;
int dloop=0;
int crloop=0, drloop=0;
int alloop=0;
int locx=0;
int locy=0;
int pvalue=0;
char cref[20];
char alpp[20];
char zalpp[20];
char num[20];
while (source[gloop]!='#')
{
while(isdigit(source[gloop]) || isstop(source[gloop]) ||
isoperator(source[gloop]) || isbracket(source[gloop]) ||
(source[gloop]=='E') || ( (gloop>=1) &&
isdigit(source[gloop-1]) && (source[gloop]=='e')))
{
dest[dloop]=source[gloop];
dloop++;
gloop++;
}
if (source[gloop]=='#') break;
crloop=0;
if (isalpha(source[gloop]))
{
do
{
cref[crloop]=source[gloop];
crloop++; gloop++;
}
while (isdigit(source[gloop])||
isalpha(source[gloop]));
}
cref[crloop]='\0';
crloop=0;
alloop=0;
while(isalpha(cref[crloop]))
{
alpp[alloop]=cref[crloop];
crloop++;
alloop++;
}
alpp[alloop]='\0';
if (alloop==1)
locx=alpp[0]-96;
else
if (alloop==2)
locx=((alpp[0]-96)*26)+alpp[1]-96;
else
{
locx=0;
*error=1;
return;
}
if (uniq==0)
strcpy(zalpp,alpp);
alloop=0;
clr_str(alpp);
while (isdigit(cref[crloop]))
{
alpp[alloop]=cref[crloop];
crloop++;
alloop++;
}
alpp[alloop]='\0';
locy=atoi(alpp);
if ((locx<1)||(locx>100))
{
*error=1;
return;
}
if ((locy<1)||(locy>100))
{
*error=1;
return;
}
pvalue=(locx-1)*100+locy;
rtype=srtype+pvalue;
if (*rtype=='E')
{
*error=1;
return;
}
if ((locx==qol)&&(locy==rw))
{*error=1;
*rtype='E';
return;}
else *rtype='F';
pvalue=((locx-1)*100)+locy;
type=stype+pvalue;
rtype=srtype+pvalue;
if (*type=='N')
{
if (uniq==0)
{
strcat(dest, zalpp);
dloop+=strlen(zalpp);
}
if (uniq==0)
{
strcat(dest, alpp);
dloop+=strlen(alpp);
}
if (uniq==1)
{
numeric=snumeric+pvalue;
sprintf(num, "%e",*(*numeric));
strcat(dest,num);
dloop+=strlen(num);
}
}
clr_str(cref); clr_str(alpp);
if (*type=='F')
{
dest[dloop]='(';
dloop+=1;
cell=scell+pvalue;
strncat(dest,*cell,(strlen(*cell)-1));
dloop+=strlen(*cell)-1;
dest[dloop]=')';
dloop+=1;
fcat=1;
}
if (*type=='E'|| *type=='S')
{
*error=1;
return;
}
}
- Log in to post comments