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

package main

import (
	"fmt"
)

type Matrix2 struct {
	X int
	Y int
	Z int
}

type Stack2 []Matrix2

func (s *Stack2) Push(item Matrix2) {
	*s = append(*s, item)
}

func (s *Stack2) Pop() Matrix2 {
	if len(*s) == 0 {
		panic("can not pop stack!")
	}

	r := (*s)[len(*s)-1]
	*s = (*s)[:len(*s)-1]
	return r
}

func (s *Stack2) Len() int {
	return len(*s)
}

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

	mMap := map[byte]Matrix2{}
	for i := 0; i < n; i++ {
		var x, y int
		_, _ = fmt.Scan(&x, &y)

		mMap[(byte)('A'+i)] = Matrix2{X: x, Y: y, Z: 0}
	}

	// fmt.Printf("mMap: %#v\n", mMap)

	var expr string
	fmt.Scan(&expr)

	// fmt.Printf("expr: %#v\n", expr)

	mStack := Stack2{}
	for _, b := range []byte(expr) {
		if b == ')' {
			p1 := mStack.Pop()
			p0 := mStack.Pop()

			newMatric := Matrix2{X: p0.X, Y: p1.Y, Z: (p0.Z + p1.Z + p0.X*p0.Y*p1.Y)}
			// fmt.Printf("newMatric: %#v\n", newMatric)
			mStack.Push(newMatric)
		} else if b != '(' {
			mStack.Push(mMap[b])
			// fmt.Printf("PUSH: %#v\n", mStack)
		}
	}

	// fmt.Printf("mStack: %#v\n", mStack)

	result := 0
	var leftM *Matrix2
	for {
		m := mStack.Pop()
		if leftM == nil {
			leftM = &m
			result += leftM.Z
			// fmt.Printf("result: %#v\n", result)
		} else {
			result += leftM.X*leftM.Y*m.Y + leftM.X + m.Z
		}

		if mStack.Len() == 0 {
			break
		}
	}

	fmt.Printf("%v\n", result)
}