public class Parser2 {
	// *****************************************************************
	// the tokens of the language:

	/** Opening bracket */
	private final static String LPAREN = "(";

	/** Closing bracket */
	private final static String RPAREN = ")";

	/** Operator for conjunction */
	private final static String AND = "and";

	/** Operator for disjunction */
	private final static String OR = "or";

	/** Operator for implication */
	private final static String IMPLIES = "implies";

	/** Operator for negation */
	private final static String NOT = "not";

	/** Constant: true */
	private final static String TRUE = "true";

	/** Constant: false */
	private final static String FALSE = "false";

	// *****************************************************************
	// fields

	/**
	 * Stores the string to be parsed as an array of characters.
	 */
	private byte[] input;

	/**
	 * Index of the current character in the string.
	 *
	 * The string to be parsed is read character-by-character; this field stores
	 * the location of the character currently being read. As each character is
	 * read, this field should be incremented.
	 */
	private int index;

	/**
	 * Index of the last accepted character.
	 *
	 * Sometimes a character is read that needs to be "put back"; for example,
	 * reading an opening bracket causes a recursive call of the
	 * {@link #parseToPrec(int) parseToPrec()} method, that will read an entire
	 * term up until the closing bracket; once the closing bracket is read in
	 * the recursive call, that call "puts the bracket back" by setting
	 * {@link #index index} to the value of <code>backIndex</code> and returns
	 * the term it has read; in the calling method, the closing bracket is read
	 * (to check that brackets match).
	 */
	private int backIndex;

	// *****************************************************************

	/**
	 * Parse a string representing a term in propositional logic.
	 *
	 * @param s
	 *            the <code>String</code> string to be parsed
	 * @return the <code>BoolTerm</code> representing that term
	 */
	public BoolTerm parse(String s) {
		// store the string as an array of bytes, removing any leading
		// or trailing spaces
		input = s.trim().getBytes();

		// move to start of input
		backIndex = 0;
		index = 0;

		if (input.length == 0){
			System.out.println("Empty input");
			return null;
		}

		BoolTerm t = parseToPrec(Operators.MAX_PREC);

		// check that input is fully read
		if (index != input.length){
			System.out.println("Expected input to end at character number " + index);
			return null;
		}

		// otherwise
		return t;
	}

	// *****************************************************************
	/**
	 * parse a term
	 *
	 * This method parses a term according to the precedence of its operators;
	 * for example, a term "a or b and c" will be parsed as a or (b and c) since
	 * "and" has a lower precedence than "or".
	 *
	 * The argument gives a precedence value, and the routine will return the
	 * BoolTerm corresponding to the largest initial substring of the input that
	 * does not contain an operator with a higher precedence than the argument
	 * (unless such an operator with higher precedence is nested in
	 * parentheses). Thus, calling the routine with MAXPREC causes the entire
	 * string to be parsed, because no operator can have a higher precedence
	 * than MAXPREC.
	 *
	 * Thus a call parseToPrec(p) will construct a term from the largest
	 * possible initial segment of the input string, that contains no operators
	 * with precedence higher than p, unless they are nested in brackets.
	 *
	 * @param prec
	 *            the precedence of an operator; the method recursively reads a
	 *            term until an operator of greater precedence is read
	 * @return the <code>BoolTerm</code> representing the term read
	 */
	private BoolTerm parseToPrec(int prec) {
		BoolTerm t1, t2;
		Operator op;

		// read the first term
		t1 = readOneTerm();
		backIndex = index;

		// read an operator
		int pr; // the precedence of the operator
		String s;
		while (!endOfInput()) {
			s = nextToken();
			// if s is a closing bracket, then t1 is the largest subterm
			// that can be read
			if (s.equals(RPAREN)) {
				index = backIndex;
				return t1;
			}

			// otherwise, the next token should be an operator
			op = getOperator(s);
			pr = op.getPrecedence();

			// only read further if the precedence of the new operator
			// is no greater than prec
			if (pr > prec) {
				index = backIndex;
				return t1;
			} else // op has lower precedence
			{
				t2 = parseToPrec(pr);
				t1 = new BoolTerm(op, new BoolTerm[] { t1, t2 });
			}
		}
		return t1;
	}

	/**
	 * Parse the smallest initial segment that can be read as a valid term.
	 *
	 * @return A {@link BoolTerm BoolTerm} representing the initial term
	 */
	private BoolTerm readOneTerm() {
		BoolTerm t;
		String s = nextToken();
		if (s.equals(LPAREN)) {
			t = parseToPrec(Operators.MAX_PREC);
			read(RPAREN);
			return t;
		}
		if (s.equals(NOT)) {
			t = parseToPrec(Operators.NOT_PREC);
			return new BoolTerm(Operators.NOT, new BoolTerm[] { t });
		}
		if (s.equals(TRUE)) {
			return new BoolTerm(Operators.TRUEC);
		}
		if (s.equals(FALSE)) {
			return new BoolTerm(Operators.FALSEC);
		}
		t = new BoolTerm(Operators.makeVar(s));
		return t;
	}

	/**
	 * Test whether the end of the input string has been reached
	 *
	 * @return <code>true</code> when {@link #index index} points to the end of
	 *         {@link #input input}; <code>false</code> otherwise
	 */
	private boolean endOfInput() {
		return (index == input.length);
	}

	// *****************************************************************
	/**
	 * Parse a string as the name of an {@link Operator Operator}. The string
	 * should be the name of one of the operators declared in {@link Operators
	 * Operators.java}.
	 *
	 * @param s
	 *            a string representing the name of an {@link Operator Operator}
	 * @return the {@link Operator Operator} representing the initial term
	 */
	private Operator getOperator(String s) {
		if (s.equals(AND)) {
			return Operators.AND;
		}
		if (s.equals(OR)) {
			return Operators.OR;
		}
		if (s.equals(IMPLIES)) {
			return Operators.IMPLIES;
		}
		else{
			System.out.println(
				"Expected one of \"and\", \"or\", or \"implies\"");
			return null;
		}
	}

	/**
	 * Parse the smallest initial segment that can be read as a token
	 *
	 * @return the smallest initial string that can be read as a token
	 */
	private String nextToken() {
		if (input[index] == '(') {
			index++;
			readWhiteSpace();
			return LPAREN;
		}
		if (input[index] == ')') {
			index++;
			readWhiteSpace();
			return RPAREN;
		}
		return readLiteral();
	}

	/**
	 * Check that the next part of the input is a given string.
	 *
	 * @param s
	 *            the string that is expected to be next in the input
	 */
	private void read(String s) {
		String t = readNext(s.length());
		if (!t.equals(s))
			System.out.println("Expected " + s + " at character number "
					+ (index - s.length()));
	}

	/**
	 * Remove any leading white space in the input. {@link #index index} is
	 * incremented while the current input is white space
	 */
	private void readWhiteSpace() {
		while ((!endOfInput()) && isWhiteSpace())
			index++;
	}

	/**
	 * Test whether the current input is white space.
	 *
	 * @return <code>true</code> if the current input character is white space
	 */
	private boolean isWhiteSpace() {
		byte b = input[index];
		return (b == 9 || b == 10 || b == 32);
	}

	/**
	 * Test whether the current input character is alphanumeric
	 *
	 * @return <code>true</code> if the current input character is a letter or a
	 *         digit; false otherwise
	 */
	private boolean isAlphanum() {
		byte b = input[index];
		return isAlpha(b) || isNum(b);
	}

	/**
	 * Test whether the current input character is a letter
	 *
	 * @return <code>true</code> if the current input character is a letter;
	 *         false otherwise
	 */
	private boolean isAlpha(byte b) {
		return (65 <= b && b < 91) || (97 <= b && b < 123);
	}

	/**
	 * Test whether the current input character is a digit
	 *
	 * @return <code>true</code> if the current input character is a digit;
	 *         false otherwise
	 */
	private boolean isNum(byte b) {
		return 48 <= b && b < 58;
	}

	/**
	 * Read a number of characters in the input.
	 *
	 * @param n
	 *            the number of characters to be read
	 * @return the string consisting of the next <code>n</code> characters from
	 *         input
	 */
	private String readNext(int n) {
		if (index + n > input.length){
			System.out.println("Unexpected end of input");
			return null;
		}

		String s = new String(input, index, n);
		index += n;
		readWhiteSpace();
		return s;
	}

	/**
	 * Read an alphanumeric string from input.
	 *
	 * @return the longest alphanumeric string currently to be read in the input
	 */
	private String readLiteral() {
		int start = index;

		while ((!endOfInput()) && isAlphanum()) {
			index++;
		}
		String s = new String(input, start, index - start);
		readWhiteSpace();
		return s;
	}
	
	
	// Example use:
	public static void main(String[] args) {
		Parser p1 = new Parser();
		try {
			BoolTerm boolTerm = p1.parse("((a and b) or not(b and c))");
			System.out.println(boolTerm.toString());
		} catch (ParseException e) {
			e.printStackTrace();
		}
	}

}// Parser