/* File: CExamples/Lists/turing.c */
/* simulate a Turing Machine that scans
   the input tape stdin and writes to
   the auxiliary tape to reverse the input
   (testing to be a palindrom)
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct turing_cell {
   char cell;
   struct turing_cell *next;
   struct turing_cell *prev; 
};

int main(void)
{struct turing_cell *tape = NULL;
 char c;
 
 tape = (struct turing_cell*)malloc(sizeof(struct turing_cell));
 tape->cell = '^';
 tape->prev = NULL;
 tape->next = NULL;

 while ( (c=getchar()) != '$' )
    {tape->next = (struct turing_cell*)malloc(sizeof(struct turing_cell));
     tape->next->prev = tape;
     tape = tape->next;
     tape->cell = c;
     tape->next = NULL;
    }/* end while != '$' */

  while (tape->cell != '^')
    {putchar(tape->cell);
     tape = tape->prev;
    }/* end while != '^' */
  putchar('$');
  putchar('\n');
}