双向链接列表中缀到PostFix

For class, we are tasked with the assignment of converting an infix expression to postfix using a "doubly linked list stack implementation in abstraction". I was able to write a program that uses the Stack in order to make the conversion, but what is the purpose of the doubly linked list? What node of information are we adding to the list?

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

This is the stack class that was provided to us as an example. Why is the variable next type Stack? Shouldn't it be Node?

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

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;
  }
}

If I create a doubly linked list and node class, what data is in the node object?

如果我创建一个双向链表和节点类,那么节点对象中有哪些数据?

2 个解决方案

#1

Data member of Node class would be: pointers to previous and next, along with the data.

Node类的数据成员将是:指向上一个和下一个的指针以及数据。

#2

You have to convert an infix notation to postfix, which means converting something like 2 + 2 to 2 2 + In this case, Node will hold either the operator (+) or operand (2) and it will hold links to the previous and next nodes in the list. For example, if I represent a node using parenthesis and links using arrows, 2 + 2 looks like: NULL <- (2) <-> (+) <-> (2) -> NULL

你必须将中缀符号转换为后缀,这意味着将2 + 2转换为2 2 +在这种情况下,Node将保持运算符(+)或操作数(2),它将保存前一个和下一个的链接列表中的节点。例如,如果我使用括号表示节点并使用箭头表示链接,则2 + 2看起来像:NULL < - (2)< - >(+)< - >(2) - > NULL