Need some help..

How can i transform a tree like (node1 (childrens) node2 (childrens) ...) into (root (child1 (childrens_child1 (..)) child2 (childrens_child2 (...)))). Example: (1 (2 3) 2 (4) 3 4) => (1 (2 (4) 3)) And i also need to do it backwards (1 (2 (4) 3)) => (1 (2 3) 2 (4) 3 4)

Another problem i bumped into is to create a macro that gets an argument N and an expresion, and i need to return the Nth element of the list(only variable). Example: (var 2 '(+ (- a b) c)) => b

I started to think that it is a way so i can remove the math operators that to get nth from list, but i can't manage to get to the sublist(in the example (- a b)), it works for a simple one like (+ 1 2) it will return 1 2 and than i can do nth, but i need to do it for more complex expresions.

FYI, these sound like homework. As a general rule, its best to tell people when you're asking about homework problems.

I don't fully understand the first question; so I can't help there.

For the second, there are two basic approaches. You could flatten the lists first, or you could use recursion to walk the tree. The recursive solution will basically look like your function for a flat list; but for sublists, it calls itself with the sublist and the remaining count. It returns (values item 0) if found or (values nil number-checked) if not.

I didn't said it isn't a homework(sorry anyway, it is my first time here on this forum), i tried to do it for the last 2 days and nothing good. this is the reason why i asked here, maybe someone who knows more can help.
For the first problem I need to convert from one tree form into another.
For the first example i wrote it wrong: (1 (2 3) 2 (4) 3 4) it is actualy (1 (2 3) 2 (4)).
The first form is like this: 1 it is the root with the childrens 2 and 3, 2 actualy is a subtree and has one leaf 4(left leaf).

For the second it is something like preorder traversal( Root Left Right): it first gets 1 as root with 2 as children(subtree), that also has a children 4(that is a leaf), and 3 that is a leaf.

For the second one i found a way to represent it, but for the first one is the problem.

here another example how the tree is reprezented: (b (c d) a (b e) e (f)) => a - root , b e - children of a , c d - children of b , f - children of e
(a (b e) b (c d) e (f))) => a - root , b e - children of a , c d - children of b , f - children of e

(a ((b (c d)) (e (f)) => a - root , b - children of a -- c d children of b , e - children of b -- f children of e

For the answer for the second problem:
What do you mean by flatten the list ?
I tried to remove the math operators, and than to get nth n from the new list, but i couldn't write it in lisp. there is a special function so i can use to chech if the list elements are alpha-numerical and than use the delete-if function ?

Johny22 wrote:For the first problem I need to convert from one tree form into another.

It is still not clear what the two forms exactly are. Try to express them more formally, rather than throwing random examples. It should make the solution clearer. This is rather silly anyway, usually in Common Lisp one would represent a tree as a structure anyway. Messing with cons-cell representations is usually counterproductive.

Are you sure you are using Common Lisp, anyway? Despite mostly cosmetic similarities languages from Lisp family are quite different from one another.

Johny22 wrote:For the answer for the second problem:
What do you mean by flatten the list ?
I tried to remove the math operators, and than to get nth n from the new list, but i couldn't write it in lisp. there is a special function so i can use to chech if the list elements are alpha-numerical and than use the delete-if function ?

Why would someone give a homework assignment in Lisp without teaching any Lisp first? Flattening a list is most common list manipulation example ever it seems. Just do a depth-first traversal collecting the elements. The latter question seems irrelevant, as the operators are, presumably, always at the front of the list so they can be stripped without examining them during traversal.

That is only a simple example, for more complex ones the math operator can be somewhere in the middle, anyway I will read more about flattening and try that one.

For the first one, i don't really know hoe else to explain .
I will try this way:
a this is my tree example
/ \
b e
/ \
c d
In LISP i can represent it in two ways(two are asked) one is (a (b e) b (c d) e (f))) an the second one is (a (b (c d) e)). I need to convert from one representation to another one.
I would have to make a function that gets as an argument one of the representations and the result would be the other representation.

The general formula for both of them is:(node1(child11 child12) node2(child21 child22) node3(child31 child32) ...)
and (root (child1(child11 child12) child2(child21 child22)...).

I hope this explains a little more what i need to do!

Johny22 wrote:In LISP i can represent it in two ways(two are asked) one is (a (b e) b (c d) e (f))) an the second one is (a (b (c d) e)). I need to convert from one representation to another one.

What I guess you are saying is that the first form is a tree represented as a partially folded edge graph, and the second form is structural. It would help if your examples were congruent. There is no 'f' in your second example. If you cannot specify the transformation algorithm in a non-fuzzy way at all, then it is not the fault of the language that you cannot program it. And I am not convinced that the second form is even sane, are you sure it is not of form `(head children-or-subtree*)`? In which case the tree would look like (a (b c d) (e f)).

Johny22 wrote:That is only a simple example, for more complex ones the math operator can be somewhere in the middle, anyway I will read more about flattening and try that one.

In expression with prefix syntax the operator cannot be in the middle by definition.

i mean like this (+ (* 2 3) (/ 8 2)), or more complex ones, i wonder if there is a function that test for alpha-numeric elements, for example : if not alpha-numeric remove from list => ((2 3)(8 2)) and then to aply the nth element to return the variable that i look, but for this i will look into myself, i only want to know if there is a function that can test for that alhpa-numeric.

and for the tree, that is only an example(and yes i forgot an f - it should be (a (b (c d) e (f)) ), only one form is an argument and than i need to aply a function to transform it into the other form; and another function to the the oposite.
Those forms can be shorter or longer, depends on what the user enters as an argument.

Let's take the example below,
(node1(child11 child12) node2(child21 child22) node3(child31 child32) ...) -> node1 =a ; child11 = b and child12 = e ; node2 = b ; child21 = c and child22 =d ; node3 = e ; child31 = f and child32 = nil ( if we create an expanded binary tree, if not we don;t have that nil)
(root (child1(child11 child12) child2(child21 child22)...) -> root = a ; child1 = b ; child11 = c and child12 = d ; child2 = e ; child21 = f and child22 = nil (also if we create an expanded binary tree, if not we don;t have that nil)
Another way i understood it is that the first one is somewhat like an level-order traversal and the second one like an preorder traversal.
Observation !! (a (b e) b (c d) e (f))) <=> (b (c d) a (b e) e (f))
I can't think of another way to explain this problem, hope this helps a little.

Johny22 wrote:i mean like this (+ (* 2 3) (/ 8 2)), or more complex ones, i wonder if there is a function that test for alpha-numeric elements, for example : if not alpha-numeric remove from list => ((2 3)(8 2)) and then to aply the nth element to return the variable that i look, but for this i will look into myself, i only want to know if there is a function that can test for that alhpa-numeric.

I don't think this is what you really want. Yes, there is a function to tell you whether a character is alphanumeric or not (called ALPHANUMERICP (the P stands for “predicate”), surprise, surprise), but it only works on characters. But that example up there doesn't include any characters. It's got some symbols, +, *, and /, and it's got some numbers, 2, 3, 8, and 2. Probably what you want is either NUMBERP or SYMBOLP.

the argument can also be like (+ (* a b)(/ c a )), i think i will combine that alphanumericp and numberp functions to remove any other symbol and than use nth on the resulting list.

Thanks for the tip about the alphanumericp function !

Johny22 wrote:the argument can also be like (+ (* a b)(/ c a )), i think i will combine that alphanumericp and numberp functions to remove any other symbol and than use nth on the resulting list.

This still has all operators in head position, and you don't have to check them! Just strip the heads when flattening the list. Do you understand the concept of nested lists?

I do not know the concept of nested list, can you please explain a little ?

Johny22 wrote:I do not know the concept of nested list, can you please explain a little ?

I hope this is mostly a language barrier, because this is rather fundamental to programming.

A list is an ordered set of objects. Lists are nested when one of the object contained by a list is a list itself. Lisp uses a syntax for lists where they are delimited by parentheses and contained objects are separated by whitespace.

So in the

(+ (* a b)(/ c a ))

example there is a list of three objects, two of which are lists themselves, each of which contain three objects. In the prefix syntax for expressions, the first element of a list, sometimes called `head`, is an operator, and the remaining elements are its arguments. Hence, there are are no operators 'in the middle' of the expression, because they all are in front of a list, even if their particular list is inside, or nested, in another list.

This example shows one way of traversing nested lists, dispatching on what you find, and collecting results.

(defun recur-sum (list)
  "sum the numbers in a tree of lists, return (values sum count)"
  (let ((sum 0)
        (count 0))
    (dolist (x list)
      (cond
        ((symbolp x)
         (error "Can't add symbol ~A" x))
        ((null x)) ;; optimization: ignore empty lists
        ((listp x)
         (multiple-value-bind (subsum subcount)
             (recur-sum x)
           (incf sum subsum)
           (incf count subcount)))
        ((numberp x)
         (incf sum x)
         (incf count 1))
        (t
         (error "Can't add ~A ~A" (type-of x) x))))
    (values sum count)))

;; test case
(trace recur-sum)
(recur-sum '(1 2 (3 4) 5))
(untrace recur-sum)

If recur-sum took an "&optional (count 0)" parameter and recurred using "(recur-sum x count)", then the recursive calls would know how many items were before them.

For the second problem with nth var, how can i use delete-if ?

i tried writing some code but it didn't work , can someone help me with this code and correct it if necesary ?

(defun nth_var (el l)
	(if (null l) '()
		(and (delete-if-not #' (lambda (x) alpha-char-p (x)) (l))(delete-if-not #' (lambda (x) alphanumericp (x)) (l))
				(nth el (l))
		)
	)
)

I tried to modify the list so the math operators will be removed and than to get the nth element from the list.

I also need it to be a macro, how can i do that ?

PS: I tried that flattening method but nothing, so i tried this method but this one also doesn't work.

for the problem where i need to get the nth variable from an expresion, I found how to flatten the list , here is the code i used (i used the loop function ):

(defun flatten (list)
	(loop for i in list if (listp i) append (flatten i) else collect i)
	
)

Now i want to use the alpha-char-p and alphanumericp functions with the remove-if function so i can remove all math operators from my flattened list and than to use the nth function so i can get the nth element from my final list. Can someone pls help me with this ?

PS: It needs to be a macro.

I've wrote these 3 functions :

(defun flatten (list)
"Flatten the list"
	(if (null list) '()
		(loop for i in list if (listp i) append (flatten i) else collect i)
	)
)
(defun rem_mo (list)
"Remove the math operators"
	(if (null list) '()
		(delete-if-not #'alphanumericp list)
	)
)
(defun nth_var (el list)
"Get the nth variable from the list"
	(if (null list) '()
		(nth el list)
	)
)

Can someone show me how to make them work together ? I want to flatten the list gotten as an argument, tham to remove the math operators and finaly get the nth element that also was given as argument. All this needs to be a macro. Anyone knows how to do this ?

Hint: you want the nth_var of the rem_mo of the flattened list.

Why do you need this to be a macro? Other than defmacro instead of defun, macros use the same syntax as functions; they just get their arguments unevaluated and can't easily be used at runtime. So (fun '(1 2 3)) becomes (mac (1 2 3)).

I made them work :d, thanks to all that tried to help me