/*
 * Created on Jan 31, 2004
 */
import java.util.*;
/**
 * @author David Matuszek
 * @version Jan 31, 2004
 */
public class Parser {
    Tokenizer tokenizer = null;
    
    /**
     * The stack used for holding BinaryTrees as they are created.
     * Only BinaryTrees should be put on the stack.
     */
    public Stack stack = new Stack();

    /**
     * Constructs a Recognizer for the given string.
     * @param text The string to be recognized.
     */
    public Parser(String text) {
        tokenizer = new Tokenizer(text);
    }

    /**
     * Tries to recognize an <expression>.
     * <pre>&lt;expression&gt; ::= &lt;term&gt;
     *               | &lt;term&gt; &lt;add_operator&gt; &lt;expression&gt;</pre>
     * A <code>LogoParseException</code> will be thrown if the add_operator
     * is present but not followed by a valid &lt;expression&gt;.
     * @return <code>true</code> if an expression is recognized.
     */
    public boolean expression() {
        if (!term())
            return false;
        while (addOperator()) {
            if (!term())
                error("Error in expression after '+' or '-'");
            makeTree(2, 1, 3);
        }
        return true;
    }

    /**
     * Tries to recognize a &lt;term&gt;.
     * <pre>&lt;term&gt; ::= &lt;factor&gt;
     *         | &lt;factor&gt; &lt;multiply_operator&gt; &lt;term&gt;</pre>
     * A <code>LogoParseException</code> will be thrown if the multiply_operator
     * is present but not followed by a valid &lt;term&gt;.
     * @return <code>true</code> if a term is recognized.
     */
    public boolean term() {
        if (!factor())
            return false;
        while (multiplyOperator()) {
            if (!factor())
                error("No term after '*' or '/'");
            makeTree(2, 1, 3);
        }
        return true;
    }

    /**
     * Tries to recognize a &lt;factor&gt;.
     * <pre>&lt;factor&gt; ::= &lt;name&gt;
     *           | &lt;number&gt;
     *           | "(" &lt;expression&gt; ")"</pre>
     * A <code>LogoParseException</code> will be thrown if the opening
     * parenthesis is present but not followed by a valid
     * &lt;expression&gt; and a closing parenthesis.
     * @return <code>true</code> if a factor is recognized.
     */
    public boolean factor() {
        if (name())
            return true;
        if (number())
            return true;
        if (symbol("(")) {
            stack.pop();
            if (!expression())
                error("Error in parenthesized expression");
            if (!symbol(")"))
                error("Unclosed parenthetical expression");
            stack.pop();
            return true;
        }
        return false;
    }

    /**
     * Tries to recognize an &lt;add_operator&gt;.
     * <pre>&lt;add_operator&gt; ::= "+" | "-"</pre>
     * @return <code>true</code> if an addop is recognized.
     */
    public boolean addOperator() {
        return symbol("+") || symbol("-");
    }

    /**
     * Tries to recognize a &lt;multiply_operator&gt;.
     * <pre>&lt;multiply_operator&gt; ::= "*" | "/"</pre>
     * @return <code>true</code> if a multiply_operator is recognized.
     */
    public boolean multiplyOperator() {
        return symbol("*") || symbol("/");
    }

    //------------------------- Private "helper" methods

    /**
     * Tests whether the next token is a number. If it is, the token
     * is consumed, otherwise it is not.
     * 
     * @return <code>true</code> if the next token is a number.
     */
    private boolean number() {
        return nextTokenMatches(Token.NUMBER);
    }

    /**
     * Tests whether the next token is a name. If it is, the token
     * is consumed, otherwise it is not.
     * 
     * @return <code>true</code> if the next token is a name.
     */
    private boolean name() {
        return nextTokenMatches(Token.NAME);
    }

    /**
     * Tests whether the next token is the expected name. If it is, the token
     * is consumed, otherwise it is not.
     * 
     * @param expectedName The String value of the expected next token.
     * @return <code>true</code> if the next token is a name with the expected value.
     */
    private boolean name(String expectedName) {
        return nextTokenMatches(Token.NAME, expectedName);
    }

    /**
     * Tests whether the next token is the expected symbol. If it is,
     * the token is consumed, otherwise it is not.
     * 
     * @return <code>true</code> if the next token is the expected symbol.
     */
    private boolean symbol(String expectedSymbol) {
        return nextTokenMatches(Token.SYMBOL, expectedSymbol);
    }

    /**
     * If the next Token has the expected type, it is used as the
     * value of a new (childless) BinaryTree node, and that node
     * is then pushed onto the stack. If the next Token does not
     * have the expected type, this method effectively does nothing.
     * 
     * @param type The expected type of the next token.
     * @return <code>true</code> if the next token has the expected type.
     */
    private boolean nextTokenMatches(int type) {
        Token t = tokenizer.next();
        if (t.getType() == type) {
            stack.push(new BinaryTree(t));
            return true;
        }
        else
            tokenizer.pushBack(t);
        return false;
    }

    /**
     * If the next Token has the expected type and value, it is used as
     * the value of a new (childless) BinaryTree node, and that node
     * is then pushed onto the stack; otherwise, this method does
     * nothing.
     *
     * @param type The expected type of the next token.
     * @param value The expected value of the next token; must
     *              not be <code>null</code>.
     * @return <code>true</code> if the next token has the expected type.
     */
    private boolean nextTokenMatches(int type, String value) {
        Token t = tokenizer.next();
        if (type == t.getType() && value.equals(t.getValue())) {
            stack.push(new BinaryTree(t));
            return true;
        }
        else {
            tokenizer.pushBack(t);
        }
        return false;
    }

    /**
     * Replaces the top three objects on the stack with a BinaryTree.
     * The three elements are numbered in the order they were put on the
     * stack.<br>
     * <b>Example:</b> If elements had been put onto the stack in the
     * order x, y, z, then 1 refers to x, 2 to y, and 3 to z. The call
     * <code>makeTree(2, 1, 3)</code> would result in y at the root,
     * x as the left child, and z as the right child.
     * 
     * @param rootIndex Which of the three stack elements (1 = leftmost element,
     *             2 = middle element, 3 = rightmost element) to use as the
     *             value of the root of the BinaryTree.
     * @param leftIndex Which of the three stack elements to use as the left
     *             subtree of the BinaryTree.
     * @param rightIndex Which of the three stack elements to use as the right
     *              subtree of the BinaryTree.
     */
    private void makeTree(int rootIndex, int leftIndex, int rightIndex) {
               
        BinaryTree root = getStackItem(rootIndex);
        BinaryTree leftChild = getStackItem(leftIndex);
        BinaryTree rightChild = getStackItem(rightIndex);
        
        Token rootValue = (Token) (root.value);
        
        stack.pop();
        stack.pop();
        stack.pop();
        
        stack.push(new BinaryTree(rootValue, leftChild, rightChild));
    }
    
    /**
     * Returns, as a BinaryTree, one of the top three elements of the
     * instance variable <code>stack</code>: 3 gets the top element,
     * 2 gets the second from the top, and 1 gets the third from the
     * top.
     * 
     * @param n Which of the top three elements of the stack, counting
     *          3 as the top element, to return.
     * @return One of the top three elements of the stack.
     */
    private BinaryTree getStackItem(int n) {
        return (BinaryTree) stack.get(stack.size() - 4 + n);
    }

    /**
     * Utility routine to throw a <code>LogoParseException</code> with the
     * given message.
     * @param message The text to put in the <code>LogoParseException</code>.
     */
    private void error(String message) {
        throw new LogoParseException(message);
    }
}