Need some help..

Discussion of Common Lisp
Johny22
Posts: 11
Joined: Thu Oct 29, 2009 5:36 am

Need some help..

Post by Johny22 » Thu Oct 29, 2009 5:38 am

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.

nuntius
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: Need some help..

Post by nuntius » Thu Oct 29, 2009 11:07 am

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.

Johny22
Posts: 11
Joined: Thu Oct 29, 2009 5:36 am

Re: Need some help..

Post by Johny22 » Thu Oct 29, 2009 11:29 am

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 ?

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Need some help..

Post by ramarren » Thu Oct 29, 2009 12:16 pm

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.

Johny22
Posts: 11
Joined: Thu Oct 29, 2009 5:36 am

Re: Need some help..

Post by Johny22 » Thu Oct 29, 2009 3:16 pm

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!

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Need some help..

Post by ramarren » Thu Oct 29, 2009 3:31 pm

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.

Johny22
Posts: 11
Joined: Thu Oct 29, 2009 5:36 am

Re: Need some help..

Post by Johny22 » Thu Oct 29, 2009 4:38 pm

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.

Paul Donnelly
Posts: 148
Joined: Wed Jul 30, 2008 11:26 pm

Re: Need some help..

Post by Paul Donnelly » Thu Oct 29, 2009 9:28 pm

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.

Johny22
Posts: 11
Joined: Thu Oct 29, 2009 5:36 am

Re: Need some help..

Post by Johny22 » Fri Oct 30, 2009 2:32 am

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 !

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Need some help..

Post by ramarren » Fri Oct 30, 2009 3:34 am

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?

Post Reply