反向波兰语符号的简化算法 [英] Simplification Algorithm for Reverse Polish Notation

问题描述

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

A couple of days ago I played around with Befunge which is an esoteric programming language. Befunge uses a LIFO stack to store data. When you write programs the digits from 0 to 9 are actually Befunge-instructions which push the corresponding values onto the stack. So for exmaple this would push a 7 to stack:

34 +

要推入大于9的数字，必须使用小于或等于9的数字进行计算。这将得出123。

In order to push a number greater than 9, calculations must be done with numbers less than or equal to 9. This would yield 123.

99 * 76 * +

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

While solving Euler Problem 1 with Befunge I had to push the fairly large number 999 to the stack. Here I began to wonder how I could accomplish this task with as few instructions as possible. By writing a term down in infix notation and taking out common factors I came up with

9993 + * 3 + *

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

One could also simply multiply two two-digit numbers which produce 999, e.g.

39 * 66 * 1 + *

我考虑了一段时间，然后决定编写一个程序，将最小的表达式根据这些规则，对于任何给定的整数，使用反向抛光符号。到目前为止，这是我所拥有的（用underscorejs用NodeJS编写）：

I thought about this for while and then decided to write a program which puts out the smallest expression according to these rules in reverse polish notation for any given integer. This is what I have so far (written in NodeJS with underscorejs):

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

代码天真地构造了表达式，而且很长。现在我的问题是：

This piece of code constructs the expression naively and is obvously way to long. Now my questions:

• 是否有一种算法可以简化反波兰表示法中的表达式？


• 会


• 是否可以证明像 9993 + * 3 + * 这样的表达式是最小的表达式？

• Is there an algorithm to simplify expressions in reverse polish notation?
• Would simplification be easier in infix notation?
• Can an expression like 9993+*3+* be proofed to be the smallest one possible?

我希望您能提供一些见解。

I hope you can give some insights. Thanks in advance.

推荐答案

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

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

Were I to attack this problem, I'd start by first trying to evenly divide the number. So given 999 I would divide by 9 and get 111. Then I'd try to divide by 9, 8, 7, etc. until I discovered that 111 is 3*37.

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

37 is prime, so I go greedy and divide by 9, giving me 4 with a remainder of 1.

这似乎为我提供了一半的最佳结果我尝试过的当然，要进行偶数除法测试会有点贵。

That seems to give me optimum results for the half dozen I've tried. It's a little expensive, of course, testing for even divisibility. But perhaps not more expensive than generating a too-long expression.

使用此格式，100变为 55 * 4 * 。 102计算出 29 * 5 * 6 + 。

Using this, 100 becomes 55*4*. 102 works out to 29*5*6+.

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

101 brings up an interesting case. 101/9 = (9*11) + 2. Or, alternately, (9*9)+20. Let's see:

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

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

Whether it's easier to generate the postfix directly or generate infix and convert, I really don't know. I can see benefits and drawbacks to each.

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

Anyway, that's the approach I'd take: try to divide evenly at first, and then be greedy dividing by 9. Not sure exactly how I'd structure it.

确定后，我一定希望看到您的解决方案。

I'd sure like to see your solution once you figure it out.

这是一个有趣的问题。我想出了一个递归函数，该函数在生成后缀表达式方面做得很可靠，但这并不是最佳选择。

This is an interesting problem. I came up with a recursive function that does a credible job of generating postfix expressions, but it's not optimum. Here it is in 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 + ** ，我认为是最佳的。

For 999 it generates 9394*1+**, which I believe is optimum.

这会生成值<== 90的最佳表达式。从0到90的每个数字都可以表示为两个一位数字的乘积，或者是形式为（9x + y）的表达式，其中 x 和 y 是一位数字。但是，我不知道这样可以保证值大于90的最优表达式。

This generates optimum expressions for values <= 90. Every number from 0 to 90 can be expressed as the product of two one-digit numbers, or by an expression of the form (9x + y), where x and y are one-digit numbers. However, I don't know that this guarantees an optimum expression for values greater than 90.

这篇关于反向波兰语符号的简化算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！