Fastening the run-time interpretation of mathematical expressions

I am writing a piece of software that accept in input the definition
of a mathematical function and a list of points in which evaluate the
function and puts the result in output. The main feature of the progam
is that once the function definition is read, the program evaluates
the function very fast [Well this isn't done already...]. I was
thinking to build a pair of stacks, one containig the operands
(floats) and the other containig the operators (function pointers).


For each evaluation the following steps should be done:
Duplicate the operands stack
Do the operations (modifying the duplicated stack)


The operations are as simple as a function call (through a pointer),
the matheatical operation itself and the stack update (that is moving
the pointer and writing the resulting data).


Question 1: Is this a fast method to do the stuff (given that the
function is known at run time and I do not want to generate the
assebler code for portability sake).


Parsing the function definitions (using Bison) gives the RPN
representation of the expression, that is near the two stack
representation, but it is not exactly that. The gramar is:


%token <val> NUM /*float representation*/
%token <name> ID /*name starting with [a-zA-Z_] */
%left '-' '+'
%left '*' '/'
%left NEG /* negation--unary minus */
%right '^' /* exponentiation */


exp: NUM {printf(" %g",$1);}
                | ID {printf(" #%s",$1);}
                | ID '(' exp ')' {printf(" @%s",$1);}
                | exp '+' exp {printf(" +");}
                | exp '-' exp {printf(" -");}
                | exp '*' exp {printf(" *");}
                | exp '/' exp {printf(" /");}
                | '-' exp %prec NEG {printf(" neg");}
                | exp '^' exp {printf(" ^");}
                | '(' exp ')'
;


Given the RPN expression
1 2 + 3 *
in the two stack forms is (the left of the string is the top of the
stack):
|1 2 3| |+ *|
which can also mean RPN
1 2 3 + *


Things would be much easier if all the RPN would be in a form that in
every step of the evaluation would be true the following:
On the top of the stack there are n operand followed by the operator
(taking n operands) that conusumes them.


For example 1 2 3 + * could be rewritten 2 3 + 1 *


Question 2: Is always possible to rewrite the expression in the form I
said? How could I do it automatically?


Some more examples:


2^(3+4) -> 2 3 4 + ^ -> 3 4 + 2 commutate^
where commutate-operator is an operator that swaps its operands [ a
commutate^ b = b^a]


4+3*(2+1) -> 4 3 2 1 + * + -> 2 1 + 3 * 4 +


I didn't find any case in which the conversion is impossble.


Thnx for reading this message,
any help is wellcome


Paolo Pantaleo
[This seems much more complicated than it needs to be. The usual way to
do an RPN interpreter is to make the RPN a string of tokens, and then
for the interpreter to run through the set of tokens, popping arguments
and pushing results for each operator, with the result left on the top
of the stack. Only one stack needed, no stack copying, and no RPN
rewriting. -John]

Return to the comp.compilers page.
Search the comp.compilers archives again.