algorithm - 逆波兰表示法中的变长运算符(后缀)

Question

背景:在传统的逆波兰表示法中，所有运算符都必须具有固定长度，这使得 RPN 可以很容易地被代码评估和操作，因为每个标记、表达式和子表达式都是“自包含”的，以至于人们可以盲目地替换 y在 x 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 的 token 独立性。缺点包括 RPN 更难调试，因为一个微小的畸形 token 可能会扰乱整个参数列表并且滚雪球失控，无法检测它是故意的还是偶然的。

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的所有优点。此外，它使解析器的读取方面变得简单。此外，调试更容易，因为不会意外插入新参数。但是，它使 RPN 代码的操作和生成更加复杂。更新和生成参数列表很困难，因为该解决方案偏离了 RPN 的 token 独立性方面，因此添加参数(并更改参数)需要两个 Action 和一个查找(与传统的一个 Action 和零查找相反):
(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 的生成变得非常困难。

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

Answer 1

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

#2 基本上是 #4 的一个版本，但具有奇怪的语义(, 运算符可以创建一个 2 项列表，将一个项附加或前置到列表中，或者连接两个列表，具体取决于上下文)并且列表是不是一流的对象，因为列表不能包含列表。

#1 和 #3 类似于以空字符结尾的字符串与以长度为前缀的字符串之间的相似性/差异性。现在人们普遍认为，带长度前缀的序列比使用哨兵更好，因为您可以在 O(1) 时间内读取长度，并且如果某些值被不同地视为哨兵，那么它就不会出现在序列中(除非有某种方法可以逃避它)。

就我个人而言，我喜欢选项 #4，因为如果编程语言没有列表/数组作为一流对象，那么它对于一般用途不是很有用。我不确定您所说的“这违反了 RPN 的全部规则和优势 [...] 操纵 RPN 并且 RPN 的生成变得非常困难”的确切含义。很有可能在 concatenative language 中有用于创建列表和嵌套列表的语法。像RPN。
带上我自己的玩具语言 fffff例如，代码 [1 2 3].通过使用 [ 打开一个新堆栈来创建一个序列运算符，将文字值 1、2 和 3 推送到这个新堆栈，然后使用 ]. 关闭新堆栈运算符，它还将对新堆栈的引用推送到先前的当前堆栈上。这服从连接属性，因为例如，如果函数 three_and_close被定义为做 3 ].然后是代码 [1 2 three_and_close具有与原始代码相同的行为；所以分解出​​部分代码仍然像在标准 RPN 中一样容易。