Java中的Lisp表达式评估器(仅使用一个堆栈) [英] Lisp expression evaluator in Java (using only one stack)

问题描述

我正在尝试使用Java实现一个简单的Lisp表达式评估器.实际上，有关该主题的信息很多，但似乎它们都使用两个单独的堆栈来得出结果.我想知道是否有可能仅使用一个堆栈来实现这样的程序，以及一些伪代码看起来像什么.

I'm trying to implement a simple Lisp expression evaluator using Java. There's actually a wealth of information on the subject, but it appears they all use two separate stacks to arrive at the result. I'm wondering if it is possible to implement such a program using only one stack and what some pseudo code might look like for that.

谢谢.

有关我正在谈论的内容的更多信息，请参见

For more info on what I'm talking about refer to

• http://www.chegg.com/homework-help/questions-and-answers/outline-given-import-import-javautil-public-class-simplelispexpressionevaluator-current-input-lis-q2332957
• http://stdioe.blogspot.ca/2012/01/lets-implement-simple-lisp-interpreter.html

• http://www.chegg.com/homework-help/questions-and-answers/outline-given-import-javautil-public-class-simplelispexpressionevaluator-current-input-lis-q2332957
• http://stdioe.blogspot.ca/2012/01/lets-implement-simple-lisp-interpreter.html

推荐答案

您链接的两个解释器都做出了非常重要的假设:+，-，*等都是二进制函数，也就是说，它们始终采用正好有两个参数.在实际的Lisp中，您可以说(+ 1 2 3 4 5)求和一堆数字.但是，如果您愿意接受简化的假设，即每个操作员的熟悉程度都是已知的，那么您绝对可以只用一个堆栈就可以做到.关键:颠倒堆叠.

Both of the interpreters you linked to make a very important assumption: that +, -, *, etc. are all binary functions, that is, they always take exactly two arguments. In real Lisp, you can say (+ 1 2 3 4 5) to sum a bunch of numbers. But, if you're willing to accept the simplifying assumption that the arity of each operator is known, then you can definitely do this with only one stack. The key: turn the stack upside down.

您链接的口译员具有如下堆栈:

The interpreters you linked to have stacks like this:

底部-> ( + ( - 2 1 ) 4 )<-顶部(我们从此处推动并弹出)

bottom -> ( + ( - 2 1 ) 4 ) <- top (we push and pop from here)

但是，您也可以从右侧向后读表达式，并像这样构建堆栈:

But, you could also read in your expression backwards, from the right, and build the stack like this:

顶部-> ( + ( - 2 1 ) 4 )<-底部

top -> ( + ( - 2 1 ) 4 ) <- bottom

然后，您基本上获得了RPN，即反向抛光符号. RPN在堆栈上的表现非常好.

Then you essentially get RPN, reverse polish notation. RPN plays really nicely with stacks.

算法如下:

• 如果您看到括号，请忽略它
• 如果看到操作数，则将其压入堆栈
• 如果看到运算符，请调用它.操作员弹出所需的任意多个值，然后将其结果压入堆栈

例如，( + ( - 2 1 ) 4 ).该算法的工作方式如下:

Take, for example, ( + ( - 2 1 ) 4 ). Here's how the algorithm would operate:

堆栈: 空 阅读: ) 操作:括号被忽略. 左: ( + ( - 2 1 ) 4

Stack: empty Reading: ) Action: parenthesis ignored. Left: ( + ( - 2 1 ) 4

堆栈: 空 阅读: 4 操作:操作数被压入堆栈. 左: ( + ( - 2 1 )

Stack: empty Reading: 4 Action: operand pushed to stack. Left: ( + ( - 2 1 )

堆栈: 4 阅读: ) 操作:括号被忽略. 左: ( + ( - 2 1

Stack: 4 Reading: ) Action: parenthesis ignored. Left: ( + ( - 2 1

堆栈: 4 读数: 1 操作:操作数被压入堆栈. 左: ( + ( - 2

Stack: 4 Reading: 1 Action: operand pushed to stack. Left: ( + ( - 2

堆栈: 1 4 阅读: 2 操作:操作数被压入堆栈. 左: ( + ( -

Stack: 1 4 Reading: 2 Action: operand pushed to stack. Left: ( + ( -

堆栈: 2 1 4 阅读: - 操作:运算符.它将弹出堆栈2和1，然后将2-1=1推入堆栈. 左: ( + (

Stack: 2 1 4 Reading: -Action: operator invoked. It will pop 2 and 1 off the stack, and then push 2-1=1 onto it. Left: ( + (

堆栈: 1 4 阅读: ( 操作:括号被忽略. 左: ( +

Stack: 1 4 Reading: ( Action: parenthesis ignored. Left: ( +

堆栈: 1 4 阅读: + 操作:运算符.它将弹出堆栈1和4，然后将1+4=5压入堆栈. 左: (

Stack: 1 4 Reading: + Action: operator invoked. It will pop 1 and 4 off the stack, and then push 1+4=5 onto it. Left: (

堆栈: 5 阅读: ( 操作:括号被忽略. 左: 什么都没有

Stack: 5 Reading: ( Action: parenthesis ignored. Left: nothing

完成！结果是5，如预期的那样.

Done! Result is 5, as expected.

PS.只要您输入的表达式格式正确，它就可以完美地工作，但是它可以采用格式错误的表达式并赋予它们无意义的值.例如(+ - + 1 2 3 4)被解释为(+ (- (+ 1 2) 3) 4).如果您想防止此行为，只需将括号放在堆栈中即可.当需要调用一个运算符时，弹出参数，再加上一个额外的标记. 确保令牌是封闭的，否则会引发错误.获得结果后，将其推入堆栈. 确保您读入的下一个令牌是开放式的，然后将其丢弃.

PS about ignoring parentheses. This will work perfectly so long as the expression you enter is well-formed, but it can take non-well-formed expressions and given them nonsensical values. e.g. (+ - + 1 2 3 4) is interpreted as (+ (- (+ 1 2) 3) 4). If you would like to prevent this behaviour, simply push close parentheses onto the stack. When it comes time to invoke an operator, pop off the arguments, plus one extra token. Make sure that token is a close-paren, otherwise throw an error. Once you have a result, push it onto the stack. Make sure that the next token you read in is an open-paren, and then discard it.

如果像在实际Lisps中那样，函数的参数本身可以是函数，那么这一切将变得更加复杂.这样，您就没有RPN所依赖的运算符/操作数之间的方便区分，您需要更加注意括号作为分组元素.我不确定您是否可以仅用一个堆栈来完成一个具有可变对数和作为操作数的功能的成熟Lisp表达式评估器.

PPS this all becomes a lot more complicated if, as in real Lisps, the arguments to functions can themselves be functions. Then you don't have the handy distinction between operator/operand that RPN relies on, and you need to pay more attention to the parentheses as grouping elements. I'm not sure if you could do a full-blown Lisp expression evaluator, with variable-arity and functions-as-operands, with only one stack.

这篇关于Java中的Lisp表达式评估器(仅使用一个堆栈)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！