public class PDA {



    // The representation of final states, start state, current

    // state and total number of states are the same as in the

    // implementation of DFSA.

    

	private boolean[] 	finalStates;

	private int         startState;

    private int		    currentState;

    private int 		totalStates;

    

    // For a PDA, we still use a two-dimensional Linkelist array to hold

	// the transitions from each state, but we need a more complex

	// data structure, PDATransition, to store the information.

	

	private PDATransitionLinkedList[][] 	delta;

	

	// We also need to implement a stack data structure to hold

	// the PDA stack.	

    

    private PDAStack    myStack;



	public PDA (int n, int start) {

        totalStates = n;

		finalStates = new boolean[totalStates];

        //initialize the  the PDATransitionLinkedList array
		delta = new PDATransitionLinkedList[totalStates][totalStates];
		for(int i = 0; i<totalStates; i++)
		    for(int j = 0; j<totalStates; j++)
	            delta[i][j] = new PDATransitionLinkedList();//initialize the
linkelist
		

		startState = start;

		myStack = new PDAStack();

    }



    private boolean isFinal () {

        

        // The PDA is in an accept state only if:

        //   1) the current state is a final state, and

        //   2) the stack is empty.

        

        if (finalStates[currentState] && myStack.isEmpty()) {

            return true;

        } else {

            return false;

        }

    }



    public void addTransition (int fromState, int toState, String letter,
String stackSymbol, String pushSymbol) {

        // Used to be just the letter char, now must include letter, stack
symbol, push symbol.
        // add a new node to linkedlist
	    delta[fromState][toState].addNode(letter,stackSymbol,pushSymbol);

    }

    

    public void addFinalState (int q) {

        finalStates[q] = true;

    }



    public boolean isAccepted (String s) {

        Node thisTransition;

	    currentState = startState;

	    String currentLetter;

	    readingSymbols:

	        for (int i = 0; i < s.length(); i++) {	       

	            currentLetter = s.substring(i,i+1);
				
				System.out.println(" current state: "+currentState);

		        System.out.println(" current symbol: "+currentLetter);

		        System.out.println(" current stack: "+myStack);

		        for (int j = 0; j < totalStates; j++) {		         

		            thisTransition = delta[currentState][j].head;
		            // Match possible transitions with a separate method.
			        while(thisTransition != null){ // until to the last element in
the linkedlist
			            if(possibleTransition(myStack,thisTransition,currentLetter))
{

			            System.out.println("Transition("+currentState+","+j+")
matched: "+thisTransition);

			            if (thisTransition.stackChar != "e") myStack.pop();			       
    

			            if (thisTransition.pushChar != "e") 
			                
			            myStack.push(thisTransition.pushChar);

				        currentState = j;

				        continue readingSymbols;
				        }
				        //if can not find the possible transition, 
				        //go to the next node in the PDAtransition linkedlist
                        else thisTransition = thisTransition.getNext();

                       
                    }
                }

                System.out.println(" d("+currentState+","+s.charAt(i)+")
failed");

                return false;

            }

        System.out.println(" ending state: "+currentState);

        System.out.println(" ending stack: "+myStack);

        return isFinal();

    }

    

    public boolean possibleTransition (PDAStack stack, Node transition,
String letter) {

        String sChar = transition.stackChar;

        String wChar = transition.wordChar;
        
        if (wChar.equals(letter)) {

            if (sChar.equals("e")) { 

                return true;

            } else if (sChar.equals(stack.peek())) {

                return true;

            } else {
                return false;

            }

        } else {

            return false;

        }

           

    }

    

    public static void main (String args[]) {

        if(args.length==0)
		    System.out.println("Input is empty. Rejected!");
 

        // PDA from lecture notes: L(A) = a^nb^n

        

        // Three states, state 0 is the start state

        PDA a = new PDA(3,0);

        

        // One transitions from state 0
        a.addTransition(0,1,"a","e","a");
		
	
        // Three transitions from state 1
        a.addTransition(1,1,"a","e","a");
        
        a.addTransition(1,2,"#","e","e");// input #, transite from 1 to 2,
stack unchange
        a.addTransition(1,2,"!","e","e");// input !, transite from 1 to 2,
stack unchange        

        // One transition from state 2

        a.addTransition(2,2,"b","a","e");

        // State 2 is the final state.

        a.addFinalState(2);

        

        // For each input string, check value of isAccepted()
		

        for (int i = 0; i < args.length; i++) {
      
            System.out.println("\nInput String: "+args[i]);

            if (a.isAccepted(args[i])) {

                System.out.println("Accepted");

            } else {

                System.out.println("Rejected");

            }

        }



    }

}