title: Simplification Algorithm for Reverse Polish Notation
body: <p>A couple of days ago I played around with  <a href="https://en.wikipedia.org/wiki/Befunge" rel="nofollow">Befunge</a> which is an esoteric programming language. Befunge uses a LIFO stack to store data. When you write programs the digits from 0 to 9 are actually Befunge-instructions which push the corresponding values onto the stack. So for exmaple this would push a 7 to stack:</p>
  
  <p><code>34+</code></p>
  
  <p>In order to push a number greater than 9, calculations must be done with numbers less than or equal to 9. This would yield 123.</p>
  
  <p><code>99*76*+</code></p>
  
  <p>While solving <a href="https://projecteuler.net/problem=1" rel="nofollow">Euler Problem 1</a> with Befunge I had to push the fairly large number 999 to the stack. Here I began to wonder how I could accomplish this task with as few instructions as possible. By writing a term down in infix notation and taking out common factors I came up with</p>
  
  <p><code>9993+*3+*</code></p>
  
  <p>One could also simply multiply two two-digit numbers which produce 999, e.g.</p>
  
  <p><code>39*66*1+*</code></p>
  
  <p>I thought about this for while and then decided to write a program which puts out the smallest expression according to these rules in reverse polish notation for any given integer. This is what I have so far (written in NodeJS with underscorejs):</p>
  
  <pre><code>var makeExpr = function (value) {
      if (value &lt; 10) return value + "";
      var output = "", counter = 0;
      (function fn (val) {
          counter++;
          if(val &lt; 9) { output  += val; return; };
          var exp = Math.floor(Math.log(val) / Math.log(9));
          var div = Math.floor(val / Math.pow(9, exp));
          _( exp ).times(function () { output += "9"; });
          _(exp-1).times(function () { output += "*"; });
          if (div &gt; 1) output += div + "*";
          fn(val - Math.pow(9, exp) * div);    
      })(value);
      _(counter-1).times(function () { output+= "+"; });
      return output.replace(/0\+/, "");
  };
  
  makeExpr(999);
  // yields 999**99*3*93*++
  </code></pre>
  
  <p>This piece of code constructs the expression naively and is obvously way to long. Now my questions: </p>
  
  <ul>
  <li>Is there an algorithm to simplify expressions in reverse polish notation?</li>
  <li>Would simplification be easier in infix notation?</li>
  <li>Can an expression like <code>9993+*3+*</code> be proofed to be the smallest one possible?</li>
  </ul>
  
  <p>I hope you can give some insights. Thanks in advance.</p>