Java Stos Porównanie

Question

Zastanawiam się, jak to osiągnąć:

1. Porównaj dwa stos obiektów
2. Czy to rekurencyjnie
3. po metody, które wykonuje to jest kompletna, stosy pozostają jak oni na początek (tj. ta sama kolejność, te same elementy).

Tylko push, pop i isEmpty metody Stack jest dostępna.

Szukam bardziej teoretycznej pomocy niż kodowanie pomocy, ale każdy wgląd byłby doceniony.

Answer 1

w pseudo-kodu, można zrobić coś takiego:

boolean compareStacks(a, b) { 
    if (a.isEmpty() != b.isEmpty()) return false; // check if one is empty 
    if (a.isEmpty() && b.isEmpty()) return true; // check if both are empty 
    element_a = a.pop(); // grab elements and compare them 
    element_b = b.pop(); 
    if (((element_a==null) && (element_b!=null)) || !element_a.equals(element_b)) { 
    a.push(element_a); // if they are not equal, restore them and return false 
    b.push(element_b); 
    return false; 
    } 
    result = compareStacks(a, b); // compare shortened stacks recursively 
    a.push(element_a); // restore elements 
    b.push(element_b); 
    return result; // return result from recursive call 
} 

Answer 2

Dwa stosy są identyczne, jeśli ich elementy najwyższego poziomu są identyczne, a pozostałe stosy są identyczne (a mianowicie warunek rekursywny).

Teraz pomyśl, co zrobić przed powrotem z metody, aby opuścić stosy w taki sam sposób, w jaki zostały podane w czasie wywołania.

--- EDIT ---

Roboczy kod Java (pochodzący z Markus A. rozwiązania, ale z ciekawym wykorzystaniem "wreszcie", a z rodzajowych):

static <T> boolean compareStacks(Stack<T> a, Stack<T> b) { 
    if (a.isEmpty() != b.isEmpty()) return false; 
    if (a.isEmpty() && b.isEmpty()) return true; 
    T element_a = a.pop(); 
    T element_b = b.pop(); 
    try { 
     if (((element_a==null) && (element_b!=null)) || (!element_a.equals(element_b))) 
      return false; 
     return compareStacks(a, b); 
    } finally { // restore elements 
     a.push(element_a); 
     b.push(element_b); 
    } 
} 

Answer 3

z rekursji zawsze pomaga myśleć o tym jak o 2 części, a „Setup” i cyklicznej zabawy ction. Twoja konfiguracja stworzy odpowiednią sytuację (utwórz dwa stosy, przekaż je itd.), A następnie wywoła metodę rekursywną, a po wykonaniu metody rekurencyjnej zgłoś wyniki.

W twoim przypadku prawdopodobnie chcesz tego podpisu dla „rekurencyjnego” metoda:

public boolean compareStacks(Stack one, Stack two) 

Jeśli ta metoda wyskakuje & porównuje górne elementy lawety stosu, może to return false prawo to (mówiąc don porównywać). Jeśli tak, masz teraz dwa stosy, każdy krótszy niż poprzednio. Już wiesz, jak porównać te dwa stosy, tak (właśnie napisałeś metodę, aby to zrobić!).

na końcu możesz "wepchnąć" swój jeden element z powrotem na każdy stos, aby przywrócić poprzedni stan przed powrotem.

Będzie trochę trudności w przywróceniu stosu w przypadku, gdy nie są one porównywane, i zapewnienie, że jeśli wywołanie funkcji compareStack nie powiedzie się, to poprawnie przekazuje to do poprzedniego stanu, nawet jeśli "obecny" compareStack się uda, ale to są szczegóły implementacji - pomyślałem, że wspomnę o nich, więc nie przeoczysz ich.

Istnieje urocze rozwiązanie z Try/finally (bez haczyków, powrót z próby i wepchnięcie z powrotem na stos w końcu), dzięki czemu kod byłby całkiem zgrabny, ale bez niego jest dość łatwy.