Алгоритм упрощения для обратной польской записи
Пару дней назад я играл с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+*
быть доказанным, чтобы быть самым маленьким возможным?Я надеюсь, что вы можете дать некоторые идеи. Заранее спасибо.