Problem Solving►UVa

UVa 442 - Matrix Chain Multiplication

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

Solution

遇到 ‘(‘ 和矩陣 就放進 stack 中，直到遇到 ‘)’ 後，
就開始依序做乘法並記錄 乘法數量和相乘結果，直到遇到 stack 中的 ‘(‘。
每完成一對 ‘(‘、’)’ 要將結果放回推疊中，並記得處理最後剩下的矩陣(最後會剩下一個矩陣)。

Code

UVa 442
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <cstdio>
#include <stack>
#define N 26
using namespace std;

struct Matrix
{
    int r, c;
    Matrix() : r(0), c(0) {}
    Matrix(int rr, int cc) : r(rr), c(cc) {}
    int get_num(Matrix &a) //乘法數量
    {
        if (c != a.r) //error
            return 0;
        return r * c * a.c;
    }
    Matrix get_res(Matrix &a) //相乘結果
    {
        return Matrix(r, a.c);
    }
} m[N];

int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out", "w", stdout);
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        char name;
        int row, col;
        getchar();
        scanf("%c%d%d", &name, &row, &col);
        m[name - 'A'] = (Matrix){row, col};
    }

    getchar();
    char str[100];
    while (fgets(str, 100, stdin))
    {
        Matrix R, L;
        int sum = 0;
        bool err = false;
        stack<Matrix> s;
        for (int i = 0; str[i] != '\n' && !err; ++i)
        {
            if (str[i] == '(') //用 0*0 來表示 '('
                s.emplace(0, 0);
            else if (str[i] == ')')
            {
                R = s.top();
                s.pop();
                if (R.r)
                {
                    while (true)
                    {
                        L = s.top();
                        s.pop();
                        if (!L.r)
                            break;

                        int tmp = L.get_num(R);
                        if (tmp)
                        {
                            R = L.get_res(R); //L*R
                            sum += tmp;
                        }
                        else
                        {
                            err = true;
                            break;
                        }
                    }
                }
                s.push(R); //拆完一對括號，最後乘完的結果
            }
            else
                s.push(m[str[i] - 'A']);
        }

        while (!err && s.size() > 1) //剩下的矩陣
        {
            R = s.top();
            s.pop();
            L = s.top();
            s.pop();
            int tmp = L.get_num(R);
            if (tmp)
            {
                s.push(L.get_res(R)); //L*R
                sum += tmp;
            }
            else
            {
                err = true;
                break;
            }
        }
        if (err)
            puts("error");
        else
            printf("%d\n", sum);
    }

    return 0;
}