我正在尝试使用 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-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:

bottom -> ( + ( - 2 1 ) 4 ) <- top (我们从这里推送和弹出)

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 )

Stack: 4 Reading: ) Action: 括号被忽略.左: ( + ( - 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: ( +

Stack: 1 4 Reading: + Action: 操作符被调用.它将从堆栈中弹出 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.