/* counter automaton that maches ()'s

3 states: 0 is both start and accept state
State 2 is dead state.
In state 0, on seeing (, sets counter to 1 and transition to state 1, else
goto state 2.
State 1 increments counter on seeing (, decrements on seeing ), making
sure that counter doesn't become negative by transitioning back to 0
when counter is 1.

*/
public class matchfsm extends FSM3<String>
{
    protected String instring;
    protected int inx=0;   // indexes instring
    protected int cx = 0; // counter for automaton
    
    public matchfsm(String x)
	{
	    instring = x;
	    states = 3;
	    maxinputs = 2;
	    cx = 0;
	    setHash(); 
	    setStateTable();
	}
    protected String nextInput()
    {
	if (inx<instring.length()) return ""+instring.charAt(inx++);
	else return null;
    }
    protected void setHash()
    {
	Hash = new JHMadaptor<String,Integer>();
	Hash.set("(",0);  Hash.set(")",1);
    }
    // acceptState inherits default
    
    protected void setStateTable()
    {
	M = new action[states][maxinputs];
	M[0][0] = () -> { cx=1; return 1; };
	M[0][1] = () -> 2;  // 2 is dead state
	M[1][0] = () -> { cx++; return 1; };
	M[1][1] = () -> { // seen ')'
	    cx--;
	    if (cx==0) return 0;
	    else return 1; };
	M[2][0] = M[2][1] = () -> 2;
    }//setStateTable

    public static void main(String[] av)
    {
	String x = av[0]; // command-line string
	matchfsm machine = new matchfsm(x);
	machine.trace = true;
	machine.keeprunning = true; // process entire input
	boolean r = machine.run();
	System.out.println(r);
    }
}
// run: java matchfsm "(()))"