Optimizing stack size for evaluating RPN expression

Question

I'm trying to make a program that will basically evaluate a expression in reverse polish notation on a GPU using OpenCL (with different parameter values in parallel).

I have an AST of the expression and I need to convert it to RPN, but since my binary operations are commutative there is more than one way to do this and I need to find one that uses the smallest amount of stack space during evaluation.

As an example, I can sum numbers 1 to 4 with 1 2 + 3 + 4 + (requiring only 2 items on stack at any time) or with 1 2 3 4 + + + (requiring 4 items).

What algorithm can I use to do this?

Answer 1

If all you can rely on is commutativity (or, equivalently, if every operator is implemented in two versions, one of which reverses its arguments) then you can minimize the stack cost by recursively walking the AST, at each node first visiting the most costly child. To compute the cost of a node, a simple recursive computation is performed: the cost of a leaf is one, and the cost of a non-leaf is the cost of its most costly child if the children differ in cost and otherwise one more than the cost of either child. (Another expression is max(max(left, right), min(left, right)+1)). (If you had nodes with more than two children, you'd need a similar but more complicated formula.)

If you can also rely on associativity, allowing you to replace ab+cd++ (cost 3) with ab+c+d+ (cost 2), then you should start by maximally unbalancing the AST.

Answer 2

If all of your binary operations are commutative, you can use a tree balancing algorithm (some examples here). A balanced tree will have minimum depth. Then perform a depth-first traversal of this balanced tree to produce RPN that minimizes stack size.