LISP - Splitting string with delimiter also included in new list

I have a list of elements following

("(aviyon" "213" "flyingman" "no))") as list

What i want is that I want to split this list containing strings using parentheses as splitter but also want to include these parentheses in a new list without breaking the order

My desired output of new list(or same list modified)

("(" "aviyon" "213" "flyingman" "no" ")" ")")

I am coming from imperative languages and this would be 15 minute job in Java or C++. But here i'm stuck what to do. I know i have to

1- Get a element from list in a loop

I think this is done with (nth 1 '(listname) )

2- separate without removing delimiter put in to a new list

I found functions such as SPLIT-SEQUENCE but i can't do without removing it and without breaking original order.

Any help would be appreciated.

Solution

Let's have another answer, without external libraries. Like you already did, we can split in the problem into smaller parts:

define a function which builds a list of tokens from a string, all-tokens
apply this function on all strings in your input list, and concatenate the result:
```
(mapcan #'all-tokens strings)
```

The first part, taking a state and building a list from it, looks like an unfold operation (anamorphism).

Fold (catamorphism), called reduce in Lisp, builds a value from a list of values and a function (and optionally an initial value). The dual operation, unfold, takes a value (the state), a function, and generate a list of values. In the case of unfold, the step function accepts a state and returns new state along with the resulting list.

Here, let's define a state as 3 values: a string, a starting position in the string, and a stack of tokens parsed so far. Our step function next-token returns the next state.

 ;; definition follows below
 (declare (ftype function next-token))

The main function which gets all tokens from a string just computes a fixpoint:

(defun all-tokens (string)
  (do (;; initial start value is 0
       (start 0)
       ;; initial token stack is nil
       (tokens))

      ;; loop until start is nil, then return the reverse of tokens
      ((not start) (nreverse tokens))

    ;; advance state
    (multiple-value-setq (string start tokens)
      (next-token string start tokens))))

We need an auxiliary function:

(defun parenthesisp (c)
  (find c "()"))

The step function is defined as follows:

(defun next-token (string start token-stack)
  (let ((search (position-if #'parenthesisp string :start start)))
    (typecase search
      (number
       ;; token from start to parenthesis
       (when (> search start)
         (push (subseq string start search) token-stack))
       ;; parenthesis
       (push (subseq string search (1+ search)) token-stack)
       ;; next state
       (values string (1+ search) token-stack))
      (null
       ;; token from start to end of string
       (when (< start (1- (length string)))
         (push (subseq string start) token-stack))
       ;; next-state
       (values string nil token-stack)))))

You can try with a single string:

(next-token "(aviyon" 0 nil)
"(aviyon"
1
("(")

If you take the resulting state values and reuse them, you have:

(next-token "(aviyon" 1 '("("))
"(aviyon"
NIL
("aviyon" "(")

And here, the second return value is NIL, which ends the generation process. Finally, you can do:

(mapcan #'all-tokens '("(aviyon" "213" "flyingman" "no))"))

Which gives:

("(" "aviyon" "213" "flyingman" "no" ")" ")")

The above code is not fully generic in the sense that all-tokens knows too much about next-token: you could rewrite it to take any kind of state. You could also handle sequences of strings using the same mechanism, by keeping more information in your state variable. Also, in a real lexer you would not want to reverse the whole list of tokens, you would use a queue to feed a parser.