首页 > 代码库 > Matrix Chain Multiplication UVA 442 (栈 表达式求值)

Matrix Chain Multiplication UVA 442 (栈 表达式求值)

说说:

其实这道题是栈这个数据结构最经典的运用,即表达式的求值。与一般情况不同的是,此次要求的运算数是矩阵。在整个解析表达式的过程中,无非遇到三类字符,一个是‘(‘,另一个是‘)’,剩下的就是运算数了。首先,在遇到‘(’的时候,栈指针自动加一,并将栈顶元素的行数和列数都设置为-1,这样就不会和正常的运算数混淆了。如果遇到的是运算数,首先要判断当前的栈顶元素是否为运算数(当然,还要注意栈为空的特殊情况)。若是,则直接将新的运算数与栈顶运算数进行计算,否则将新运算数入栈。还有最后一种情况就是遇到‘)’。此时,栈顶必为运算数,且栈顶的下一个元素必定是‘(’所以只要将栈顶元素下移一位即可。在这里有一点要特别注意,此时可能会出现两个栈的顶部出现连续的两个运算数(至多两个,三个是不可能的),因为在这种情况下,我们还要对这两个元素进行运算。不断重复上述步骤,整个题目就搞定啦!

源代码:

#include <stdio.h>
#define MAXN 26+5

typedef struct{
 int x;
 int y;
}Matrix;

int main(){
 int n,i,p,wrong,ans;
 char c;
 Matrix stack[MAXN],current,data[MAXN];
// freopen("data","r",stdin);
 scanf("%d\n",&n);
 for(i=0;i<n;i++)
   scanf("%c %d%d\n",&c,&data[i].x,&data[i].y);
 
 while(1){
  p=wrong=ans=0;
  while((c=getchar())!='\n'){
   if(c=='('){
     stack[p].x=stack[p].y=-1;//填充无效数,栈指针上移
     p++;
   }
   else if(c==')'){
     p--;
     stack[p-1].x=stack[p].x;//栈顶元素向下移动一位
     stack[p-1].y=stack[p].y;
     if(p-2>=0&&stack[p-2].x!=-1){//若此时栈顶存在连续两个运算数
      p--;
      if(stack[p-1].y!=stack[p].x)
        wrong=1;
      ans+=stack[p-1].x*stack[p-1].y*stack[p].y;
      stack[p-1].y=stack[p].y;
     }
   }
   else{
     if(p==0||stack[p-1].x==-1){
       stack[p].x=data[c-'A'].x;
       stack[p].y=data[c-'A'].y;
       p++;
     }
     else{
       if(stack[p-1].y!=data[c-'A'].x)
         wrong=1;
       ans+=stack[p-1].x*stack[p-1].y*data[c-'A'].y;
       stack[p-1].y=data[c-'A'].y;
     }
   }
  }

  if(wrong)//wrong为1标识着在运算过程中存在着不符合矩阵运算法则的情况
    printf("error\n");
  else 
    printf("%d\n",ans);

  if((c=getchar())==EOF)
    break;
  else 
    ungetc(c,stdin);
 }
 
 return 0;
}


Matrix Chain Multiplication UVA 442 (栈 表达式求值)