Java: создан класс Stack для выражений Infix и Postfix

Question

Для наборов кода у меня есть класс SinglyLinkedList, а также класс MyStack и тестер, но вывод не отображается просто []. Я хотел бы понять, как правильно реализовать стек для выполнения выражений infix и postfix,Я думаю, что это в основном связано с классом MyStack ... Я думаю, что я мог неправильно реализовать некоторые методы.

import java.util.Iterator;
import java.util.NoSuchElementException;

public class SinglyLinkedList<T> implements Iterable<T>{
    //head and tail pf the list
    private Node<T> head;
    private Node<T> tail;
    private int size;

    /*this will set the head and tail to null*/
    public SinglyLinkedList(){
        head = null;
        tail = null;
    }

    /*returns size*/
    public int size(){
        int size = 0;
        Node<T> p = head;
        while (p != null) {
            size++;
            p = p.getNext();
        }
    return size;
    }//end of size()

    /*this will ass a new node to the end of the list*/
    public void add(T element){
        Node<T> node = new Node<T>(element);
        if(head == null){
            head = node;
            tail = node;
        }
        else{
            tail.setNext(node);
            tail = node;
        }
        size++;
    }//end of add()

    /*returns true if list is empty*/
    public boolean isEmpty(){
        if(head == null){
            return true;
        }
        else{
            return false;
        }
    }//end of isEmpty()

    /*deletes node with given data if it exists*/
    public boolean delete(T element){
        if(head == null){
            return false; //empty list
        }
        if (head.getData().equals(element)) {
            head = head.getNext();
            if (head == null) {
                tail = null;
            }
             return true;
        }
        Node<T> node = head;
        Node<T> next = head.getNext();
        while (next != null) {
            if (next.getData().equals(element)) {
                node.setNext(next.getNext());
                if (node.getNext() == null) {
                    tail = node;
                }
            return true; //sucess
            }
            //moving to next pair of nodes
            node = node.getNext();
            next = next.getNext();
        }
        return false; //failed
    }//end of delete()

    /*toString method*/
    @Override 
    public String toString(){
        String data = "[";
        Node<T> p = head;
        while (p != null) {
            data += p.data;
            p = p.next;
            if (p != null) {
            data += ", ";
            }
        }
        data += "]";
        return data;
    }//end of toString

    public void clear(){
        head = null;
        tail = null;
        size = 0;
    }//end of clear()

/*
**inner Node class
*/
public class Node<T> {
    T data;
    Node<T> next;

    /* constructor taking value for the data*/
    public Node(T data) {
    this.data = data;
    next = null;
    }//end of constructor

    public Node<T> getNext() {
         return next;
    }

    public void setNext(Node<T> next) {
        this.next = next;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {

         this.data = data;

    }
}//end of inner Node class


/*
**inner SinglyLinkedListIterator class
*/
public class SinglyLinkedListIterator implements Iterator<T> {
    private Node<T> node;//current node
    private T current; 

    /*constructor*/
    public SinglyLinkedListIterator(){
        node = head;
        current = null;
    }//end of condtructor

    @Override
    public boolean hasNext(){                                        
        return node != null;
    }

    @Override
    public T next(){
        current = node.getData();
        node = node.getNext();
        return current;
    }

    @Override
    public void remove() {
        delete(current);
    }
}

    @Override
    public Iterator<T> iterator() {
        return new SinglyLinkedListIterator();
    }

}//end of SinglyLinkedList class

    import java.util.LinkedList;
    import java.util.*;

    public class MyStack<T> extends SinglyLinkedList{

        private LinkedList<T> stack;

        /*constructor*/
        public MyStack(){
            stack = new LinkedList<T>();
        }//end of constructor

        public void push(T element){
            this.stack.add(element);
        }

        public T pop(){
            if(stack.size() == 0){
                return null;
            }

            return stack.removeLast();
        }

        public boolean isEmpty(){
            if(stack == null){
                return true;
            }
            else{
                return false;
            }
        }
    } //end of MyStack


    public class Startup{
    public static void main(String[] args) {
        MyStack<String> stack = new MyStack<String>();

        stack.push("a+b*(c-d)");
        System.out.println(stack.toString());


    }//end of main
}//end of startup cla

ss

Answer 1

Давайте оставим в стороне тот факт, что в вашем классе MyStack<> вы используете двусвязный список Java на секунду.

1) Вы создали односвязный списокэто идет голова к хвосту .Затем вы реализовали add(), который работает на конце tail . Это самая неэффективная реализация , которую вы можете сделать для стека.

Стек по своей природе - LIFO (последний вошел, первый вышел).Т.е. если вы сделаете add(1); add(2); add(3);, тогда pop(), вы должны получить 3 - последний добавленный вами элемент.В вашей реализации, чтобы добраться до 3, нужно пройти через 1 и 2. Теперь представьте, если у вас есть миллион предметов, и вам нужно выскочить два из них.Чтобы пройти к хвосту, нужно дважды пройти миллион элементов.

Лучшая реализация для стека, подкрепленного от головы к хвосту связанным списком, будет add и pop от головы .Когда вы делаете pop, у вас уже есть последний элемент, добавленный к голове, и у вас уже есть ссылка на следующий элемент, который будет новой головой.

2) После всего этого вы приступили ксоздайте класс MyStack<>, который использовал private LinkedList<T> stack; для его поддержки. Это реализация двусвязного списка Java .Это должно прекрасно работать для стека, но не дает возможности выполнить ваши первые 50 строк кода по созданию реализации связанного списка самостоятельно.

3) Когда вы делаете stack.push(), вы вызываете push()метод в вашем классе MyStack, который выталкивает его в список с двойной связью , упомянутый в 2) выше.

Затем вы пытаетесь распечатать stack.toString().В этом случае MyStack не имеет метода toString, поэтому он относится к своему родительскому классу SinglyLinkedList.Но так как вы даже не коснулись односвязного списка в своем коде, он возвращается пустым, и вы ничего не получаете.

---

В заключение, ваша оценка, что он как-то связан с вашим MyStack реализация находится на 100% месте.Вы смешиваете и сопоставляете класс LinkedList Java со своим собственным классом SinglyLinkedList;добавление значений к одному, а затем чтение другого.