Hace un par de días jugué un rato conBefunge que es un lenguaje de programación esotérico. Befunge utiliza una pila LIFO para almacenar datos. Cuando escribe programas, los dígitos del 0 al 9 son en realidad instrucciones Befunge que colocan los valores correspondientes en la pila. Así que por ejemplo esto empujaría un 7 para apilar:

34+

Para presionar un número mayor que 9, los cálculos deben hacerse con números menores o iguales a 9. Esto daría 123.

99*76*+

Mientras se resuelveEuler problema 1 con Befunge tuve que empujar el número bastante grande 999 a la pila. Aquí comencé a preguntarme cómo podría realizar esta tarea con la menor cantidad de instrucciones posible. Al escribir un término en notación infija y eliminar los factores comunes que se me ocurrieron

9993+*3+*

Uno también podría simplemente multiplicar dos números de dos dígitos que producen 999, por ej.

39*66*1+*

Pensé en esto por un tiempo y luego decidí escribir un programa que expresara la expresión más pequeña de acuerdo con estas reglas en notación de pulido inverso para cualquier entero dado. Esto es lo que tengo hasta ahora (escrito en NodeJS con underscorejs):

var makeExpr = function (value) {
    if (value < 10) return value + "";
    var output = "", counter = 0;
    (function fn (val) {
        counter++;
        if(val < 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 > 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*++

Este fragmento de código construye la expresión ingenuamente y, obviamente, es demasiado largo. Ahora mis preguntas:

¿Hay un algoritmo para simplificar expresiones en notación de pulido inverso?¿Sería más fácil la simplificación en la notación de infijo?¿Puede una expresión como9993+*3+* ¿Ser probado para ser el más pequeño posible?

Espero que puedan dar algunas ideas. Gracias por adelantado.