title: Optimizing stack size for evaluating RPN expression
body: <p>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).</p>
  
  <p>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.</p>
  
  <p>As an example, I can sum numbers 1 to 4 with <code>1 2 + 3 + 4 +</code> (requiring only 2 items on stack at any time) or with <code>1 2 3 4 + + +</code> (requiring 4 items).</p>
  
  <p>What algorithm can I use to do this? </p>