反向波兰符号中的可变长度运算符(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作为代码的中间表示。我希望尽可能多地保留RPN的有用性和易用性，同时仍然表示可变长度运算符。我设计了三个解决方案，并在下面相当简单的演示中实现了它们。

1. 一个特殊的ARUMENTS_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));

2. 逗号运算符将参数分组在一起(为了这个问题的目的，我们将使用,对最后两项进行分组，使用~表示零长度组)。此解决方案是传统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));

3. 运算符本质上存储其长度(出于这个问题的目的，我们将在函数名上附加一个数字)。该解决方案继承了传统RPN的所有优点。此外，它使解析器的读取方面变得简单。此外，调试更容易，因为没有意外插入新参数。然而，它使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的全部原则和优势，即拥有一个扁平的项目列表。也许，如果名单只有一个，就不会有太大的问题；然而，对于我的用例，我最终会得到深度嵌套的列表。因此，RPN的操作和RPN的生成变得非常困难

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

Answer 1

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

关于优点和缺点：

• #2基本上是#4的一个版本，但具有奇怪的语义(,运算符可以创建一个2项列表，将一项附加或前置到列表中，或者根据上下文连接两个列表)，并且列表不是一级对象，因为列表不能包含列表
• #1和#3类似于空终止字符串与长度前缀字符串之间的相似性/差异。现在人们普遍认为，带长度前缀的序列比使用sentinel要好，因为你可以在O(1)时间内读取长度，如果某个值被不同地视为sentinel，那么它就不会出现在序列中(除非有某种方法可以转义它)

就我个人而言，我喜欢选项#4，因为如果一种编程语言没有列表/数组作为一级对象，那么它对一般用途就不是很有用。我不知道你所说的"em"到底是什么意思；这违反了RPN[…]操作RPN的整个原则和优点，并且RPN的生成变得非常困难"在RPN这样的串联语言中创建列表和嵌套列表的语法是很可能的。

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

Answer 2

我不确定你的计划是将你实现的每个函数都视为一个独立的运算符，有自己独特的arity，还是有一个"；函数调用"；运算符，在调用函数之前从计算器的操作数堆栈中提取所需数量的参数。

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

名称(expr1，expr2…exprN)

到此：

name expr1 expr2…exprN callFunc

记住，任何"；exprX"；可能是任意复杂的，包括它自己的函数调用。这并不重要；到"；callFunc"；到达时，您只需要担心操作数堆栈上最顶端的N+2项。最棘手的一点是跟踪实际存在的参数数量，并确保该计数在"0"之前进入RPN；callFunc"；。

这需要某种堆栈来解释嵌套函数，但在其他方面并不太困难。实际上，使用运算符堆栈是可能的(将计数"保留在"callFunc"运算符下，一个已知的偏移量，并在每次遇到逗号时更新它。这自然会处理函数嵌套，但不是唯一的方法)。

"执行中"；callFunc"；取一个参数N，即从操作数堆栈中取出的参数数。这些可以放入列表或数组中，然后传递给"；name"；一旦你把它取下来并调用它(很可能是间接使用某种字典)。

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