正经题解｜logo的语言

【算法分析】

先去掉字符串中的空格。$dfs(l,r)$ 表示 $l \sim r$ 字符串求出的值。每次只处理最左边的一个操作。只可能是 $FD、BK、REPEAT$ 中的一种。特别要注意的是 $REPEAT$ 要找到对应的重复的段。

【参考代码】

#include <bits/stdc++.h>
using namespace std;

string s;
int dfs(int l, int r) {
    if (l > r) return 0;
    string t;
    while (l <= r && s[l] >= 'A' && s[l] <= 'Z') {
        t += s[l];
        l++;
    }
    int num = 0;
    while (l <= r && s[l] >= '0' && s[l] <= '9') {
        num = num * 10 + s[l] - '0';
        l++;
    }
    if (t == "FD") {
        return num + dfs(l, r);
    }
    else if (t == "BK") {
        return -num + dfs(l, r);
    }
    else {
        int ans = 0;
        for (int i = l; i <= r; i++) {
            if (s[i] == '[') ans++;
            else if (s[i] == ']') ans--;
            if (ans == 0) return num * dfs(l + 1, i - 1) + dfs(i + 1, r);
        }
    }
}
int main() {
    string str;
    while (cin >> str) {
        s += str;
    }
    cout << abs(dfs(0, s.size() - 1));
    return 0;
}

【时间复杂度】

$O(|S|*|S|)$

【预计得分】

$100pts$