/**
 *  Resolviendo el Problema del orden de la cadena de Matrices
 *  por Programacion Dinamica
 *
 *@author     is111936
 *@created    November 20, 2001
 */

import java.applet.Applet;
import java.awt.event.*;
import java.awt.*;
import java.lang.*;


public class Matrix1 extends Applet implements ActionListener {
	int MAXIMO = 100;
	Panel Arriba, Abajo, Ombligo;
	Label ackkck, cmat, AlFin, EtiquPar, FinM, FinS;
	TextField TAam;
	int Arr[], size, size2, ini, fin;
	int[][] LaMswap, MhmH;
	TextArea m, s, Parentesis;
	Button Reset, Calcular;
	Panel Pan1, Pan2, Pan3, Pan4, Pan5, Pan6, Pan7;


	/**
	 *  Action Performed
	 *
	 *@param  evento  Description of Parameter
	 */
	public void actionPerformed(ActionEvent evento) {
		if ((evento.getSource()).equals(Calcular)) {
			Cargatelas();
			Parentesis.setText("");
			llena();
			ShowThaMatrix();
			
			ini = 0;
			fin = size - 1;
			String sfin;
			sfin = Integer.toString(LaMswap[ini][fin]);
			AlFin.setText("Mejor Costo Total = " + sfin);

			Parentesis.setText("");
			Parentesis.append(HumanLanguage(CadGen()));

		}
		else if ((evento.getSource()).equals(Reset)) {
			TAam.setText("");
			Parentesis.setText("");
			m.setText("");
			s.setText("");
		}

	}


	/**
	 *  Init del applet
	 */
	public void init() {
		MAXIMO = 100;
		ackkck = new Label("Introduce las matrices (Separadas Por comas):");
		TAam = new TextField(50);

		cmat = new Label("Tamano : 0");
		AlFin = new Label("Mejor Costo Total = 0");
		EtiquPar = new Label("Expresion : ");
		Parentesis = new TextArea("", 1, 50, 2);

		Reset = new Button("Reset");
		Calcular = new Button("Calcular Orden");

		FinM = new Label("Tabla  M :");
		FinS = new Label("Tabla  S :");

		m = new TextArea("", 10, 55);
		s = new TextArea("", 10, 55);

		setLayout(new GridLayout(3, 1));

		Arriba = new Panel();
		Arriba.setLayout(new GridLayout(3, 1));
		Ombligo = new Panel();
		Ombligo.setLayout(new GridLayout(1, 2));
		Abajo = new Panel();
		Abajo.setLayout(new GridLayout(1, 2));

		Parentesis.setEditable(false);
		Pan1 = new Panel();
		Pan2 = new Panel();
		Pan3 = new Panel();
		Pan4 = new Panel();
		Pan5 = new Panel();

		Pan6 = new Panel(new GridLayout(1, 2));
		Pan7 = new Panel();

		Pan1.add(cmat);
		Pan2.add(ackkck);
		Pan2.add(TAam);
		Pan2.add(Calcular);
		Calcular.addActionListener(this);
		Pan2.add(Reset);
		Reset.addActionListener(this);


		Arriba.add(Pan2);
		Arriba.add(Pan1);
		Arriba.add(Pan3);
		add(Arriba);

		Pan4.add(FinM);

		Pan4.add(m);
		m.setEditable(false);

		Pan5.add(FinS);

		Pan5.add(s);
		s.setEditable(false);

		Ombligo.add(Pan4);
		Ombligo.add(Pan5);
		add(Ombligo);


		Pan6.add(EtiquPar);

		Pan6.add(Parentesis);
		Pan6.add(AlFin);

		Abajo.add(Pan6);

		add(Abajo);

	}


	/**
	 *  Solucion al problema
	 */
	public void llena() {
		LaMswap = new int[size][size];
		MhmH = new int[size][size];

		for (int w = 0; w < size; w++) {
			LaMswap[w][w] = 0;
			MhmH[w][w] = 0;
		}

		for (int k = 1; k < size; k++) {
			for (int i = 0; i < (size - k); i++) {
				int j = (i + k);
				LaMswap[i][j] = 1000000000;
				//infinito
				for (int n = i; n < j; n++) {
					int q = LaMswap[i][n] + LaMswap[n + 1][j] + Arr[i] * Arr[n + 1] * Arr[j + 1];
					if (q < LaMswap[i][j]) {
						LaMswap[i][j] = q;
						MhmH[i][j] = n + 1;
					}
				}
			}
		}
	}


	/**
	 *  Crear una cadena con los parentesis correspondientes
	 *
	 *@param  cad  Description of Parameter
	 *@return      Description of the Returned Value
	 */
	public String HumanLanguage(String cad) {
		String tem;
		String temp;
		String temPan1;
		String ayuda;
		String ayuda1;
		String div1;
		String inicio = new String("(");
		String f = new String(")");
		if (((cad.length()) == 3) || ((cad.length()) == 6)) {
			tem = inicio.concat(cad);
			temp = tem.concat(f);
		}
		else {
			int i;
			int t;
			int j;
			char r;
			char l;
			t = cad.length() - 1;
			i = ((int) (cad.charAt(1) - (int) '0') * 10) + (int) (cad.charAt(2) - (int) '0');
			j = ((int) (cad.charAt(t - 1) - (int) '0') * 10) + (int) (cad.charAt(t) - (int) '0');

			int div = MhmH[i - 1][j - 1];

			div1 = "M";

			if (div > 9) {
				div1 = (div + "");

			}
			else {
				div1 = ("0" + div + "");

			}
			int m;
			m = cad.indexOf(div1) + 2;

			ayuda = cad.substring(0, m);
			ayuda1 = cad.substring(m, t + 1);


			temp = HumanLanguage(ayuda);
			temPan1 = HumanLanguage(ayuda1);

			temp = inicio.concat(temp);
			temp = temp.concat(temPan1);
			temp = temp.concat(f);

		}

		return temp;
	}


	/**
	 *  Mostrar los datos en pantalla
	 */
	public void ShowThaMatrix() {
		m.setText("");
		s.setText("");
		String u;
		String v;
		String esp;
		String tit;
		int t = size;
		int band = 0;
		esp = new String("\n");

		m.append("\t");
		s.append("\t");
		for (int r = 1; r <= size; r++) {
			tit = Integer.toString(r);
		}
		m.append("\n");
		s.append("\n");
		for (int i = (size - 1); i >= 0; i--) {
			for (int j = 0; j < t; j++) {
				if (band == 0) {
					tit = Integer.toString(t);

					band = 1;
				}
				u = Integer.toString(LaMswap[j][i]);
				v = new String(" " + u + "\t");
				m.append(v);
			}
			t--;
			m.append(esp);
			band = 0;
		}
		t = size;
		for (int i = (size - 1); i >= 0; i--) {
			for (int j = 0; j < t; j++) {
				if (band == 0) {
					tit = Integer.toString(t);
					band = 1;
				}
				u = Integer.toString(MhmH[j][i]);
				v = new String(" " + u + "\t");
				s.append(v);
			}
			t--;
			s.append(esp);
			band = 0;
		}

	}

	/**
	 *  Description of the Method
	 *
	 *@return    Description of the Returned Value
	 */
	public String CadGen() {
		String Buf;
		String Dos;
		Dos = "";
		char mat = 'A';

		for (int i = 1; i <= (fin + 1); i++) {
			if (i > 9) {
				Buf = (mat + "" + i);
			}
			else {
				Buf = (mat + "0" + i);
			}
			Dos = Dos + Buf;
		}

		return (Dos);
	}

	/**
	 *  Description of the Method
	 */
	void Cargatelas() {
		int i;
		int j;
		int temp;
		int cont;
		int[] atemp = new int[70];
		String cadena;
		String subcadena;
		String scont;
		cadena = (TAam.getText()).concat(",");
		i = 0;
		j = 0;
		cont = 0;
		while (i < cadena.length() && j < MAXIMO) {
			while (i < cadena.length() && (cadena.charAt(i) > '9' || cadena.charAt(i) < '0')) {
				i++;
			}
			if (i == cadena.length()) {
				break;
			}
			temp = 0;
			while (i < cadena.length() && cadena.charAt(i) <= '9' && cadena.charAt(i) >= '0') {
				temp = temp * 10 + (int) cadena.charAt(i) - (int) '0';
				i++;
			}
			if (i == cadena.length()) {
				break;
			}

			atemp[j] = temp;
			j++;
		}
		for (; ; ) {
			if ((atemp[cont] != 0) || (atemp[cont + 1] != 0)) {
				cont++;
			}
			else {
				break;
			}
		}
		size = cont - 1;
		Arr = new int[size + 1];
		for (int q = 0; q < Arr.length; q++) {
			if ((atemp[q] != 0) || (atemp[q + 1] != 0)) {
				Arr[q] = atemp[q];
			}
		}
		scont = Integer.toString(cont - 1);
		cmat.setText("Tamano :" + scont);
	}
}