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

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

public class Main {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner in = new Scanner(System.in);
    while (in.hasNext()) {
        int num = in.nextInt();
        int a[][] = new int[num][2];
        for (int i = 0; i < num; i++) {
            a[i][0] = in.nextInt();
            a[i][1] = in.nextInt();
        }

        String s = in.next();

        int res = calc(s, a);
        System.out.println(res);


    }
}

public static int calc(String in, int[][] a) {
    char[] r = in.toCharArray();
    Stack<Integer> q = new Stack<Integer>();
    int sum = 0;
    for (int i = 0; i < r.length; i++) {
        if (r[i] == '(') {
            continue;
        } else if (r[i] == ')') {
            int a1 = q.pop();
            int a2 = q.pop();
            int a3 = q.pop();
            int a4 = q.pop();

            sum += a1 * a2 * a4;
            q.push(a4);
            q.push(a1);
        } else {
            int index = r[i] - 'A';
            q.push(a[index][0]);
            q.push(a[index][1]);
        }


    }

    //扫尾
    if (q.isEmpty() == false && q.size() == 4) {
        int a1 = q.pop();
        int a2 = q.pop();
        int a3 = q.pop();
        int a4 = q.pop();

        sum += a1 * a2 * a4;
    }
    return sum;

}

}

import java.util.Stack;

public class Main {

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        Scanner in = new Scanner(System.in);

        while (in.hasNext()) {

            int num = in.nextInt();

            int a[][] = new int[num][2];

            for (int i = 0; i < num; i++) {

                a[i][0] = in.nextInt();

                a[i][1] = in.nextInt();

            }

            String s = in.next();

            int res = calc(s, a);

            System.out.println(res);

        }

    }

    public static int calc(String in, int[][] a) {

        char[] r = in.toCharArray();

        Stack<Integer> q = new Stack<Integer>();

        int sum = 0;

        for (int i = 0; i < r.length; i++) {

            if (r[i] == '(') {

                continue;

            } else if (r[i] == ')') {

                int a1 = q.pop();

                int a2 = q.pop();

                int a3 = q.pop();

                int a4 = q.pop();

                sum += a1 * a2 * a4;

                q.push(a4);

                q.push(a1);

            } else {

                int index = r[i] - 'A';

                q.push(a[index][0]);

                q.push(a[index][1]);

            }

        }

        //扫尾

        if (q.isEmpty() == false && q.size() == 4) {

            int a1 = q.pop();

            int a2 = q.pop();

            int a3 = q.pop();

            int a4 = q.pop();

            sum += a1 * a2 * a4;

        }

        return sum;

    }

}