Algorithms – How to Evaluate Math Expressions Without a Stack

algorithmslanguage-agnostic

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.

Best Answer

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.

Related Topic