infixpostfixstring.java

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

import dslib.tree.LinkedSimpleTreeUos;
import dslib.base.*;
import java.io.*;

public class InfixPostfixString
{
	LinkedSimpleTreeUos exprTree;

	public InfixPostfixString() 
	{
		exprTree = new LinkedSimpleTreeUos();
		makeExprTree();
		printExprTree();
	}

	/**	Create the expression tree for 2 * (a + b * c)
		Analysis: Time = (1) */
	public void makeExprTree()
	{
		LinkedSimpleTreeUos t1, t2, t3;
		t1 = new LinkedSimpleTreeUos(null, new Character('b'), null);
		t2 = new LinkedSimpleTreeUos(null, new Character('c'), null);
		t3 = new LinkedSimpleTreeUos(t1, new Character('*'), t2);
		t1 = new LinkedSimpleTreeUos(null, new Character('a'), null);
		t2 = new LinkedSimpleTreeUos(t1, new Character('+'), t3);
		t1 = new LinkedSimpleTreeUos(null, new Character('2'), null);
		exprTree = new LinkedSimpleTreeUos(t1, new Character('*'), t2);
		System.out.println(exprTree);
	}

	public void printExprTree() 
	{
		System.out.println("Infix String " + infixString(exprTree));
		System.out.println("Postfix String " + postfixString(exprTree));
	}

	/**	For the expression tree t, return its expression in standard infix notation. */
	public String infixString(LinkedSimpleTreeUos t)
	{
		if (t.isEmpty())
			return new String();
		else 
		{
			return "(" + infixString((LinkedSimpleTreeUos)t.rootLeftSubtree())
				+ t.rootItem() + infixString((LinkedSimpleTreeUos)t.rootRightSubtree()) + ")"; 
		}
	}

	/**	For the expression tree t, return its expression in standard postfix notation. */
	public String postfixString(LinkedSimpleTreeUos t) 
	{
		if (t.isEmpty())
			return new String();
		else
		{
			return postfixString((LinkedSimpleTreeUos)t.rootLeftSubtree())
				+ postfixString((LinkedSimpleTreeUos)t.rootRightSubtree())
				+ t.rootItem();
		}	
	}

	public static void main(String args[]) throws Exception
	{
		InfixPostfixString c = new InfixPostfixString();
	}
}