Lisp expression evaluator in Java (using only one

Question

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.

Thanks.

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

Answer 1

hope it can help you lisp style calculator with no stack

Answer 2

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 (we push and pop from here)

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

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

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

The algorithm is like this:

• If you see a parenthesis, ignore it
• If you see an operand, push it onto the stack
• If you see an operator, invoke it. The operator pops off as many values as it needs, then pushes its result onto the stack

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

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

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

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

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

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

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: ( + (

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

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: (

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

Done! Result is 5, as expected.

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.

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.