How do you evaluate arbitrary math expressions using temporary variables instead of a stack? What I’m talking about is translating an expression into an array of simple operations- each that change one variable based on the second argument.
An example list of operations might be:
=
+=
-=
*=
/=
Notice how each operation changes the first argument. (none of them “return” anything)
Here’s a simple expression: (I have postfix with depth written under it as well)
x=2+a*(b+c)
x 2 a b c + * + =
0 1 2 3 4 3 2 1 0
x=c
x+=b
x*=a
x+=2
Notice how you don’t need temporary variables.
Here’s an expression that requires a temporary variable:
x=a*(b+c)+d*(e+f)
x a b c + * d e f + * + =
0 1 2 3 2 1 2 3 4 3 2 1 0
x=b
x+=c
x*=a
tmp=e
tmp+=f
tmp*=d
x+=tmp
I can’t seem to figure out an algorithmic solution for obtaining these sets of operations. Needing temporary variables seems to have something to do with lower-precedence operators that have the result of higher-precedence operators as arguments, but I can’t tell.
I feel stupid… The way seems right in front of me but I can’t see it. Obviously you could do it the “easy” way; AKA, make a temporary variable to store the result of each operation so no operations are destructive to anything but what you put before the =, but that’s bad and I don’t like it. How can you get the “algorithm” for an expression in simplest form?
EDIT: Due to my own ambiguity, I must clarify that a stack is allowed in translation, but not in the end psuedo-language I’m producing.
6
Here is a suggestion.
Create a parse tree. Reorder it so that the deepest part of the tree is to the left, and do this recursively.
Every “rising chain” in the parse tree does not need temporaries. Every time you encounter a node with children on both sides, you will need a temporary. If you process the whole tree, you can discover the maximum number of temporaries that you need at any given time.
I have not tried to show that this greedy solution is truly optimal, but it discovers the best answer in simple cases, and in all cases you’ll come up with an answer with a limited number of temporaries.
4
Here’s a way:
Start with your expression:
x=2+a*(b+c)
Write out the stack operations that would be used:
PUSH b
PUSH c
ADD
PUSH a
MULTIPLY
PUSH 2
ADD
STORE x
Replace PUSH followed by a math operation by an inplace math operation
PUSH b
IADD c
IMULTIPLY a
IADD 2
STORE x
Simply use variables and temps for each position on the stack. The first position will be x, and the rest will be temps
x = b
x += c
x *= a
x += 2
If I’m understanding your problem correctly, look at the algorithms used by compiler to compile expressions for machines with registers while trying to use as few registers as possible. For instance this one is a classic, more modern approaches are using graph coloring.
5
So this would be a problem:
x=(a*b)+(c*d)
Assuming neither a nor b is zero, then factor out the (a*b) term:
x = (1+(c*d)/(a*b))*(a*b)
So:
x=c
x*=d
x/=a
x/=b
x+=1
x*=a
x*=b
As I said, if a or b is zero, you have to pre-reduce the calculation to:
x=c*d
3