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

//反对很多人的做法, 都是错的, 没有考虑ABCDEF没有括号从左到右的顺序
//贴上本大神的代码

import java.util.Scanner;
import java.util.Stack;

public class Main
{
    public static void main(String[] args)
    {
        Stack<int[]> stack = new Stack<>();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < 2; j++)
            {
                arr[i][j] = sc.nextInt();
            }
        }
        String str = sc.next();


        //                    行,列,结果
        int[] res = new int[]{0, 0, 0};
        int[] tmp;
        for (int i = 0; i < str.length(); i++)
        {
            char ch = str.charAt(i);
            if (ch == '(')
            {
                //如果res被压栈, 但是又遇到 (
                //(A(((BC)D)E))         (A((
                if (res[2] == 0 && res[0] == 0 && res[1] == 0)
                {
                    stack.push(new int[]{-1, -1, -1});
                }
                //stack里存储的是引用数据类型, 所以进栈前必须new新的空间, 否则tmp永远等于res
                else
                {
                    tmp = new int[]{res[0], res[1], res[2]};
                    stack.push(tmp);
                    res[0] = res[1] = res[2] = 0;
                }

            }//(A(BC))
            else if (ch == ')' && !stack.isEmpty())
            {
                tmp = stack.pop();
                if(tmp[0] != -1)
                {
                    res[2] = tmp[0] * tmp[1] * res[1] + tmp[2] + res[2];
                    res[0] = tmp[0];
                }

            }
            //必须加这个条件, 否则, ch == ')' && stack.isEmpty()时执行这个条件会数组越界错误
            else if (ch >= 'A' && ch <= 'Z')
            {
                int index = ch - 'A';
                if (res[2] == 0 && res[0] == 0 && res[1] == 0)
                {
                    res[0] = arr[index][0];
                    res[1] = arr[index][1];
                } else
                {
                    res[2] += res[0] * res[1] * arr[index][1];
                    res[1] = arr[index][1];

                }
            }
        }
        System.out.println(res[2]);
    }
}