武汉邀请赛 Key Logger 双向链表

Key Logger

Time Limit: 3000ms

Case Time Limit: 3000ms

Memory Limit: 65536KB

64-bit integer IO format: %lld Java class name: Main

Submit Status PID: 29373

Font Size:

Decode the message from the given key logger. The logger consists:

’-’ representing backspace: the character directly before the cursor position is deleted, if there is any.
’<’ (and ’>’) representing the left (right) arrow: the cursor is moved 1 character to the left (right), if possible.
alphanumeric characters, which are part of the password, unless deleted later. Here assumes ‘insert mode’: if the cursor is not at the end of the line, and you type an alphanumeric character, then all characters after the cursor move one position to the right.

Input

The first line contains a single integer T, indicating the number of test cases.
Each test case contains a string L, with 1 <= Length(L) <= 1000000.

Output

For each test case, output the case number first, then the decoded message string in a line.

Sample Input

2
<<o<IL>>>veU-
HelloAcmer

Sample Output

Case 1: ILove
Case 2: HelloAcmer

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cstdlib>
  5 using namespace std;
  6 
  7 
  8 struct node
  9 {
 10     char c;
 11     struct node *next;
 12     struct node *before;
 13 };
 14 char a[1000005];
 15 
 16 int main()
 17 {
 18     int T,i,len,s;
 19     while(scanf("%d",&T)>0)
 20     {
 21 
 22         for(s=1;s<=T;s++)
 23         {
 24             scanf("%s",a+1);
 25             len=strlen(a+1);
 26             node *head=(struct node*)malloc(sizeof(node));
 27             head->before=NULL;
 28             head->next=NULL;
 29             node *p1,*p2,*p3,*p4;
 30             p1=p2=p3=p4=head;
 31             for(i=1;i<=len;i++)
 32             {
 33                 if(a[i]!='-' && a[i]!='>' && a[i]!='<')
 34                 {
 35                     p1=(struct node*)malloc(sizeof(node));
 36                     p1->c=a[i];
 37 
 38                     if(p2->next!=NULL)
 39                     {
 40                       p3=p2->next;
 41 
 42                       p2->next=p1;
 43                       p1->before=p2;
 44                       p1->next=p3;
 45                       p3->before=p1;
 46                       p2=p1;
 47                     }
 48                     else
 49                     {
 50                         p1->next=NULL;
 51                         p1->before=p2;
 52                         p2->next=p1;
 53                         p2=p1;
 54                     }
 55                 }
 56                 else if(a[i]=='-')
 57                 {
 58                     if(p2==head) ;
 59                     else if(p2->next==NULL&&p2!=head)
 60                     {
 61                         p4=p2;
 62                         p1=p2->before;
 63                         p2=p1;
 64                         p2->next=NULL;
 65                         free(p4);
 66                     }
 67                     else
 68                     {
 69                         p4=p2;
 70                         p1=p2->before;
 71                         p3=p2->next;
 72                         p1->next=p3;
 73                         p3->before=p1;
 74                         p2=p1;
 75                         free(p4);
 76                     }
 77                 }
 78                 else if(a[i]=='<')
 79                 {
 80                     if(p2->before==NULL);
 81                     else p2=p2->before;
 82                 }
 83                 else if(a[i]=='>')
 84                 {
 85                     if(p2->next==NULL);
 86                     else p2=p2->next;
 87                 }
 88             }
 89             printf("Case %d: ",s);
 90             p1=head;
 91             while(p1->next!=NULL)
 92             {
 93                 p4=p1;
 94                 printf("%c",p1->next->c);
 95                 p1=p1->next;
 96                 free(p4);
 97             }
 98             printf("
");
 99         }
100     }
101     return 0;
102 }