Um par de dias atrás eu brinquei comBefunge que é uma linguagem de programação esotérica. Befunge usa uma pilha LIFO para armazenar dados. Quando você escreve programas, os dígitos de 0 a 9 são, na verdade, instruções Befunge, que empurram os valores correspondentes para a pilha. Então, por exemplo, isso empurraria um 7 para empilhar:

34+

Para enviar um número maior que 9, os cálculos devem ser feitos com números menores ou iguais a 9. Isso produziria 123.

99*76*+

Enquanto resolveProblema de Euler 1 com o Befunge eu tive que empurrar o grande número 999 para a pilha. Comecei a me perguntar como poderia realizar essa tarefa com o mínimo de instruções possível. Escrevendo um termo na notação infixa e tirando os fatores comuns, eu inventei

9993+*3+*

Pode-se também simplesmente multiplicar dois números de dois dígitos que produzem 999, e.

39*66*1+*

Eu pensei sobre isso por enquanto e, em seguida, decidi escrever um programa que coloca a menor expressão de acordo com essas regras na notação de polimento inverso para qualquer inteiro dado. Isto é o que eu tenho até agora (escrito em NodeJS com 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*++

Esse trecho de código constrói a expressão ingenuamente e é obviosamente longo. Agora minhas perguntas:

Existe um algoritmo para simplificar expressões na notação de polimento inverso?A simplificação seria mais fácil na notação infixada?Pode uma expressão como9993+*3+* ser prova para ser o menor possível?

Eu espero que você possa dar algumas ideias. Desde já, obrigado.