Poj Solution 1057

http://poj.org/problem?id=1057

/* @author:����acmilan_fan@yahoo.cn */
import java.io.*;
public class Main {
  public static void main(String[] args) throws Exception{
//System.setIn(new FileInputStream(new File("E:\in.txt")));
//System.setOut(new PrintStream(new File("E:\out.txt")));
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  String s;
  Node root=new Node("ROOT",null);
  Node curr=root;
  Node t,n;
  int count=1;
  tag:
  while(true){
    switch((s=br.readLine()).charAt(0)){
       case 'f':
         t=new Node(s,curr);
      if(curr.fleftmost==null)
          curr.fleftmost=t;
      else{
         if(t.compareTo(curr.fleftmost)< 0){
             t.frightsib=curr.fleftmost;
             curr.fleftmost=t;
         }else{
        n=curr.fleftmost;
        while(n.frightsib!=null&&t.compareTo(n.frightsib)>0){
           n=n.frightsib;
        }
        t.frightsib=n.frightsib;
        n.frightsib=t;
         }
     }
     break;
      case 'd':
      t=new Node(s,curr);
      if(curr.dleftmost==null)
        curr.dleftmost=curr.drightmost=t;
      else{
        curr.drightmost.drightsib=t;
        curr.drightmost=t;
       }
       curr=curr.drightmost;
       break;
    case ']':
       curr=curr.parent;
       break;
    case '*':
        print(root,count++);
        curr=root=new Node("ROOT",null);
        break;
    case '#':
        break tag;
     }
   }
  }

 static void print(Node root,int count) {
   System.out.println("DATA SET "+count+":");
   print0(root,0);
   System.out.println();
 }

static void print0(Node root, int d) {
   for(int i=0;i< d;i++){
    System.out.print("|     ");
    }
    System.out.println(root.content);
    Node t=root.dleftmost;
    while(t!=null){
        print0(t,d+1);
        t=t.drightsib;
    }
    t=root.fleftmost;
    while(t!=null){
        print0(t,d);
        t=t.frightsib;
    }
  }
}
class Node implements Comparable< Node>{
    String content;
    Node parent;
    Node fleftmost;
    Node frightsib;
    Node dleftmost;
    Node drightsib;
    Node drightmost;
    Node(String c,Node n){
        content=c;
        parent=n;
    }
    @Override
    public int compareTo(Node o) {
        return this.content.compareTo(o.content);
    }
}

											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *