背景:在传统的逆波兰表示法中,所有运算符都必须具有固定长度,这使得 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 的有用性和易用性,同时仍然表示可变长度运算符。我设计了三个解决方案,并在下面相当简单的演示中实现了它们。
#
来解决这个问题)。该解决方案与传统 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));
(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));
单题外推:这个问题还有其他可能的解决方案吗?这个问题的标准(最常用)解决方案是什么?我的解决方案是否存在根本性问题(请提供反例)?我是否忽略了我的解决方案的一些优点/缺点?我的解决方案的算法可以改进吗?
最佳答案
我认为您已经涵盖了这些选项:如果您必须能够传递可变长度的参数列表,那么您的语言需要具有 native 数据结构,允许整个列表成为堆栈上的单个值(即#4 中的嵌套列表,或 #2 中的它们的模拟,其中列表表示为字符串,以逗号分隔,并且不能包含其他列表),否则列表元素必须是堆栈上的单独值。在这种情况下,可变长度必须由标记(如#1)或长度字段(如#3)确定。这似乎很详尽。
至于优缺点:
,
运算符可以创建一个 2 项列表,将一个项附加或前置到列表中,或者连接两个列表,具体取决于上下文)并且列表是不是一流的对象,因为列表不能包含列表。 就我个人而言,我喜欢选项 #4,因为如果编程语言没有列表/数组作为一流对象,那么它对于一般用途不是很有用。我不确定您所说的“这违反了 RPN 的全部规则和优势 [...] 操纵 RPN 并且 RPN 的生成变得非常困难”的确切含义。很有可能在 concatenative language 中有用于创建列表和嵌套列表的语法。像RPN。
带上我自己的玩具语言 fffff例如,代码
[1 2 3].
通过使用 [
打开一个新堆栈来创建一个序列运算符,将文字值 1、2 和 3 推送到这个新堆栈,然后使用 ].
关闭新堆栈运算符,它还将对新堆栈的引用推送到先前的当前堆栈上。这服从连接属性,因为例如,如果函数 three_and_close
被定义为做 3 ].
然后是代码 [1 2 three_and_close
具有与原始代码相同的行为;所以分解出部分代码仍然像在标准 RPN 中一样容易。
关于algorithm - 逆波兰表示法中的变长运算符(后缀),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65400013/