exprtree.java

国外的数据结构与算法分析用书

import dslib.tree.*;
import dslib.exception.*;
import dslib.dictionary.arrayed.ArrayedPKeyedDictUos;

/**	Class that represents an expression tree */
public class ExprTree extends BasicBinaryTreeUos
{    
    
	/**	Construct an empty tree. <br>
		Analysis: Time = O(1) */
	public ExprTree()
	{
		super();
	}

	/**	Create the tree with lt, r, and rt as the left subtree, root item and right subtree,
		respectively (lt and/or rt can be null for an empty subtree).
		Analysis: Time = O(1)  */
	public ExprTree(ExprTree lt, Object r, ExprTree rt) 
	{	
		if (rootNode == null)
			rootNode = new BinaryNodeUos(r);
		else
			rootNode.setItem(r);
		setRootLeftSubtree(lt);
		setRootRightSubtree(rt);
	}

	/**	String representation of the tree for output. <br>
		Analysis: Time = O(n), n = size of the tree */
	public String toString()
	{
		StringBuffer result;

		if (rootLeftSubtree().isEmpty() && rootRightSubtree().isEmpty())
		{
			if(rootItem()==null)
				return " ";
			else
				return rootItem().toString();	
		}	
		else
		{
			result = new StringBuffer();
			result.append ('(');
			result.append (rootLeftSubtree().toString());
			result.append (rootItem().toString());
			result.append (rootRightSubtree().toString());
			result.append (')');
			return new String(result);
		}
	}   

	/**	The value of the expression in `this' tree.
		Analysis: Time = O(size of the tree * access time for symbolTable) */
	public int eval(ArrayedPKeyedDictUos symbolTable)
	{
		if (rootItem() instanceof Integer)
			return ((Integer)rootItem()).intValue();

		String rootString = (String) rootItem();
		ExprTree rightSubtree = (ExprTree) rootRightSubtree();
		ExprTree leftSubtree = (ExprTree) rootLeftSubtree();
		if (rootString.equals("+"))
			return leftSubtree.eval(symbolTable) + rightSubtree.eval(symbolTable);
		else if (rootString.equals("*"))
			return leftSubtree.eval(symbolTable) * rightSubtree.eval(symbolTable);
		else if (rootString.equals("-"))
			return leftSubtree.eval(symbolTable) - rightSubtree.eval(symbolTable);
		else if (rootString.equals("/"))
			return leftSubtree.eval(symbolTable) / rightSubtree.eval(symbolTable);
		else
			return ((Integer)symbolTable.obtain(rootString)).intValue();
	}
}