Solving Infix Arithmatic in LISP

Question

(defun solve (L)
    (cond
    ((null L) nil)
    (t(eval (list (car (cdr L)) (car L) (car (cdr (cdr L))))))))

The code I have is a simple evaluate program that works fine as long as the input is something like '(5 + 4). However I want to be able to solve other inputs such as '(5 +( 3 - 1)) and '(6 + 5) - (4 /2 ). My problem obviously being how to handle the parentheses. I tried comparing the literal value of '( as in ((equal (car L) '( ) (solve(cdr L))) but that only throws all of my close parentheses out of whack. Is there a way to check if an atom is a parentheses?

This looks to me like you need recursion. It would also be easier if you don't have to use explicit chains of `car`s and `cdr`s. There are compositions of these such as `cadr`, which has a nice friendly alternate name, `second`. I don't have time to put together a full answer right now, but maybe these hints will be ehough. (If it's homework, that should be enough, and you should work through the rest. Your professor wouldn't have assigned this without expecting you to have learned recursion, so review it if necessary. If it's not homework, ignore these last comments.) — Mars, Sep 30 '13 at 05:05
I'll add one more tip. Don't bother dealing with parentheses explicitly unless you're trying to write a real parser. Let Lisp deal with the parentheses. Just deal with what's inside a given pair of parentheses. — Mars, Sep 30 '13 at 05:12
@Mars +1 for comments regarding parenthesis. Shrp91, Mars's point makes a lot of sense; the value of `'(5 + (3 - 1))` is a list whose first element is (the number) `5`, second element is (the symbol) `+`, and whose third element is a list whose first, second, and third elements are `3`, (the symbol) `-`, and `1`. There's no need to worry about parentheses at all. But this raises the question, what were you actually calling `solve` with when you said `'(6 + 5) - (4 /2 )`? That's not a single expression, and spacing is important: `(4 /2)` is a list with elements `4` and (the _symbol_) `/2`. — Joshua Taylor, Sep 30 '13 at 12:10
"... the value of '(5 + (3 - 1)) is a list whose first element is (the number) 5, second element is (the symbol) +, and whose third element is a list whose first, second, and third elements are 3, (the symbol) -, and 1." This was all I needed. For some reason I was thinking a sublists first element would be a parentheses. Completely changed how I tackled the code and got it shortly after. — Shrp91, Oct 02 '13 at 18:13

score 5 · Accepted Answer · answered Sep 30 '13 at 05:59

I'm hoping that if this is a homework question, you look at Mars's comments instead of my answer. You're not going to do well if you just take my code. On the other hand, if you actually read through everything and really understand it, that's something.

Like Mars said, we need to recurse. It's simple enough; if we have a number, return it.

(defun solve (expression)
  (if (atom expression)
      expression
    'havent-dealt-with-this-yet))
[22]> (solve '3)
3

If we've got a list, take the second thing, assume it's the operator, and eval it the way you did in our sample:

(defun solve (expression)
  (if (atom expression)
      expression
    (eval (list (second expression)
                (first expression)
                (third expression)))))
[25]> (solve 3)
3
[26]> (solve '(3 + 4))
7

Cool. But here we're no further than your original code. What happens if we have a nested expression?

[27]> (solve '(3 + (2 * 2)))

*** - EVAL: 2 is not a function name; try using a symbol instead

Well, this isn't working. We can't just assume that either of (first expression) or(third expression)` are values; they may be expressions themselves. But we need to figure out the value of the expression. Let's assume we have a way to take an expression and find its value. Then our code can be:

(defun solve (expression)
  (if (atom expression)
      expression
    (eval (list (second expression)
                (find-expression-value (first expression))
                (find-expression-value (third expression))))))

Wait! solve is a function that takes an expression and finds its value!

(defun solve (expression)
  (if (atom expression)
      expression
    (eval (list (second expression)
                (solve (first expression))
                (solve (third expression))))))
[43]> (solve 3)
3
[44]> (solve '(3 + 2))
5
[45]> (solve '((3 + 1) * (6 / 2)))
12

ta-da!

Now we only need to add longer expressions with operator precedence and associativity rules :-) — 6502, Sep 30 '13 at 09:18
Or just return the list, changing this code from an interpreter to a compiler to Lisp :-) — 6502, Oct 01 '13 at 10:23
Kudos to zck for illustrating ways of thinking and working rather than just the answer. — Mars, Oct 02 '13 at 05:03
This is essentially what I came up with. My problem was thinking a sublists first element would be a parentheses. — Shrp91, Oct 02 '13 at 18:14
One of Lisp's greatest advantages is the REPL. Use it to build up things if you're not sure about them, and to test things out. Certainly it's fine to ask for help, but checking your code in the REPL (and, for that matter, building code incrementally and testing it) can avoid the need for asking someone else. — zck, Oct 02 '13 at 18:21

Solving Infix Arithmatic in LISP

1 Answers1

Linked