526互联

P2395 BBCode转换Markdown

发布时间 2023-12-30 22:10:59作者: Hanx16Msgr

BBCode转换Markdown

Luogu P2395

题面太长不贴了。

Solution

不算大的大模拟。

推荐模块化的写，每个功能都开一个函数来实现。同时推荐使用 enum 来代替代码中的数字，增强可读性。

不妨分两步来做，第一步是校验输入是否合法，第二步是将输入转换成对应的输出。

先来做第一步。因为保证了标签一定是完整的并且在非引用的部分出现的文字不会含有标签所含有的字符，所以我们可以简单地使用 [] 来确定一个标签，用是否含有 / 来确定标签是开头还是结尾。

所以我们得到了一个函数来区分标签的类别以及种类：

get_rag 
enum {open, closed};

pair<string, short> get_tag(size_t p, const string& content) {
    assert(content[p] == '[');
    size_t q = p + 1;
    while (content[q] != ']' && content[q] != '=') ++q;
    size_t start_pos = p + 1 + (content[p+1] == '/');
    string tag = '[' + content.substr(start_pos, q - start_pos) + ']';
    short type = content[p+1] == '/' ? closed : open;
    return make_pair(tag, type);
}

同时实现一个辅助函数，用于将当前的指针从当前标签的开头移动到当前标签的结尾：

move_to_tag_end 
void move_to_tag_end(size_t &p, const string& content) {
    while (p < content.length() && content[p] != ']') ++p;
}

然后就可以写出校验输入是否合法的函数：

check_format 
void check_format() {
    init_args();
    size_t ptr = 0;
    while (ptr < content.length()) {
        if (content[ptr] == '[') {
            auto tag = get_tag(ptr, content);
            if (tag.first == "[quote]") {
                if (tag.second == open) isQuoting = true;
                else {
                    if (!isQuoting) match_error();
                    isQuoting = false;
                }
            }
            if (!isQuoting && tag.first != "[quote]") {
                if (tag.second == open)
                    opt_stack.push(tag.first);
                else {
                    if (opt_stack.top() != tag.first)
                        match_error();
                    opt_stack.pop();
                }
            }
            move_to_tag_end(ptr, content);
        }
        ++ptr;
    }
    if (!opt_stack.empty())
        unclosed_mark();
}

对于标签的匹配问题，直接使用一个栈来解决。注意匹配标签时需要判断当前标签是否在引用块内。

校验完是否合法后就可以开始答案的生成了。首先 [h1]、[h2]、[i]、[b] 是好做的，可以直接替换。

考虑 [quote] 的处理，不难发现只需要一直向后找到第一个 [/quote] 并把这一段的内容单独提取出来处理即可。所以我们写一个函数来处理 [quote] 内的东西，将开头和结尾多余的间隔符删除并对所有的换行添加 > 标识：

get_quote_block 

string get_quote_block(const string& quote_buf) {
    string result = "> ";
    size_t start_pos = 0, end_pos = quote_buf.length() - 1;
    while (start_pos < quote_buf.length() && isspace(quote_buf[start_pos])) ++start_pos;
    while (end_pos >= 0 && isspace(quote_buf[end_pos])) --end_pos;
    for (size_t i = start_pos; i <= end_pos; ++i) {
        char c = quote_buf[i];
        result += c;
        if (c == '\n') result += "> ";
    }
    return result + '\n';
}

然后就是比较麻烦的 [img] 和 [url] 了。因为这两个标签对应的文字描述部分是可以嵌套其他的标签的。不妨先写一个函数用来提取这两种标签的链接和描述部分：

get_url 

pair<string, string> get_url(size_t p, const string& content, const string& type) {
    while (content[p] != '=') ++p;
    size_t q = p;
    while (content[q] != ']') ++q;
    string url = content.substr(p + 1, q - p - 1);
    size_t o = q, cnt = 1;
    while (cnt) {
        ++o;
        if (content[o] == '[') {
            auto tag = get_tag(o, content);
            if (tag.first == type) {
                if (tag.second == open) ++cnt;
                else --cnt;
            }
        }
    }
    string word = content.substr(q + 1, o - q - 1);
    return make_pair(url, word);
}

注意描述的部分应当使用类似括号匹配的方式，因为不能够在第一个 [/img] 或 [/url] 处就停止，而是应当找到当前标签对应的闭合标签。

顺带写出一个将指针移动到当前标签结尾的函数：

move_to_url_end 
void move_to_url_end(size_t& p, const string& content, const string& type) {
    size_t cnt = 1;
    move_to_tag_end(p, content);
    while (cnt) {
        ++p;
        if (content[p] == '[') {
            auto tag = get_tag(p, content);
            if (tag.first == type) {
                if (tag.second == open) ++cnt;
                else --cnt;
            }
        }
    }
}

这时候应当处理 [img] 和 [url] 标签内部文字描述的标签嵌套问题。会发现这部分的处理方式跟原来一整个字符串的处理方式一样，所以直接递归处理即可。

从而得到生成答案的函数：

get_result 
string get_result(const string& content) {
    init_args();
    size_t ptr = 0;
    string quote_buf = "", result = "";
    while (ptr < content.length()) {
        if (content[ptr] == '[') {
            auto tag = get_tag(ptr, content);
            if (tag.first != "[quote]" && isQuoting) {
                quote_buf += '[', ++ptr;
                continue;
            } else if (tag.first == "[quote]") {
                if (tag.second == open) {
                    if (isQuoting)
                        quote_buf += "[quote]";
                    isQuoting = true;
                } else {
                    isQuoting = false;
                    if (!result.empty() && result.back() != '\n')
                        result += '\n';
                    result += get_quote_block(quote_buf);
                    quote_buf = "";
                }
            } else {
                if (tag.first == "[h1]") {
                    if (tag.second == open) result += "# ";
                    else result += " #";
                }
                if (tag.first == "[h2]") {
                    if (tag.second == open) result += "## ";
                    else result += " ##";
                }
                if (tag.first == "[i]")
                    result += "*";
                if (tag.first == "[b]")
                    result += "__";
                if (tag.first == "[img]" && tag.second == open) {
                    auto info = get_url(ptr, content, tag.first);
                    result += "![" + get_result(info.second) + "](" + info.first + ")";
                    move_to_url_end(ptr, content, tag.first);
                }
                if (tag.first == "[url]" && tag.second == open) {
                    auto info = get_url(ptr, content, tag.first);
                    result += "[" + get_result(info.second) + "](" + info.first + ")";
                    move_to_url_end(ptr, content, tag.first);
                }
            }
            move_to_tag_end(ptr, content);
        } else {
            if (isQuoting) quote_buf += content[ptr];
            else result += content[ptr];
        }
        ++ptr;
    }
    return result;
}

然后把所有函数综合到一起就得到了 AC 代码：

Code 
#include <bits/stdc++.h>

using namespace std;

string content;

void input_content() {
    string buf;
    while (getline(cin, buf)) content += buf + '\n';
}

void match_error() {
    cout << "Match Error\n";
    exit(0);
}

void unclosed_mark() {
    cout << "Unclosed Mark\n";
    exit(0);
}

stack<string> opt_stack;
bool isQuoting;

void init_args() {
    isQuoting = false;
}

enum {open, closed};

pair<string, short> get_tag(size_t p, const string& content) {
    assert(content[p] == '[');
    size_t q = p + 1;
    while (content[q] != ']' && content[q] != '=') ++q;
    size_t start_pos = p + 1 + (content[p+1] == '/');
    string tag = '[' + content.substr(start_pos, q - start_pos) + ']';
    short type = content[p+1] == '/' ? closed : open;
    return make_pair(tag, type);
}

void move_to_tag_end(size_t &p, const string& content) {
    while (p < content.length() && content[p] != ']') ++p;
}

void check_format() {
    init_args();
    size_t ptr = 0;
    while (ptr < content.length()) {
        if (content[ptr] == '[') {
            auto tag = get_tag(ptr, content);
            if (tag.first == "[quote]") {
                if (tag.second == open) isQuoting = true;
                else {
                    if (!isQuoting) match_error();
                    isQuoting = false;
                }
            }
            if (!isQuoting && tag.first != "[quote]") {
                if (tag.second == open)
                    opt_stack.push(tag.first);
                else {
                    if (opt_stack.top() != tag.first)
                        match_error();
                    opt_stack.pop();
                }
            }
            move_to_tag_end(ptr, content);
        }
        ++ptr;
    }
    if (!opt_stack.empty())
        unclosed_mark();
}

pair<string, string> get_url(size_t p, const string& content, const string& type) {
    while (content[p] != '=') ++p;
    size_t q = p;
    while (content[q] != ']') ++q;
    string url = content.substr(p + 1, q - p - 1);
    size_t o = q, cnt = 1;
    while (cnt) {
        ++o;
        if (content[o] == '[') {
            auto tag = get_tag(o, content);
            if (tag.first == type) {
                if (tag.second == open) ++cnt;
                else --cnt;
            }
        }
    }
    string word = content.substr(q + 1, o - q - 1);
    return make_pair(url, word);
}

void move_to_url_end(size_t& p, const string& content, const string& type) {
    size_t cnt = 1;
    move_to_tag_end(p, content);
    while (cnt) {
        ++p;
        if (content[p] == '[') {
            auto tag = get_tag(p, content);
            if (tag.first == type) {
                if (tag.second == open) ++cnt;
                else --cnt;
            }
        }
    }
}

string get_quote_block(const string& quote_buf) {
    string result = "> ";
    size_t start_pos = 0, end_pos = quote_buf.length() - 1;
    while (start_pos < quote_buf.length() && isspace(quote_buf[start_pos])) ++start_pos;
    while (end_pos >= 0 && isspace(quote_buf[end_pos])) --end_pos;
    for (size_t i = start_pos; i <= end_pos; ++i) {
        char c = quote_buf[i];
        result += c;
        if (c == '\n') result += "> ";
    }
    return result + '\n';
}

string get_result(const string& content) {
    init_args();
    size_t ptr = 0;
    string quote_buf = "", result = "";
    while (ptr < content.length()) {
        if (content[ptr] == '[') {
            auto tag = get_tag(ptr, content);
            if (tag.first != "[quote]" && isQuoting) {
                quote_buf += '[', ++ptr;
                continue;
            } else if (tag.first == "[quote]") {
                if (tag.second == open) {
                    if (isQuoting)
                        quote_buf += "[quote]";
                    isQuoting = true;
                } else {
                    isQuoting = false;
                    if (!result.empty() && result.back() != '\n')
                        result += '\n';
                    result += get_quote_block(quote_buf);
                    quote_buf = "";
                }
            } else {
                if (tag.first == "[h1]") {
                    if (tag.second == open) result += "# ";
                    else result += " #";
                }
                if (tag.first == "[h2]") {
                    if (tag.second == open) result += "## ";
                    else result += " ##";
                }
                if (tag.first == "[i]")
                    result += "*";
                if (tag.first == "[b]")
                    result += "__";
                if (tag.first == "[img]" && tag.second == open) {
                    auto info = get_url(ptr, content, tag.first);
                    result += "![" + get_result(info.second) + "](" + info.first + ")";
                    move_to_url_end(ptr, content, tag.first);
                }
                if (tag.first == "[url]" && tag.second == open) {
                    auto info = get_url(ptr, content, tag.first);
                    result += "[" + get_result(info.second) + "](" + info.first + ")";
                    move_to_url_end(ptr, content, tag.first);
                }
            }
            move_to_tag_end(ptr, content);
        } else {
            if (isQuoting) quote_buf += content[ptr];
            else result += content[ptr];
        }
        ++ptr;
    }
    return result;
}

signed main() {
    input_content();
    check_format();
    cout << get_result(content);
}

一些细节：题目中输入的规模是 \(10^6\) 级别的，因此函数传参务必使用引用 &，不然每次调用函数都会复制一遍原字符串，带来很大的开销，导致 TLE on 2, 8。