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

let line
let arr = []



const getIndex = (code) =>{
//     A的unicide编码为65,即A-0 B-1以此类推
    return code.charCodeAt() - 65
}
// 7
// 47 45
// 45 31
// 31 20
// 20 35
// 35 59
// 59 42
// 42 28
// (A((B(C(DE)))(FG)))

while(line = readline()){
    arr.push(line);
    if(arr.length>1){
        let count = parseInt(arr[0])
        
        if(arr.length == count + 2){
            let metrixArr = JSON.parse(JSON.stringify(arr)).splice(1,arr.length - 2).map(i=>i.split(' ').map(i=>parseInt(i)))
            let calcStr = arr[arr.length - 1]
            let loop = calcStr.split('');
            let calcCount = 0
            let tempArr =  []
            for(let j = loop.length - 1;j>=0;j--){
                     if(loop[j] == '('){
//                      取出最近两个数(倒数第二个和倒数第一个)
                     let n1 = tempArr.pop()
                     let n2 = tempArr.pop()
                     calcCount += metrixArr[getIndex(loop[n1])][0] * metrixArr[getIndex(loop[n1])][1] * metrixArr[getIndex(loop[n2])][1];
//                      将矩阵的乘法次数进行相加。loop[n1]代表在原数组的索引代表的值比如 ‘(A((B(C(DE)))(FG)))’  n1 = 14 代表 loop[n1]代表F  n2 = 15 loop[n2]代表G
//                      矩阵乘法公式 【m,n】 *[n,p] 即 m*n*p  

                     metrixArr[getIndex(loop[n1])][1] = metrixArr[getIndex(loop[n2])][1]
//                      然后将 【m,p】的p和下一个矩阵进行相乘
//                      然后将 最后一次的索引添加到数组，重置p
                     tempArr.push(n1)
//                      n1,n2的值依次打印为
//                      14 15
//                      8 9
//                      6 8
//                      4 6
//                      4 14
//                      1 4
//tempArr的值依次打印为
// 14
// 14,8
// 14,6
// 14,4
// 4
// 1
//                      所以可以看出。14*15 是单独的运算 然后是8*9*6*4 *14 * 1  即为 D*E*C*B * FG * A /FG运算后的n1即为14 符合规律
                 }else if(loop[j] != '(' && loop[j] != ')'){
                     tempArr.push(j)
                 }
             }
            arr = []
            console.log(calcCount)
        }
    }
}