🔗 UVA-442 Matrix Chain Multiplication

tags: `堆疊(Stack)`

C++ 範例程式碼已於 UVA、瘋狂程設(CPE) 上測試通過。

題意

給定 $N$ 個矩陣的代號和大小，在之後若干行中，每行給定一個字串，字串中包含矩陣代號和括號，要求計算這個字串代表的矩陣乘法的總乘法次數，若無法相乘則輸出 $\rm{error}$ 。

思路：堆疊(Stack)

對於這種有計算順序的問題，可以使用堆疊來處理。若遇到字母，則將其對應的矩陣大小壓入堆疊；若遇到左括號，則將左括號壓入堆疊；若遇到右括號，則將堆疊中的矩陣依序相乘，直到遇到左括號，並將結果壓入堆疊。

由於給定的語法中確保了每組括號內都恰好包含兩個矩陣，或是兩個需要被事先計算的表達式，因此在遇到右括號時，堆疊中前三個元素一定是矩陣大小、矩陣大小、左括號。每次遇到右括號時，都只需要取出堆疊頂端的兩個元素，進行一次矩陣相乘，故左括號可以不存入堆疊。

複雜度分析

時間複雜度： $O(n)$ ，其中 $n$ 為輸入字串的長度。
空間複雜度： $O(n)$ ，存儲堆疊。

N = int(input())

mp = dict()
for _ in range(N):
    ch, m, n = input().split()
    mp[ch] = (int(m), int(n))

while True:
    try:
        line = input()
    except EOFError:
        break
    ans = 0
    st = []
    for ch in line:
        if ch in mp.keys():
            st.append(mp[ch])
        elif ch == "(":
            # st.append("(")
            pass
        elif ch == ")":
            x2, y2 = st.pop()
            x1, y1 = st.pop()
            if y1 != x2:
                ans = -1
                break
            ans += x1 * y1 * y2
            # st.pop() # pop "("
            st.append((x1, y2)) # new matrix size
    print(ans if ans != -1 else "error")

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, x, y, x1, y1;
    char ch;
    LL ans;

    map<char, pair<int, int>> mp;
    cin >> n;
    while (n--) {
        cin >> ch >> x >> y;
        mp[ch] = {x, y};
    }

    cin.ignore(1024, '\n');
    string line;
    while (getline(cin, line)) {
        ans = 0;
        stack<pair<int, int>> st;
        for (char ch : line) {
            if (mp.count(ch)) {
                st.push(mp[ch]);
            } else if (ch == ')') {
                x = st.top().first;
                y = st.top().second;
                st.pop();
                x1 = st.top().first;
                y1 = st.top().second;
                st.pop();
                if (y1 != x) {
                    ans = -1;
                    break;
                }
                ans += x1 * y1 * y;
                st.push({x1, y});  // new matrix
            }
        }
        cout << (ans != -1 ? to_string(ans) : "error") << endl;
    }
    return 0;
}