CODEWITHSUNDEEP
javarecursionlinked-list
Snowman
Snowman

Reputation: 32081

Help with backward recursion and LinkedList in Java

/**
     * Converts linked list into a sentence (a single string representation).
     * Each word pair is separated by a space. A period (".") is appended after
     * the last word. The last link represents the first word in the sentence
     * (and vice versa). The partialResult is the partial string constructed
     * from earlier links. This partialResult is initially an empty string. 
     */
    public String getReversedSentence(String partialResult) {
        if (next==null) {
            partialResult+=this.word;
            return partialResult + ".";
        }
        else{
            partialResult=next.getReversedSentence(partialResult) + this.word;
            return partialResult;
            }
    }

Everything is working fine, except for the period (and the spaces, but Im not worrying about that yet). I cant get the period to be placed properly.

Here's the test it's failing:

public void testGetReversedSentence() {
        LinkedList tail = new LinkedList("not",null);
        LinkedList middle = new LinkedList("too",tail);
        LinkedList head = new LinkedList("tricky",middle);
        assertEquals("not.",tail.getReversedSentence(""));
        assertEquals("not too tricky.",head.getReversedSentence(""));

It comes up with not.too tricky instead of not too tricky.

Edit: Contrusctor

public LinkedList(String word, LinkedList next) {
        this.word = word;
        this.next = next;
    }

Any hints?

Upvotes: 0

Views: 946

Answers (4)

Sanya Zahid
Sanya Zahid

Reputation: 468

//--------------------------linklist class------------------------------------------------

import java.util.Stack;

public class Linklist {
    Stack <Character> a = new Stack <Character>();
    Node front; 
    Node back;
    Node Temp;

    public void insert (char d){
        Node newNode = new Node (d);
    if (front == null){
        front = newNode;
        back = newNode;
    }


    else {
        Temp = front;
        while (Temp != null){

            back= Temp;
        Temp = Temp.next ;
        }

        back.next = newNode;
    }


    }





    public void display(){
        Node T=front;
        System.out.print(T.data);
        T=T.next;
        while(T!=front)
        {
            System.out.print(T.data);
            T=T.next;
            if (T == null ){
                break;
            }
        }
    }


    public void reverse(){
    Linklist bb = new Linklist ();


        Node temp = front;
        while(temp != null ){
            if (temp.data != '_'){
 a.push(temp.data);

            }


            else{
        //char x =  
while (!a.isEmpty()){
    char pop = a.pop();
bb.insert(pop);


            }
bb.insert('_');
            }
            temp = temp.next;
        }// while end

        bb.display();

    }


}
//-------------------------------------------------------------------------------------


//------------------ test class
public class Test {

    /**
     * @param args
     */
    public static void main(String[] args) {

        queueLinklist a = new queueLinklist ();
a.insert('m');
a.insert('y');
a.insert('_');
a.insert('n');
a.insert('a');
a.insert('m');
a.insert('e');
a.insert('_');
a.insert('i');
a.insert('s');
a.insert('_');
a.insert('s');
a.insert('a');
a.insert('m');
a.insert('_');

a.display();
System.out.println(" ");
    a.reverse();
    a.reverse();
    }

}
// ---------- node class

public class Node {
char data;
Node next;

Node (){
    data= (Character) null ;
    next = null;
}

Node (char d){
    data = d;
    next = null;
}
}

Upvotes: -1

irrelephant
irrelephant

Reputation: 4111

Well... there's no need to use 2 methods, (important) --> because this method has String partialResult as a parameter. (You can if you want to and if helper methods are allowed in the solution, but it's unnecessary.) In other words, try to find some way to incorporate the current word with partialResult. Another hint: there is a solution that is 3 lines long (and properly formatted).

Upvotes: 1

rsp
rsp

Reputation: 23383

What is going wrong is that the "." is appended to the word that is deepest in recursion, which is the first word in the reversed sequence.

You want to find a way to add the "." to the end of the reversed sequence, maybe by splitting your method in 2 methods where the one that calls the other knows something about the result.

Upvotes: 1

The Archetypal Paul
The Archetypal Paul

Reputation: 41777

 public String getReversedSentence(String partialResult) {
        if (next==null) {
            partialResult+=this.word;
            return partialResult + ".";
        }
        else{
            partialResult=next.getReversedSentence(partialResult) + this.word; // <---
            return partialResult;
            }
    }

The problem is the line marked <---. The recursive call will eventuallyt return with the . appended (since it will recurse until it gets to the end of hte list, then add a ., return that and then you append this.word.

Since this is homework, I won't give a solution.

Upvotes: 1

Related Questions