abstractmatrixchain.java

<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关 2. 数据结构 2.1 基本数据结构 2.2 散列表 2.3 二叉查找树 2.4 红黑树 2.5 数据结构

/*
 * Copyright (C) 2003-2008 Wang Pengcheng <[e-mail]>
 * Permission is granted to copy, distribute and/or modify this
 * document under the terms of the GNU Free Documentation License,
 * Version 2.0 or any later version published by the Free Software Foundation;
 * with no Invariant Sections.
 * You may obtain a copy of the License at
 *   http://www.gnu.org/licenses/lgpl.txt
 */
//19 Feb 2008
package cn.edu.whu.iss.algorithm.unit15.matrixchain;

public abstract class AbstractMatrixChain implements GetMatrixChainInfor {

	protected long[] p;
	protected int[][] s;
	protected long ans;
	
	public AbstractMatrixChain() {
		super();
	}

	public AbstractMatrixChain(long[] p) {
		super();
		this.p = p;
	}

	public String getOptimalParens(long[] p) {
		this.p = p;
		return getOptimalParens();
	}

	public String getOptimalParens() {
		matrixChainOrder();
		return getOptimalParens(0, p.length-2);
	}
	
	private String getOptimalParens(int i,int j){
		if(i==j){
			return "A"+(i+1);
		}else{
			return "("+getOptimalParens(i, s[i][j])+getOptimalParens(s[i][j]+1, j)+")";
		}
	}

	public long matrixChainOrder(long[] p) {
		this.p = p;
		ans = matrixChainOrder();
		return ans;
	}

}