反向波兰语表示法的简化算法

一尘不染

反向波兰语表示法的简化算法

algorithm

几天前，我玩了
一种深奥的编程语言Befunge。Befunge使用LIFO堆栈来存储数据。当您编写程序时，从0到9的数字实际上是Befunge指令，会将相应的值压入堆栈。因此，例如，这将把7压入堆栈：

34+

为了使数字大于9，必须使用小于或等于9的数字进行计算。这将产生123。

99*76*+

在用Befunge
解决Euler问题1时，我不得不将相当大的数字999推入堆栈。在这里，我开始想知道如何用尽可能少的指令来完成此任务。通过写下一个用中缀表示法的术语并排除常见的因素，我想到了

9993+*3+*

一个人也可以简单地将两个两位数相乘得到999，例如

39*66*1+*

我考虑了一会儿，然后决定编写一个程序，针对任何给定的整数，根据这些规则以反波兰表示法推出最小的表达式。这是我到目前为止（用underscorejs用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+*证明像这样的表达式是最小的吗？

希望您能提供一些见解。提前致谢。

阅读 297

2020-07-28

共1个答案

一尘不染

也有93*94*1+*，基本上是27*37。

如果要解决这个问题，我首先要尝试将数字平均分配。因此给定999，我将除以9得到111。然后尝试除以9、8、7等，直到发现111为3 * 37。

37是质数，所以我贪婪地除以9，得到4的余数为1。

这似乎给了我尝试过的一半最佳结果。当然，要进行偶数除法测试会有点贵。但是也许不比生成一个太长的表达式更昂贵。

使用此，将变为100 55*4*。102解决29*5*6+。

101提出了一个有趣的案例。101/9 =（9 * 11）+ 2，或者（9 * 9）+20。让我们来看看：

983+*2+  (9*11) + 2
99*45*+  (9*9) + 20

直接生成后缀还是生成中缀并转换更容易，我真的不知道。我可以看到每种方法的优缺点。

无论如何，这就是我要采取的方法：先尝试平均分配，然后再用9贪婪地分配。不确定确切的结构。

弄清楚之后，我肯定希望看到您的解决方案。

编辑

这是一个有趣的问题。我想出了一个递归函数，该函数可以可靠地生成后缀表达式，但这并不是最佳选择。它在C＃中。

string GetExpression(int val)
{
    if (val < 10)
    {
        return val.ToString();
    }
    int quo, rem;
    // first see if it's evenly divisible
    for (int i = 9; i > 1; --i)
    {
        quo = Math.DivRem(val, i, out rem);
        if (rem == 0)
        {
            // If val < 90, then only generate here if the quotient
            // is a one-digit number. Otherwise it can be expressed
            // as (9 * x) + y, where x and y are one-digit numbers.
            if (val >= 90 || (val < 90 && quo <= 9))
            {
                // value is (i * quo)
                return i + GetExpression(quo) + "*";
            }
        }
    }

    quo = Math.DivRem(val, 9, out rem);
    // value is (9 * quo) + rem
    // optimization reduces (9 * 1) to 9
    var s1 = "9" + ((quo == 1) ? string.Empty : GetExpression(quo) + "*");
    var s2 = GetExpression(rem) + "+";
    return s1 + s2;
}

对于999，它生成9394*1+**，这是最佳的。

这将生成值<= 90的最佳表达式。0到90之间的每个数字都可以表示为两个一位数字的乘积，也可以表示为形式(9x + y)，其中x和y是一位数字。但是，我不知道这保证了大于90的值的最佳表达。

2020-07-28