逆波兰表示法（后缀）中的可变长度运算符

Question

背景：在传统的Reverse Polish Notation中，所有的运算符都必须有固定的长度，这使得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作为代码在最终确定为指定代码语言之前的中介表示。我想尽可能多地保留 RPN 的实用性和易用性，同时仍然表示可变长度运算符。我设计了三个解决方案，并在下面的相当简单的演示中实现了它们。

一个特殊的 ARGUMENTS_BEGIN 前缀运算符（我们将使用 # 来解决这个问题）。该解决方案与传统的 RPN 背道而驰，因为它添加了前缀运算符来表示参数的开始位置。这使得参数列表的大小自动扩展，并有助于调试，因为格式错误的标记替换不会破坏参数列表，从而更容易定位错误。由于需要更多代码来处理嵌套函数调用等情况，这可能会使参数操作变得更加复杂，但我不完全确定会出现什么复杂情况。我猜想我会在解析包含前缀和后缀运算符的语法时遇到障碍。它还使直接评估变得更加困难，因为需要回溯或单独的堆栈来定位参数的开始。

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));

逗号运算符将参数组合在一起（我们将使用 , 对最后两项进行分组，并使用 ~ 表示出于此问题目的的零长度组）。这个解决方案是传统的 RPN，只是对逗号和零组运算符进行了稍微特殊的处理。每个变长运算符都被视为长度为 1（零参数用 ~ 表示）。逗号从两个项目中构建参数列表，每个项目都可以是普通标记、参数列表或零组运算符。优点包括易于操作和解析代码、符合 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));

运算符本质上存储它的长度（出于这个问题的目的，我们将在函数名称上附加一个数字）。该方案继承了传统 RPN 的所有优点。此外，它使解析器的 reading 方面变得简单。此外，调试更容易，因为不会意外插入新参数。但是，它使 RPN 代码的操作和生成更加复杂。更新和生成参数列表很困难，因为此解决方案偏离了 RPN 的标记独立性方面，因此添加一个参数（并更改元数）需要两个动作和一个查找（与传统的一个动作和零查找相反）： (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));

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

单题外推：这个问题还有其他可能的解法吗？这个问题的标准（最常用）解决方案是什么？我的解决方案是否存在根本问题（请提供反例）？我是否忽略了一些 pros/cons 的解决方案？我的解决方案的算法可以改进吗？

Answer 1

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

至于优缺点：

#2 基本上是#4 的一个版本，但具有奇怪的语义（, 运算符可以创建一个 2 项列表，将一个项目追加或添加到列表中，或者连接两个列表，具体取决于在上下文中）并且列表不是 first-class 对象，因为列表不能包含列表。
#1 和#3 类似于空终止字符串与长度前缀字符串之间的 similarities/differences。现在普遍认为长度前缀序列比使用哨兵更好，因为你可以在 O(1) 时间内读出长度，如果某个值被区别对待为哨兵那么它就不会出现在序列中（除非有某种方法可以逃避它）。

就个人而言，我赞成选项 #4，因为如果一种编程语言没有 lists/arrays 作为 first-class 对象，那么它对于一般用途不是很有用。我不确定你所说的 是什么意思“这违反了 RPN 的全部原则和优势 [...] 操作 RPN 和生成 RPN 变得非常困难。” 它是很可能有一种语法可以在 concatenative language 中创建列表和嵌套列表，例如 RPN。

以我自己的玩具语言fffff为例，代码[1 2 3].通过使用[运算符打开一个新堆栈创建一个序列，压入文字值1、2和 3 到这个新堆栈，然后使用 ]. 运算符关闭新堆栈，这也会将对新堆栈的引用推送到先前的当前堆栈上。这遵循串联属性因为如果，例如，函数 three_and_close 被定义为执行 3 ]. 那么代码 [1 2 three_and_close 与原始代码具有相同的行为；所以分解部分代码仍然和标准 RPN 一样简单。

Answer 2

我不确定您的计划是（曾经）将您实现的每个函数都视为具有其独特参数的单独运算符，还是使用一个“函数调用”运算符从调用函数前计算器的操作数堆栈。

如果是后者，最直接的反向波兰转换可能来自：

名称（表达式 1、表达式 2...表达式 N）

对此：

名称 expr1 expr2...exprN N callFunc

请记住，任何“exprX”都可能是任意复杂的，包括它自己的函数调用。没关系;到达“callFunc”时，您只需担心操作数堆栈中最顶层的 N+2 项。最棘手的一点是跟踪实际存在的参数数量，并确保计数在“callFunc”之前进入 RPN。

这需要某种堆栈来解释嵌套函数，但除此之外并不太难。实际上可以使用运算符堆栈（将计数“保持在”“callFunc”运算符下，一个已知的偏移量，并在每次遇到逗号时更新它。这自然会处理函数嵌套，但这不是唯一的方法） .

在执行过程中，“callFunc”接受一个参数 N，即从操作数堆栈中取出的参数数量。这些你可以放入一个列表或数组中，一旦你把它拉下来并调用它就可以传递给“name”（很可能间接使用某种字典）。

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

逆波兰表示法（后缀）中的可变长度运算符

Variable-Length Operators In Reverse Polish Notation (Postfix)

algorithm

variadic-functions

postfix-notation

variable-length

rpn