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

本题求解多个矩阵相乘所用到的乘法的次数，由于存在括号所以要考虑优先级问题，被括号包起来的矩阵优先级更高，优先做乘法，若没有被括号包起来，则遵从从左到右的顺序。
运算存在优先级问题可以考虑用栈，另外本题中存在矩阵的映射问题，所以用到了unordered_map。
从后往前遍历字符串，若是字母或右括号就将其入栈，若为左括号就将栈中保留的元素出栈进行乘法运算,知道栈顶为右括号。

#include<iostream>
#include<string>
#include<unordered_map>
#include<vector>
#include<stack>
using namespace std;

int getMultipCount(const string& str,unordered_map<char, vector<int>>& um);

int main(){
    int n;
    while(cin >> n){
        int row = 0;
        int col = 0;
        unordered_map<char, vector<int>> um;
        for(int i = 0; i < n; ++i){
            cin >> row >> col;
            um['A' + i] = {row, col};
        }
        string str;
        cin >> str;
        cout << getMultipCount(str, um) << endl;
    }
    return 0;
}

int getMultipCount(const string& str,unordered_map<char, vector<int>>& um){
    stack<char> stk;
    int res = 0;
    for(int i = str.size() - 1; i >= 0; --i){
        if(str[i] != '('){
            stk.push(str[i]);
        }else{
            char val1 = stk.top();
            stk.pop();
            while(stk.top() != ')'){
                char val2 = stk.top();
                stk.pop();
                res = res + um[val1][0] * um[val1][1] * um[val2][1];
                um[val1][1] = um[val2][1];
            }
            stk.pop();
            stk.push(val1);
        }
    }
    return res;
}