Evaluating expressions

SOME MORE PROGRAMMING - EVALUATING EXPRESSIONS
by Stefan Posthuma

If  you  like to be bored by mindintoxicatingly  boring  boredom, 
you are in for a treat here.  Just read the following article and 
you'll know what I mean.  It is about programming extreme  things 
in GfA,  doing difficult things in general. I wonder where I ever 
got  the  inspiration  to  write  things  that  are  probably  as 
difficult as getting the plastic wrapper of a cassette tape.

Evaluating  expressions has baffled me ever since I got the  idea 
of programming it.  In case you don't know what it is,  take  GfA 
basic, go into direct mode and type something like: Print 1+1

The  computer will do what it is made for and print  2.  It  just 
evaluated an expression,  being '1+1'.  Now this is very  simple, 
but what about something like:

1+2*4^(5-3)-4/(34-2)

Still simple to make a routine that calculates it?  Well,  it can 
be  done,  just  type  it  (and Print of  course)  and  GfA  will 
calculate it for you.  Just think about it. You will have to deal 
with  the  priority of  operators.  Multiplication  comes  before 
addition  and more of that.  Also,  you have to calculate  values 
between  parenthesis  first.  If you don't know  excatly  how  to 
program  it,  it will become hopelessly complicated.  But  I  was 
browsing  through a highly dedicated book on the AWK  programming 
language.  AWK is a text-processing language, most commonly found 
on  the bigger XENIX and UNIX systems.  I use it to  create  nice 
things,  and  the  book was just something I had to read  for  my 
work. But nothing can describe my amazement when I stumbled along 
a small algorithm programmed in the particular AWK language  that 
was able to evaluate expressions of almost unlimited  complexity! 
I immediately tossed the book in my briefcase,  and that night  I 
sat down and loaded GfA 3.0.  It can be done in GfA 2.0, but that 
will be very difficult.

I will now present you with the algorithm, in pseudo-code:

Function Expr()
   a=Muldiv()
   while element = "+" or element = "-"
      if element = "+" then
         add a,Muldiv()   
      else
         sub a,Muldiv()
      endif
   wend
   return a
End Function

Function Muldiv()
   a=Power()
   while element = "*" or element = "/"
      if element = "*" then
         mul a,Power()
      else
         div a,Power()
      end if
      call Getelement()
   wend
   return a
End Function

Function Power()
   a=Factor()
   call Getelement()
   while element = "^"
      a=a^Factor()
      call Getelement()
   wend
   return a
End Function

Function Factor()
   call Getelement()
   if element is a number then
      return element
   else
      if element = "("
         a=Expr()
         if element <> ")"
            error
         endif
         return a
      else
         error
      endif
   endif
End Function

That's it! Maybe it looks a little complicated, but it is easy to 
program. (Providing you use GfA 3.0 or C)

Now instead of giving you the literal GfA code, try to program it 
yourself.  I  will give a couple of hints though,  and the  basic 
source can be found in the programs folder on this disk.

This is the way my routine works:

I construct a string,  let's say E$ which contains the expression 
to be calculated.  You can easily enter program variables into it 
by means of STR$. So you want to calculate the function:

y=x/4

your statements would be this:

E$=str$(x)+"/4"
y=@expr

The  'element'  variable  used in the algorithm is  in  fact  any 
element from the expression. In this case ranging from any number 
to the operators + - * / and ^ and the parenthesis.  You'll  have 
to  write a procedure (called Getelement here) who gets the  next 
element from the string. If you want to simplify things a little, 
assume  that  the  various  elements  from  the  expression   are 
separated by blanks. So "1+-2" will become "1 + -2" which is much 
easier to break apart.  All routines (like Muldiv, Power and Expr 
itself)  will  have to be functions,  because  they  must  return 
values.  The 'Factor' routine will actually get a number from the 
expression (a number is expected) or it will calculate the  value 
of  a new expression between parenthesis by  recursively  calling 
the  Expr function again.  So the string and the pointer  to  the 
next  element in the string will have to be globals (outside  any 
function  or  routine).   In  this  way,  the  number  of  nested 
parenthesis only depends on the size of your stack.

Well,  it  needs  a  little programming  experience  and  a  good 
understanding of the algorithm,  but it is possible. If you don't 
feel like programming,  just take a look at the basic program  as 
to be found in the programs folder on this disk. It is a slightly 
enhanced  version that can also calculate things like  SIN,  COS, 
TAN,  LOG  and  the  likes.  It  is merely  an  addition  to  the 
Getelement  routine that will find the SIN or whatever  function, 
call  Expr (recursion again!) to calculate the value between  the 
parenthesis,  use  this value to calculate the sinus or  whatever 
and  return the obtained number just like there was  an  ordinary 
number in the string.

I wish you lots of succes programming it.

Stefan.
�