/*
  Interpreter of the Turing Machine.
  An initial CURRENT_STATE of the Turing Machine is coded by "start",
  final CURRENT_STATE - by "stop".
  The shift of the head to the right is designated through "right",
  to the left - through "left" .
*/

class brackets {

    public static int ltape=10;  /* Length of a tape  */
    public static int nunits=0; 
    public static int head;
    public static String state;

    /* Indexes in array of the instructions,   */
    public static final int CURRENT_STATE  = 0;
    public static final int CURRENT_SYMBOL = 1;
    public static final int NEXT_SYMBOL    = 2;
    public static final int NEXT_STATE     = 3;
    public static final int MOVE           = 4;

    public static String[] tape =
        { "*", "(", "(", ")", "(", ")", ")", "*", " ", " " };

    public static final String[][] instruction = {
        { "start", "*",  "*",  "qb",   "right" },
        { "qb",    "L",  "L",  "qb",   "right" },
        { "qb",    "R",  "R",  "qb",   "right" },
        { "qb",    "(",  "(",  "qb",   "right" },
        { "qb",    "*",  " ",  "qd",   "left"  },
        { "qb",    ")",  "R",  "qc",   "left"  },
        { "qc",    "L",  "L",  "qc",   "left"  },
        { "qc",    "R",  "R",  "qc",   "left"  },
        { "qc",    "(",  "L",  "qb",   "right" },
        { "qc",    "*",  "0",  "stop", "right" },
        { "qd",    "L",  "(",  "qd",   "left"  },
        { "qd",    "R",  ")",  "qd",   "left"  },
        { "qd",    "(",  "0",  "stop", "right" },
        { "qd",    "*",  "1",  "stop", "right" }
    };

    public static void main (String args[]) {
        head = 0;
    //    for (int i = 0; i < ltape; i++)      /* filling of blank  */
    //        tape[i] = " ";
    //    for (int i = head; i < head+nunits; i++)
    //        tape[i] = "1";
        long start = System.currentTimeMillis();

        test();

        long end = System.currentTimeMillis();
        System.out.println("Total time = "+ (end-start)*0.001);
        System.out.println("Final Tape : " );
        for (int i = 0; i < ltape; i++)
            System.out.print(tape[i]) ;
    }


    public static void test() {
        state = "start";
        while (state != "stop") {
            for (int i=0; i<instruction.length; i++) {
                if (state == instruction[i][CURRENT_STATE]
                && tape[head] == instruction[i][CURRENT_SYMBOL]) {
                    state=instruction[i][NEXT_STATE];
                    tape[head]=instruction[i][NEXT_SYMBOL];
                    if(instruction[i][MOVE]=="right") head++;
                    if(instruction[i][MOVE]=="left" ) head--;
                }
            }
        }
    }
}