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

[Larry Clapp]

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! =-----