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

package main

import (
	"fmt"
)

type Matrix struct {
    Row int
    Col int
}

func calTwoMatrixMulCount(rowA int, rowB int, colA int, colB int) int {
    return rowA * colB * colA
}

func calMulCount(s string, matrixMap map[byte]Matrix) int {
    var cnt int
    
    var stk1 []Matrix
    var stk2 []byte

    for i:=0; i<len(s); i++ {
        if s[i] == '(' {
            stk2 = append(stk2, s[i])
        } else if s[i] == ')' {
            m1, m2 := stk1[len(stk1)-2], stk1[len(stk1)-1]
            stk1 = stk1[:len(stk1)-2]
            
            cnt += calTwoMatrixMulCount(m1.Row, m1.Col, m2.Row, m2.Col)
            stk1 = append(stk1, Matrix{Row:m1.Row, Col: m2.Col})

            // 弹出左括号
            stk2 = stk2[:len(stk2)-1]
        } else {
            matrix := matrixMap[s[i]]
            stk1 = append(stk1, Matrix{Row: matrix.Row, Col: matrix.Col})
        }
    }

    return cnt
}

func main() {
    var n int
    fmt.Scan(&n)

    matrixMap := make(map[byte]Matrix)
    startIndex := byte('A')
    for i:=0; i<n; i++ {
        var row, col int
        fmt.Scan(&row, &col)
        matrixMap[byte(int(startIndex)+i)] = Matrix{Row: row, Col: col}
    }

    var s string
    fmt.Scan(&s)

    cnt := calMulCount(s, matrixMap)
    fmt.Println(cnt)
}

// 本题输入为每行两个整数，所以采用：fmt.Scan(&row, &col)