Re: NON-trivial regular expression problem (could not find on google)

[Larry Clapp <larry@theclapp.org>]

In article <7606630f.0301181219.60384da2@posting.google.com>, Instant Democracy wrote:
> A frequent problem involves simplifying a pathname. The string
> format we can expect to encounter is covered by the following
> three examples:
> 
> "dir.name/../dir/../file"
> "dir/../d2/../file.ext"
> "d1/d2/../../file.ext"
> 
> The "" are part of the string, and not just string delimiters.
> These strings are inside regular text on the line. The paths
> are never absolute so that you will not encounter
> "/d1/file.ext".
> 
> The task is to eliminate patterns such as 
>     DIRNAME/../
> from the path because they are redundant.
> 
> For lines which do not have ../.. in them, this is trivial, for
> example by regexp in sed, emacs etc.
> 
> The real problem is constructing a regular expression for the
> DIRNAME before the /..
> 
> This DIRNAME can be described as a string that contains neither
> / not double-dot but anything else. Perhaps I am overlooking
> something else about DIRNAME.

Yes.  "../.." doesn't matter.  Find any pathname component
followed by ".." and remove both.  Continue until no more ".."'s
exist in the string.  In Perl:

    $_ = "d1/d2/../../file.ext";
    do {} while (s#[^/]+/\.\./##g);
    print $_;

In Common Lisp:

    (defun split (s delim)
      (let ((start-at 0))
	(nconc 
	  (loop for c across s 
		and i upto (length s)
		nconc (when (eql c delim)
			(prog1 
			  (list (subseq s start-at i))
			  (setf start-at (1+ i)))))
	  (list (subseq s start-at)))))

    (defun join (list delim)
      (let ((res (car list))
	    (delim (make-string 1 :initial-element delim)))
	(dolist (el (cdr list))
	  (setf res (concatenate 'string res delim el)))
	res))

    (defun normalize-path (path)
      (let ((names (split path #\/))
	    (stack nil))
	(dolist (name names)
	  (cond ((string= name "..") (pop stack))
		(t (push name stack))))
	(join (reverse stack) #\/)))

Testing:

    (let ((paths '("dir.name/../dir/../file"
		   "dir/../d2/../file.ext"
		   "d1/d2/../../file.ext"
		   "1234/../2345/../3546/3456/3456/../../asdf/asdf/file")))
      (dolist (path paths)
	(print (normalize-path path))))
    -> "file" 
    -> "file.ext" 
    -> "file.ext" 
    -> "3546/asdf/asdf/file" 
    => NIL

> [...]
> sigfile - you are welcome to use it or modify without changing
> its thrust.

Please drop this 3k sigfile.  Thank you.

-- Larry



-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----==  Over 80,000 Newsgroups - 16 Different Servers! =-----