Kilka dni temu bawiłem sięBefunge który jest ezoterycznym językiem programowania. Befunge używa stosu LIFO do przechowywania danych. Podczas pisania programów cyfry od 0 do 9 są w rzeczywistości instrukcjami Befunge, które przesuwają odpowiednie wartości na stos. Tak więc, na przykład, spowoduje to przesunięcie 7 na stos:

34+

Aby wypchnąć liczbę większą niż 9, obliczenia należy wykonać przy liczbach mniejszych lub równych 9. Dałoby to 123.

99*76*+

Podczas rozwiązywaniaProblem Eulera 1 z Befunge musiałem przesunąć dość dużą liczbę 999 na stos. Tutaj zacząłem się zastanawiać, jak mogę wykonać to zadanie z jak najmniejszą liczbą instrukcji. Pisząc termin w notacji infix i usuwając wspólne czynniki, które wymyśliłem

9993+*3+*

Można również po prostu pomnożyć dwie liczby dwucyfrowe, które dają 999, np.

39*66*1+*

Myślałem o tym przez jakiś czas, a następnie zdecydowałem się napisać program, który wypisuje najmniejsze wyrażenie zgodnie z tymi regułami w odwrotnej notacji polskiej dla dowolnej danej liczby całkowitej. To jest to, co mam do tej pory (napisane w NodeJS z 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*++

Ten fragment kodu konstruuje wyrażenie naiwnie i jest niezwykle długi. Teraz moje pytania:

Czy istnieje algorytm upraszczający wyrażenia w odwrotnej notacji polskiej?Czy uproszczenie byłoby łatwiejsze w notacji infix?Czy takie wyrażenie może być9993+*3+* być sprawdzonym jako najmniejszy z możliwych?

Mam nadzieję, że możesz dać kilka spostrzeżeń. Z góry dziękuję.