Алгоритм упрощения для обратной польской записи

Пару дней назад я играл сBefunge который является эзотерическим языком программирования. Befunge использует стек LIFO для хранения данных. Когда вы пишете программы, цифры от 0 до 9 на самом деле являются инструкциями Befunge, которые помещают соответствующие значения в стек. Таким образом, для примера это будет 7 к стеку:

34+

Чтобы нажать число больше 9, вычисления должны быть выполнены с числами, меньшими или равными 9. Это даст 123.

99*76*+

При решенииПроблема Эйлера 1 с Befunge мне пришлось положить довольно большое число 999 в стек. Здесь я начал задаваться вопросом, как я мог выполнить эту задачу, используя как можно меньше инструкций. Написав термин в инфиксной нотации и вычеркнув общие факторы, я придумал

9993+*3+*

Можно также просто умножить два двузначных числа на 999, например,

39*66*1+*

Я подумал об этом некоторое время, а затем решил написать программу, которая выдает наименьшее выражение в соответствии с этими правилами в обратной польской записи для любого заданного целого числа. Это то, что у меня есть (написано в NodeJS с подчеркиванием):

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

Этот кусок кода конструирует выражение наивно и явно длинно. Теперь мои вопросы:

Есть ли алгоритм для упрощения выражений в обратной польской записи?Будет ли упрощение в инфиксной записи проще?Может ли выражение как9993+*3+* быть доказанным, чтобы быть самым маленьким возможным?

Я надеюсь, что вы можете дать некоторые идеи. Заранее спасибо.

Ответы на вопрос(4)

Ваш ответ на вопрос