exprparser.java

来自「国外的数据结构与算法分析用书」· Java 代码 · 共 71 行

/**	Class that parses an expression to build an expression tree */
public class ExprParser
{    
	/**	Scanner shared by all ExprTrees for current expression */
	public ExprScanner scanner;
    
	/**	Create the parser and initialize the scanner. <br>
		Analysis: Time = O(1) */
	public ExprParser(ExprScanner scanner)
	{
		this.scanner = scanner;
	}
    
	/**	Read and build expression tree for an identifier
		Analysis: Time = O(1) */
	public ExprTree identifier()
	{
		scanner.getToken();
		return  new ExprTree(null, scanner.token, null);
	}
    
	/**	Read and build expression tree for a factor.
			<factor> ::= <identifier> | ( <expr> ) ; 
		Analysis: Time = O(n), n = number of characters in the factor */
	public ExprTree factor()
	{
		scanner.getToken();
		if (!scanner.token.equals("("))
			return new ExprTree(null, scanner.token, null);
		else
		{
			ExprTree result = expr();  // expr() reads the ")"
			return result;
		}
	}
    
	/**	Read and build expression tree for a term with one look-ahead token. 
			<term> ::= <factor> | <factor> * <term> | <factor> / <term>
		Analysis: Time = O(n), n = number of characters in the term */
	public ExprTree term()
	{
		ExprTree leftSubtree = factor();
		scanner.getToken();
		Object operator = scanner.token;
		if (!operator.equals("*") & !operator.equals("/"))
			return leftSubtree; //	leftSubtree is the whole term
		else
		{
			ExprTree rightSubtree = term(); // term() reads the next token after the term
			return new ExprTree(leftSubtree, operator, rightSubtree);
		}
	}

	/**	Read and build expression tree for an expr with one look-ahead token. 
			<expr> ::= <term> | <term> + <expr> | <term> - <expr> 
		Analysis: Time = O(n), n = number of characters in the expression */
	public ExprTree expr()
	{
		ExprTree leftSubtree = term(); // term() reads the next token after the term
		Object operator = scanner.token;
		
		if (!operator.equals("+") & !operator.equals("-"))
			return leftSubtree; // leftSubtree is the whole expr
		else
		{
			ExprTree rightSubtree = expr(); // expr() reads the next token after the expression
			return new ExprTree(leftSubtree, operator, rightSubtree);
		}
	}
}