题解 | #矩阵乘法计算量估算#

#include <stdio.h>
#include <string.h>
struct stack{
    char fu[100];
    int top;
};

struct stack zimu;

void addzimu(char c){
    zimu.fu[++zimu.top]=c;
}

char popzimu(void){
    char temp;
    temp=zimu.fu[zimu.top];
    zimu.top--;
    return temp;
}

int main(){
    int i,j, n,len;
    char str[100];
    while(scanf("%d",&n)!=-1){
        int nums[2][n];
        long int out=0,temp;
        char temp1,temp2;
        zimu.top=-1;
        for(i=0;i<n;i++){
            scanf("%d",&nums[0][i]);
            scanf("%d",&nums[1][i]);
        }
        scanf("%s",str);

        len=strlen(str);
        for(i=0;i<len;i++){
            if(str[i]=='(') addzimu(str[i]);
            if((str[i]>='A')&&(str[i]<='Z')){
                if((zimu.top!=-1)&&(zimu.fu[zimu.top]>='A')&&(zimu.fu[zimu.top]<='Z')){
                    temp1=zimu.fu[zimu.top]-65;
                    temp2=str[i]-65;
                    temp=nums[0][temp1]*nums[1][temp1]*nums[1][temp2];
                   
                    out+=temp;
                    nums[1][temp1]=nums[1][temp2];
                    
                }
                else addzimu(str[i]);
            }
            if((str[i]==')')&&(zimu.top>1)){
                temp2=popzimu()-65;
                popzimu();
                if(zimu.fu[zimu.top]!='('){
                    temp1=zimu.fu[zimu.top]-65;
                    temp=nums[0][temp1]*nums[1][temp1]*nums[1][temp2];
                   
                    out+=temp;
                    nums[1][temp1]=nums[1][temp2];
                }
                else addzimu(temp2+65);
            }
        }
        printf("%ld\n",out);
    }
    return 0;
}