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?

Answer 1

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!