背景: 在传统的逆波兰式中,所有操作符必须具有固定长度,这使得RPN易于通过代码进行评估和操作,因为每个标记、表达式和子表达式都是“自包含”的,这样可以盲目地将
问题:如何修改或调整逆波兰表达式(RPN)以适应可变长度的“操作符”(比如函数)?
研究和解决方案:我使用逆波兰表达式作为代码在最终转换为指定编程语言之前的中介表示形式。我希望尽可能保留 RPN 的实用性和易用性,同时仍能表示可变长度的操作符。因此我提出了三个解决方案并在下面的简单演示程序中进行了实现。
4. 堆栈上的嵌套数组(无演示)。这种解决方案涉及在堆栈上的运算符之前将参数存储在列表中,使得代码的直接执行非常容易。然而,这违反了逆波兰表示法的整个原则和优势,即拥有一个平面列表项。也许,如果列表仅仅是一层深度,那么问题可能不会太大;然而,对于我的用例,我最终会得到深度嵌套的列表。因此,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));
- 一个特殊的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));
- 逗号运算符用于将参数分组(我们将使用
,
来分组最后两个项目,~
表示零长度组,仅在此问题中使用)。这种解决方案实际上是传统的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));
- 操作符本质上会存储它的长度(为了这个问题,我们将在函数名后附加一个数字)。此解决方案继承了传统逆波兰表达式的所有优点。此外,它使得解析器的读取过程变得简单。此外,由于不会出现意外插入新参数,因此调试更容易。然而,它使得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));
此问题的其他可能解决方案是什么?最常用的解决方案是什么?我提出的解决方案存在基本问题吗(请提供反例)?我是否忽略了一些解决方案的利弊?我的解决方案算法能否改进?
arg1 arg2 arg3 ... argN N op
。这就是forth的pick
和roll
单词所做的。 - Raymond Chenfn
是堆栈上的占位符。然而,它主要用于调用_Java_函数。对于第七个单词fn>cnt
,需要将fn
移除并将后面参数的计数放入堆栈中。就像Chen所说的那样,在_Forth_中一样。 - Kaplan