Mar 2011
1 / 2
Mar 2011
May 2011
ajukraine
Mar '11

I'm getting Wrong Answer with solution of "Transform the Expression". I've tested it for many cases and always got expected answer. Why it WA in SPOJ? Maybe something wrong with Lisp?

(defun operatorp (char)
  (not (eql (level char) 0)))
(defun level (operator)
  (case operator 
    (#\+ 1) 
    (#\- 2) 
    (#\* 3) 
    (#\/ 4) 
    (#\^ 5)
    (otherwise 0)))
(defun lesser (first second)
  (< (level first) (level second)))
(defmacro pop-to-answer-while (stack answer test)
  `(loop
      with head = (car ,stack)
      while
	,test
      do
	(setq ,answer (cons head ,answer))
	(setq ,stack (cdr ,stack))
	(setq head (car ,stack))))
(defun solve (line)
  (let ((op-stack)
	(answer))
    (dolist (char (concatenate 'list line))
      (cond
	((eq char #\()
	 (setq op-stack (cons char op-stack)))
	((eq char #\))
	 (pop-to-answer-while 
	  op-stack 
	  answer 
	  (not (eq head #\()))
	 (setq op-stack (cdr op-stack)))
    ((operatorp char)
 (pop-to-answer-while 
  op-stack 
  answer 
  (and (not (null op-stack)) (lesser char head)))
 (setq op-stack (cons char op-stack)))

(t
 (setq answer (cons char answer)))))

(setq op-stack (remove #\( op-stack))
(unless (null op-stack)
  (setq answer (append (reverse op-stack) answer)))
     
(setq answer (reverse answer))
(concatenate 'string answer)))
(defun spoj()
  (progn 
     (let ((N (read))
	   (line))
       (dotimes (i N)
	 (setq line (read-line))
	 (format t "~s~%" (solve line))))))
(spoj)

  • created

    Mar '11

  • last reply

    May '11
  • 1

    reply

  • 465

    views

  • 1

    user

2 months later
ajukraine
May '11

Yes! I made it works!

The mistake was so lame. It was about formatting the text to stream.

I used the incorrect directive in format function. So it printed the solution string surrounded with quotes, and i always got WA. For example,

instead of

Then (with "~s" directive):

(format t "~s~%" (solve line))

Now (with "~a" directive):

(format t "~a~%" (solve line))