DT走过的路

在计算 $A\times B\times C$A×B×C 时，不同的运算顺序会带来不同的运算量。例如，$(A\times B)\times C$(A×B)×C 的运算量是 $a\times b\times c+a\times c\times d$a×b×c+a×c×d，而 $A\times (B\times C)$A×(B×C) 的运算量是 $b\times c\times d+a\times b\times d$b×c×d+a×b×d。

$$现在，对于给定的 $n$n 个矩阵的大小与运算式，请你计算出所需要的运算量。

输入描述：

$$第一行输入一个整数 $n(1\leqq n\leqq 15)$n(1≦n≦15) 代表矩阵的个数。
$$此后 $n$n 行，第 $i$i 行输入两个整数 $a_i$ai​ 和 $b_i(1\leqq a_i,b_i\leqq 100)$bi​(1≦ai​,bi​≦100) 代表第 $i$i 个矩阵的行数和列数。
$$最后一行输入一个长度为 $1\leqq \mathrm{l}\mathrm{e}\mathrm{n}(s)\leqq 10^3$1≦len(s)≦103 的字符串 $s$s 代表运算式。运算式中只包含前 $n$n 个大写字母与括号，第 $i$i 个大写字母对应输入的第 $i$i 个矩阵，括号成对出现，保证运算式合法且正确。

输出描述：

$$在一行上输出一个整数，代表计算需要的运算量。

示例1

输入：

3
50 10
10 20
20 5
(A(BC))

输出：

3500

示例2

输入：

3
50 10
10 20
20 5
((AB)C)

输出：

15000

主要需要处理入栈出栈问题。

思路：栈模拟运算

• 栈存矩阵信息 {row, col, cost}（行列 + 累计消耗）
• 遇到字母：把对应矩阵压栈
• 遇到 )：不断弹出栈顶两个矩阵相乘，合并成新矩阵，累加计算量，结果重新入栈
• ( 直接忽略

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    // Write your code here
    let ptr = 0;
    const n = await readline();
    //console.log(n);
    const mat = [];
    for (let i = 0; i < n; i++) {
        const [r, c] = (await readline()).split(" ").map(Number);
        mat.push({ r, c });
    }
    const expr = await readline();
    //console.log(mat)
    //console.log(expr)

    const stack = [];
    let total = 0;

    for (const ch of expr) {
        //console.log(ch)
        if(ch==='(') continue;
        if(ch===')'){
            const right = stack.pop();
            const left = stack.pop();
            //计算开销
            const cost = left.r * left.c * right.c;
            total+= cost;
            stack.push({r:left.r, c:right.c});
        }else{
            const idx = ch.charCodeAt() - "A".charCodeAt();
            //console.log(ch,"----",idx);
            stack.push(mat[idx]);
        }
    }
    console.log(total)
})();