首页 > 代码库 > UVa 442 矩阵链乘及scanf说明符中的\n

UVa 442 矩阵链乘及scanf说明符中的\n

题目:计算题给矩阵相乘次序所需的相乘次数。   我们已知的m*n和n*k矩阵相乘,得到的是m*k矩阵,但需要的相乘次数是m*n*k(开始当成了m*k %>_<%)。evaluate,求值

思路:每个矩阵用结构体表示,有名字、行、列、需要计算的次数。矩阵相乘的过程用栈来模拟。遇到左括号(,压栈这是自然的。遇到一个矩阵时,检查栈顶,如果栈顶元素是左括号,则压栈,否则就是矩阵,则比较栈顶矩阵和输入矩阵是否匹配,如果匹配则修改栈顶矩阵的列、计算次数,这样输入矩阵对栈顶进行了修改,相当于完成了相乘,这时栈顶矩阵已经是它们相乘的结果矩阵了。遇到右括号),需要将栈顶矩阵和其下面的左括号出栈,再将出栈的矩阵入栈。(这里可以保证矩阵不会连续存于栈里的,因为每次矩阵入栈时,如果栈顶元素是矩阵,就会进行相乘,只留结果矩阵的。)该矩阵再入栈时,需要坚持栈顶元素是否为矩阵,若为矩阵,则进行相乘,这里在修改计算次数时,不仅要加上左矩阵的次数、m*n*k,还有加上右矩阵结构体中的计算次数。  其他的还有一些边界条件需要注意的,比如这里栈顶指针top初始为0,以及一直保持着栈顶指针指向栈顶元素,top==0表示栈为空,top==n表示栈中有n个元素。

这里,在用矩阵名字来索引其在结构体数组中的位置时,增加了一个索引矩阵index2(index是c/c++的函数。。。)。即index2[name-‘A‘]表示的是name矩阵在结构体数组a中的位置。这个在输入矩阵时进行维护即可。  另外,由于有多组数据,在对每组数据进行处理时,应对结构体数组副本进行处理,所以用了memcpy对结构体数组进行了复制。

scanf("...\n");  scanf 说明符中的 \n 很特别,不是要求输入一个回车换行。它过滤空格、制表符、回车等空白符输入,在scanf("%d\n",&i); printf("%d\n",i);中,输入一个数后不会立即显示,要等再接收到一个非空白符的输入,scanf语句的输入才结束。参考:这里

//注释是C99中的。

Code:

//#define LOCAL
#include<stdio.h>
#include<string.h>

struct matrix
{
 char name;
 int m,n,num;      
};

matrix a[30];
matrix b[30];
int index2[30];  //额,index是C/C++的函数 
char stack[100];

int main()
{
 #ifdef LOCAL
  freopen("442.in","r",stdin);
  freopen("442.out","w",stdout);
 #endif
 int n;
 scanf("%d",&n);
 getchar(); 
 for(int i=0;i<n;++i)
 {
  scanf("%c%d%d",&b[i].name,&b[i].m,&b[i].n);
  b[i].num=0;
  index2[b[i].name-‘A‘]=i;
  getchar();       
 }
 /*for(int i=0;i<n;++i)
 { printf("%c %d %d\n",b[i].name,b[i].m,b[i].n);
   printf("%c:%d\n",b[i].name,index[b[i].name-‘A‘]);
 } */
 char c;
 while((c=getchar())!=EOF)
 {
  memset(stack,0,sizeof(stack));
  memcpy(a,b,sizeof(b));
  //for(int i=0;i<n;++i){ printf("%c %d %d\n",a[i].name,a[i].m,a[i].n);printf("%c:%d\n",a[i].name,index[a[i].name-‘A‘]);}
  int top=0;//top等于0时栈为空 
  int flag=1;
  while(c!=‘\n‘)
  {
   if(c==‘(‘) stack[++top]=c;
   else if(c==‘)‘)
   {
    char d=stack[top--];
    stack[top]=d;    
    if(top-1>0 && stack[top-1]!=‘(‘&&stack[top-1]!=‘)‘)
    { int yix=index2[stack[top]-‘A‘],zix=index2[stack[top-1]-‘A‘];
      if(a[zix].n!=a[yix].m) flag=0;
      else { a[zix].n=a[yix].n; 
             a[zix].num+=a[zix].m*a[yix].n*a[yix].m+a[yix].num;
             top--;
           }
    }
   }    
   else
   {//读入字母 
    if(stack[top]==‘(‘) stack[++top]=c;
    else if(top==0) stack[++top]=c;
    else
    {
     char d=stack[top];
     int dix=index2[d-‘A‘],cix=index2[c-‘A‘];
     if(a[dix].n!=a[cix].m) flag=0;
     else {
           a[dix].n=a[cix].n;
           a[dix].num=a[dix].num+a[dix].m*a[cix].n*a[cix].m+a[cix].num;
          }    
    }//else  
   }//else 
   if(flag==0) while((c=getchar())!=‘\n‘);
   else c=getchar();        
  }//whilec         
  //printf("%d\n",stack[top]);
  if(flag==0) printf("error\n");
  else printf("%d\n",a[index2[stack[top]-‘A‘]].num);//这里不是a[top],也不是a[stack[top]]。。。               
 }//while
 return 0;   
}