首页 > 代码库 > 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 (栈 表达式求值)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。