逆波兰表达式(Postfix)中的可变长度运算符

Question

背景： 在传统的逆波兰式中，所有操作符必须具有固定长度，这使得RPN易于通过代码进行评估和操作，因为每个标记、表达式和子表达式都是“自包含”的，这样可以盲目地将x y *中的y替换为y 1 +以获得x y 1 + *，这是另一个有效的表达式，可以按照您想要的方式执行。 这里是一个带有命名变量支持的简单RPN计算器的交互演示。请注意，演示尝试呈现算法的要点；它们不相关或代表生产代码。

var rpn = prompt("Please enter RPN string, where each token is " +
  "separated by a space", "x 1 x + * 2 /").trim().split(/\s+/);

var stack = [], variables = [], values = [];
for (let i = 0, len = rpn.length|0; i < len; i=i+1|0) {
    if (/^\d*(\.\d*)?$/.test(rpn[i]) && rpn[i] !== "") {
        stack.push( rpn[i] );
    } else if (/^[a-z]$/i.test(rpn[i])) {
        stack.push( rpn[i] );
        if (!~variables.indexOf(rpn[i])) variables.push( rpn[i] );
    } else {
        if(stack.length<2)throw Error("No operand for " + rpn[i]);
        const firstPop = stack.pop(); //lacks check if stack empty
        stack.push( "(" + stack.pop() + rpn[i] + firstPop + ")" );
    }
}
if (stack.length !== 1) throw Error("Invalid RPN got: " + stack);

for (let i = 0, len = variables.sort().length|0; i < len; i=i+1|0)
    values[i] = +prompt(variables[i] + " = ", Math.random()*10|0);

variables.push("'use strict';return(" + stack.pop() + ")");
alert("Result: " + Function.apply(0, variables).apply(0, values));

问题：如何修改或调整逆波兰表达式（RPN）以适应可变长度的“操作符”（比如函数）？ 研究和解决方案：我使用逆波兰表达式作为代码在最终转换为指定编程语言之前的中介表示形式。我希望尽可能保留 RPN 的实用性和易用性，同时仍能表示可变长度的操作符。因此我提出了三个解决方案并在下面的简单演示程序中进行了实现。

1. 一个特殊的ARGUMENTS_BEGIN 前缀操作符（我们将使用 # 自行理解）。这个解决方案与传统的逆波兰表达式相悖，因为它增加了前缀操作符来表示参数开始的位置。这使得参数列表可以自动扩展，并有助于调试，因为没有格式不正确的标记替换会干扰参数列表，从而可以更容易地定位错误。由于需要处理嵌套函数调用等情况，这可能使参数操作更加复杂，但我并不确定所有可能会遇到的并发情况。我猜测会遇到语法解析中包括前缀和后缀操作符的一些障碍。直接评估也更困难，因为需要回溯或单独的堆栈来找到参数的开始。

var rpn = prompt("Please enter a RPN string, where each token is " +
  "separated by a space", "# # x 210 gcd x 6 * 126 gcd").trim()
  .split(/\s+/);

var stack = [], variables = [], values = [];
for (let i = 0, len = rpn.length|0; i < len; i=i+1|0) {
    if (/^\d*(\.\d*)?$/.test(rpn[i]) && rpn[i] !== "") {
        stack.push( rpn[i] );
    } else if (/^[a-z]$/i.test(rpn[i])) {
        stack.push( rpn[i] );
        if (!~variables.indexOf(rpn[i])) variables.push( rpn[i] );
    } else if (/^[a-z]\w*$/i.test(rpn[i])) {
        const s = stack.lastIndexOf("#");
        if(s<0) throw Error("No start of arguments to " + rpn[i]);
        stack.push( rpn[i]+"(" + stack.splice(s).slice(1) + ")" );
    } else if (rpn[i] === '#') {
        stack.push( '#' ); // sparks a syntax error if misused
    } else {
        if(stack.length<2)throw Error("No operand for " + rpn[i]);
        const firstPop = stack.pop();
        stack.push( "(" + stack.pop() + rpn[i] + firstPop + ")" );
    }
}
if (stack.length !== 1) throw Error("Invalid RPN got: " + stack);

for (let i = 0, len = variables.sort().length|0; i < len; i=i+1|0)
    values[i] = +prompt(variables[i] + " = ", Math.random()*10|0);

variables.push( "gcd" );
values.push( function gcd(a, b) {return b ? gcd(b, a % b) : a;} );

variables.push("'use strict';return(" + stack.pop() + ")");
alert("Result: " + Function.apply(0, variables).apply(0, values));

2. 逗号运算符用于将参数分组（我们将使用,来分组最后两个项目，~表示零长度组，仅在此问题中使用）。这种解决方案实际上是传统的RPN，只不过对逗号和零组操作符进行了稍微特殊的处理。每个可变长度的运算符都被视为具有长度为一（零个参数表示为~）。逗号将参数列表由两个项构建而成，每个项可以是普通记号、参数列表或零组操作符。优点包括易于操纵和解析代码、符合RPN的简单性以及保持RPN的独立于记号的特点。缺点是RPN更难调试，因为一个微小的格式不正确的标记可能会破坏整个参数列表，并且无法检测到它是故意的还是意外的，进而导致问题失控。

var rpn = prompt("Please enter RPN string, where each token is " +
  "separated by a space", "x 6 * 126 , 210 , gcd ~ PI %")
  .trim().split(/\s+/);

var stack = [], variables = [], values = [];
for (let i = 0, len = rpn.length|0; i < len; i=i+1|0) {
    if (/^\d*(\.\d*)?$/.test(rpn[i]) && rpn[i] !== "") {
        stack.push( rpn[i] );
    } else if (/^[a-z]$/i.test(rpn[i])) {
        stack.push( rpn[i] );
        if (!~variables.indexOf(rpn[i])) variables.push( rpn[i] );
    } else if (/^[a-z]\w*$/i.test(rpn[i])) {
        if(stack.length<1)throw Error("No operand for " + rpn[i]);
        stack.push( rpn[i] + "(" + stack.pop() + ")" );
    } else if (rpn[i] === ',') {
        if(stack.length<2)throw Error("No operand for " + rpn[i]);
        const p2 = "" + stack.pop(), p1 = "" + stack.pop();
        stack.push( p1 && p2 ? p1 + "," + p2 : p1 || p2 );
    } else if (rpn[i] === '~') {
        stack.push( "" ); // zero-length group
    } else {
        if(stack.length<2)throw Error("No operand for " + rpn[i]);
        const firstPop = stack.pop(); //lacks check if stack empty
        stack.push( "(" + stack.pop() + rpn[i] + firstPop + ")" );
    }
}
if (stack.length !== 1) throw Error("Invalid RPN got: " + stack);

for (let i = 0, len = variables.sort().length|0; i < len; i=i+1|0)
    values[i] = +prompt(variables[i] + " = ", Math.random()*10|0);

variables.push( "gcd", "PI" );
values.push( function gcd(a, b) {return b ? gcd(b, a % b) : a;} );
values.push( function PI() {return Math.PI;} );

variables.push("'use strict';return(" + stack.pop() + ")");
alert("Result: " + Function.apply(0, variables).apply(0, values));

3. 操作符本质上会存储它的长度（为了这个问题，我们将在函数名后附加一个数字）。此解决方案继承了传统逆波兰表达式的所有优点。此外，它使得解析器的读取过程变得简单。此外，由于不会出现意外插入新参数，因此调试更容易。然而，它使得RPN代码的操作和生成更加复杂。更新和生成参数列表很困难，因为这个解决方案偏离了RPN的无关标记性，因此添加一个参数（并改变arity）需要两个动作和一个查找（与传统的一个动作和零查找相对）：(1.) 插入参数，(2.) 查找可变长度运算符的位置，以及 (3.) 更新运算符的长度。

var rpn = prompt("Please enter RPN string, where each token is " +
  "separated by a space", "x 210 gcd2 x 6 * 126 gcd3").trim()
  .split(/\s+/);

var stack = [], variables = [], values = [];
for (let i = 0, len = rpn.length|0, m; i < len; i=i+1|0) {
    if (/^\d*(\.\d*)?$/.test(rpn[i]) && rpn[i] !== "") {
        stack.push( rpn[i] );
    } else if (/^[a-z]$/i.test(rpn[i])) {
        stack.push( rpn[i] );
        if (!~variables.indexOf(rpn[i])) variables.push( rpn[i] );
    } else if (m = rpn[i].match(/^([a-z]+)(\d+)$/i)) {
       if(stack.length<m[2])throw Error("No operand for "+rpn[i]);
        stack.push( m[1] + "(" + stack.splice(-m[2]) + ")" );
    } else {
        if(stack.length<2)throw Error("No operand for " + rpn[i]);
        const firstPop = stack.pop(); //lacks check if stack empty
        stack.push( "(" + stack.pop() + rpn[i] + firstPop + ")" );
    }
}
if (stack.length !== 1) throw Error("Invalid RPN got: " + stack);

for (let i = 0, len = variables.sort().length|0; i < len; i=i+1|0)
    values[i] = +prompt(variables[i] + " = ", Math.random()*10|0);

variables.push( "gcd" );
values.push( function gcd(a, b) {return b ? gcd(b, a % b) : a;} );

variables.push("'use strict';return(" + stack.pop() + ")");
alert("Result: " + Function.apply(0, variables).apply(0, values));

4. 堆栈上的嵌套数组（无演示）。这种解决方案涉及在堆栈上的运算符之前将参数存储在列表中，使得代码的直接执行非常容易。然而，这违反了逆波兰表示法的整个原则和优势，即拥有一个平面列表项。也许，如果列表仅仅是一层深度，那么问题可能不会太大；然而，对于我的用例，我最终会得到深度嵌套的列表。因此，RPN的操作和生成变得非常困难。

此问题的其他可能解决方案是什么？最常用的解决方案是什么？我提出的解决方案存在基本问题吗（请提供反例）？我是否忽略了一些解决方案的利弊？我的解决方案算法能否改进？

- Jack G

---

不确定您所说的“添加参数需要两个操作和一个查找（与传统的一个操作和零查找相比）”是什么意思。对于传统的固定元数函数，您无法添加参数而不删除另一个参数以保留元数。另一种选择是将元数作为运算符的另一个参数。 arg1 arg2 arg3 ... argN N op。这就是forth的pick和roll单词所做的。 - Raymond Chen

我会使用面向对象的编程语言来开发您的计算器。您只需要关心用户输入的名称与内部使用的数组、变量、值或函数之间的连接即可。因此，如果您定义了一个接受n个参数的函数，那么该函数的arity是无关紧要的，因为这些参数在堆栈上并且从那里进行处理。 - Kaplan

在这种情况下，我更喜欢第三个变量。这非常有趣。我很想看到结果的某些方面。如果您需要任何建议，这里 有一种看起来非常实用的逆波兰语言。 - Kaplan

RetroForth、Factor、Joy、RPL（逆波兰Lisp）和其他一些编程语言都支持在堆栈上使用列表。通过这种方式，可变参数函数只需要接受一个参数列表即可。 - AshleyF

它很相似。fn是堆栈上的占位符。然而，它主要用于调用_Java_函数。对于第七个单词fn>cnt，需要将fn移除并将后面参数的计数放入堆栈中。就像Chen所说的那样，在_Forth_中一样。 - Kaplan

Answer 1

我认为你已经涵盖了所有选项：如果你必须能够传递变长参数列表，则你的语言需要具有本地数据结构，允许整个列表成为堆栈上的单个值（即像＃4中的嵌套列表或者类似#2的模拟，其中列表表示为字符串，逗号分隔，并且不能包含其他列表），否则列表元素必须作为堆栈上的单独值。在这种情况下，变量长度必须由哨兵（如＃1中）或长度字段（如＃3中）确定。这似乎是详尽的。

至于优缺点：

• #2 基本上是 #4 的一个版本，但语义很奇怪（, 运算符可以根据上下文要求创建一个两项列表、向列表追加或添加一个项目，或连接两个列表），并且列表不是一级对象，因为列表不能包含列表。
• #1 和 #3 类似于空终止 vs. 长度前缀字符串之间的相似性/差异性。现在通常认为使用长度前缀序列比使用哨兵更好，因为您可以在 O(1) 时间内读取长度，并且如果某个值作为哨兵被特别处理，则它不会出现在序列中（除非有某种转义方式）。

就个人而言，我更喜欢选项 #4，因为如果编程语言没有将列表/数组作为一级对象，那么它对一般用途不是非常有用。关于您所说的 "这违反了RPN的整个原则和优势[...] RPN的操作和生成变得非常困难"，我不太确定您的意思。在RPN这样的连接语言中，完全可以有一种语法来创建列表和嵌套列表。

以我自己的玩具语言fffff为例，代码[1 2 3].通过使用[运算符打开一个新堆栈，将文本值1、2和3推送到这个新堆栈中，然后使用]运算符关闭新堆栈，并将对新堆栈的引用推送到先前的当前堆栈上。这遵守连接属性，因为例如，如果函数three_and_close被定义为执行3 ].，那么代码[1 2 three_and_close具有与原始代码相同的行为；因此，分解代码的部分仍然像标准RPN一样容易。

- kaya3

---

谢谢你的建设性回答。#2和#4之间的区别在于它们采用了不相关的算法。令人惊讶的是，我实际上更倾向于#2，因为它似乎是RPN更连贯的延续。由于RPN的工作方式，永远不需要嵌套列表（嵌套列表总会产生错误。将它们视为varags；您无法嵌套参数列表）。此外，#2的语义非常直观：1 2 , -> [1, 2]；~ 1 , -> [*empty*, 1] -> [1]；1 ~ , -> [1, *empty*] -> [1]。嵌套逗号被展平成一个深度为1的列表。问题 - Jack G

我对 #1、#3 和 #4 的问题在于它们增加了额外的语义，需要进行考虑。这偏离了逆波兰表达式的简单模型。而在 #2 中，逗号的行为就像一个加法运算符。在 #1、#3 和 #4 中，需要额外的逻辑来检测和处理特殊情况，这使得代码更加复杂，因此开发难度更大，调试可能需要更长时间。让我明确一点：我的想法还没有最终确定。我问这个问题是为了防止我没有考虑到 #1、#3 和 #4 的某些方面。我不想使用 #2，然后后来意识到我需要重新开始。 - Jack G

话虽如此，你说的#2和#4是概念上的孪生兄弟是正确的。每个运算符都有一系列与之对应的参数。出于与你喜欢#4相同的原因，#2对我来说看起来很有前途，而我之所以倾向于#2，是因为它似乎更容易实现，因为它在实现上更加内聚，保持了后缀运算符和固定数量操作数的概念。此外，我同意你对#1和#3的比较，并且认为#3比#1更容易实现。 - Jack G

关于“你不能嵌套参数列表”，如果函数接受列表作为其参数，则可以进行嵌套。我不太确定您在第4条中所说的特殊情况是什么——如果您的意思是操作，例如+将必须检查它们的操作数是数字而不是数组，那么像1 2,3 +这样的代码仍然存在这个问题。 - kaya3

感谢您的见解。运算符必须验证其输入类型是一个很好的观点。不能嵌套参数列表的原因是参数列表本身没有任何意义。为了创建数组，您需要一个特殊的运算符，比如MAKE_ARRAY。使用此运算符，执行1 2，3，mean将使用三个参数调用mean，而1 2，3，MAKE_ARRAY mean将使用单个参数调用mean。要嵌套：1 2，MAKE_ARRAY 3 4，MAKE_ARRAY，5 6，MAKE_ARRAY，MAKE_ARRAY flatten等同于flatten([[1,2]，[3,4]，[5,6]])。 - Jack G

Answer 2

我不确定你的计划是否是将您实现的每个函数视为具有其自己独特的参数数量的单独运算符，还是使用一个“函数调用”运算符，在调用函数之前从评估器的操作数栈中提取所需的参数数量。如果是后者，最直接的逆波兰式转换可能是从：“name(expr1,expr2...exprN)”到“name expr1 expr2...exprN N callFunc”。请记住，任何“exprX”都可能是任意复杂的，包括它自己的函数调用。这并不重要；在达到“callFunc”时，您只需要关心操作数栈上面N+2个项目。最棘手的部分是跟踪实际存在的参数数量，并确保该计数在“callFunc”之前进入RPN。这需要某种堆栈来解决嵌套函数，但否则并不太困难。实际上可以使用操作符堆栈（将计数保持“在”“callFunc”运算符下面，即已知偏移量，并在遇到逗号时更新它）。这自然地处理了函数嵌套，但这不是唯一的方法。

"callFunc"在执行时需要一个参数N，这个参数是从操作数栈中取出的参数数量。你可以将这些参数放入列表或数组中，然后将其传递给"name"，一旦你取出并调用它（很可能是间接地使用某种字典）。

为了完整起见，您可能需要在解析时进行错误检查，以确保被调用的函数的参数数量和类型是正确的（您可以将该信息保存在指向评估函数代码的同一字典中）。还要注意逗号出现在不应该出现的地方，就像所有格式不正确的表达式一样。然后，评估器就可以愉快地运行而不必担心任何问题。

- Anton Treuenfels