双链表中缀到后缀

Question

对于类，我们的任务是使用“抽象中的双链接列表堆栈实现”将中缀表达式转换为后缀。我能够编写一个使用堆栈进行转换的程序，但是双链表的用途是什么？我们将向列表中添加哪些信息节点？

这是作为示例提供给我们的堆栈类。为什么下一个变量是Stack类型？不应该是节点吗？

public class Stack {
  private int data;
  private Stack next;
  private static Stack top;

  //Initialize Stack
  public Stack () {
      top = null;
      next = null;
  }

  public Stack (int d, Stack node) {
      data = d;
      next = node;
  }

  public void push(int item) {
      top = new Stack(item, top);
  }

  public int peek () {
     if(top == null) {
         throw new EmptyStackException();
     } 
     return (top.data);          
  }

  public int pop () {
      int item;

      if(top == null) {
          throw new EmptyStackException();
      } else
          item = top.data;
      top = top.next;
      return (item);
  }

  public boolean empty () {
      return top == null;
  }
}

如果我创建双向链表和节点类，节点对象中有什么数据？

Answer 1

您必须将中缀符号转换为后缀，这意味着将类似于2的东西转换为2。在这种情况下，节点将保留运算符（）或操作数（2），并且它将保留指向列表中上一个和下一个节点的链接。例如，如果我用括号表示一个节点，用箭头表示链接，那么2看起来像：NULL

Answer 2

节点类的数据成员将是：指向上一个和下一个的指针，以及数据。