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

也有

93*94*1+*

27*37

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

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

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

使用此，将变为100

55*4*

29*5*6+

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

983+*2+  (9*11) + 299*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