home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 25 / nopv25.iso / 040A / SNIP9707.ZIP / EVAL.HOW < prev    next >
Encoding:
Text File  |  1997-07-05  |  2.3 KB  |  38 lines
  1. +++Date last modified: 05-Jul-1997
  2.  
  3.   Basically, EVAL.C converts infix notation to postfix notation. If you're
  4. not familiar with these terms, infix notation is standard human-readable
  5. equations such as you write in a C program. Postfix notation is most familiar
  6. as the "reverse Polish" notation used in Hewlett Packard calculators and in
  7. the Forth language. Internally, all languages work by converting to postfix
  8. evaluation. Only Forth makes it obvious to the programmer.
  9.  
  10.   EVAL.C performs this conversion by maintaining 2 stacks, an operand stack
  11. and an operator stack. As it scans the input, each time it comes across a
  12. numerical value, it pushes it onto the operand stack. Whenever it comes
  13. across an operator, it pushes it onto the operator stack. Once the input
  14. expression has been scanned, it evaluates it by popping operands off the
  15. operand stack and applying the operators to them.
  16.  
  17.  For example the simple expression "2+3-7" would push the values 2, 3, and 7
  18. onto the operand stack and the operators "+" and "-" onto the operator stack.
  19. When evaluating the expression, it would first pop 3 and 7 off the operand
  20. stack and then pop the "-" operator off the operator stack and apply it. This
  21. would leave a value of -4 on the stack. Next the value of 2 would be popped
  22. from the operand stack and the remaining operator off of the operator stack.
  23. Applying the "+" operator to the values 2 and -4 would leave the result of
  24. the evaluation, -2, on the stack to be returned.
  25.  
  26.   The only complication of this in EVAL.C is that instead of raw operators
  27. (which would all have to be 1 character long), I use operator tokens which
  28. allow multicharacter operators and precedence specification. What I push on
  29. the operator stack is still a single character token, but its the operator
  30. token which is defined in the 'verbs' array of valid tokens. Multicharacter
  31. tokens are always assumed to include any leading parentheses. For example, in
  32. the expression "SQRT(37)", the token is "SQRT(".
  33.  
  34.   Using parentheses forces evaluation to be performed out of the normal
  35. sequence. I use the same sort of mechanism to implement precedence rules.
  36. Unary negation is yet another feature which takes some explicit exception
  37. processing to process. Other than these exceptions, it's pretty
  38. straightforward stuff.