Vor ein paar Tagen habe ich rumgespieltBefunge Das ist eine esoterische Programmiersprache. Befunge verwendet einen LIFO-Stack zum Speichern von Daten. Beim Schreiben von Programmen sind die Ziffern von 0 bis 9 eigentlich Befunge-Anweisungen, die die entsprechenden Werte auf den Stapel schieben. Zum Beispiel würde dies eine 7 zum Stapeln bringen:

34+

Um eine Zahl größer als 9 zu pushen, müssen Berechnungen mit Zahlen durchgeführt werden, die kleiner oder gleich 9 sind. Dies würde 123 ergeben.

99*76*+

Beim LösenEuler Problem 1 bei befunge musste ich die ziemlich große nummer 999 auf den stapel schieben. Hier begann ich mich zu fragen, wie ich diese Aufgabe mit so wenig Anweisungen wie möglich erledigen könnte. Indem ich einen Begriff in Infixnotation aufschrieb und gemeinsame Faktoren herausstellte, kam ich auf die Idee

9993+*3+*

Man könnte auch einfach zwei zweistellige Zahlen multiplizieren, die 999 ergeben, z.

39*66*1+*

Ich habe eine Weile darüber nachgedacht und dann beschlossen, ein Programm zu schreiben, das den kleinsten Ausdruck nach diesen Regeln in umgekehrter polnischer Notation für eine bestimmte Ganzzahl ausgibt. Folgendes habe ich bisher (in NodeJS mit Unterstrichen geschrieben):

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*++

Dieses Stück Code konstruiert den Ausdruck naiv und ist offensichtlich viel zu lang. Nun meine Fragen:

Gibt es einen Algorithmus zur Vereinfachung von Ausdrücken in umgekehrter polnischer Notation?Wäre die Vereinfachung in der Infixnotation einfacher?Kann ein Ausdruck gefallen9993+*3+* bewiesen werden, der kleinste zu sein, der möglich ist?

Ich hoffe, Sie können einige Einblicke geben. Danke im Voraus.