matrix.c

ulm大学1996-1999年的竞赛题和解题报告

/* University of Ulm Programming Contest 1996
   Problem G: Matrix Chain Multiplication
   Implementation: Mark Dettinger */

#include <stdio.h>

typedef struct {int mults; int rows; int cols;} triple;  

int rows[256],cols[256];  /* sizes of the matrices               */
char e[100];              /* the expression that is to be parsed */
int p;                    /* current position during parsing     */
char error;               /* error flag                          */

triple expression()
{
  /* Precondition: The expression to be parsed begins at &e[p]. */

  triple t;
  if (e[p]=='(')  /* Case 1: Expr -> ( Expr Expr ) */
    {
      triple t1,t2;
      p++;
      t1 = expression();
      t2 = expression();
      p++;
      if (t1.cols!=t2.rows) error = 1;  /* matrices are incompatible */
      t.rows  = t1.rows;
      t.cols  = t2.cols;
      t.mults = t1.mults+t2.mults+t1.rows*t1.cols*t2.cols;
    }
  else            /* Case 2: Expr -> Matrix */ 
    {
      t.rows = rows[e[p]];
      t.cols = cols[e[p]];
      t.mults = 0;
      p++;
    }
  return t;  

  /* Return Value: a triple consisting of three integers representing
                   - the number of needed multiplications 
		   - the number of rows of the resulting matrix
		   - the number of columns of the resulting matrix */

  /* Postcondition: &e[p] points to the character after the expression
     that has been parsed */
}

main()
{
  FILE* input = fopen("matrix.in","r");
  char c;
  int i,n,ro,co;
  triple t;
  
  fscanf(input,"%d%c",&n,&c);  /* read number of matrices */
  for (i=0; i<n; i++)          /* read sizes of matrices */
    {
      fgets(e,99,input);
      sscanf(e,"%c %d %d",&c,&ro,&co);
      rows[c] = ro;
      cols[c] = co;
    }
  while (1)               /* for each expression do */
    {
      fgets(e,99,input);       /* read expression */
      if (feof(input)) break;
      p = error = 0;           /* parse expression */
      t = expression();      
      if (error)               /* print result */
	puts("error");
      else
	printf("%d\n",t.mults);
    }
  fclose(input);
  return 0;
}