P2395 题解
P2395 题解
题目链接：P2395 BBCode转换Markdown
不算太大的字符串模拟题，是把 BBCode 转换成 Markdown。
目前还没有转换 Token 做的题解。
既然是一种语言转另一种语言，也类似于一个编译器，模拟编译器常见的思路就是转换 Token。
Token 就是代码中的一个元素，比如这道题中就有两种 Token：
- 标签：一对方括号内一个合法的 BBCode 命令
- 文本：除标签外的其他内容
用结构体存储 Token，存类别、文字或标签名、参数。
Step 1
先把 BBCode 转成 Token。
为了方便转换，这里先忽略 [quote][/quote] 中的标签按文本处理的特殊情况，都按标签处理，之后特判。
[url] 和 [img] 要特殊处理，另外存储“参数”（= 之后 ] 之前的内容）
Step 2
检查 BBCode 是否合法。
用栈模拟，遇到开始标签就把标签名压入栈，遇到结束标签就弹出栈顶。如果弹出时发现栈为空，或者弹出的标签与结束标签不匹配，就是 Match Error，如果到最后栈不为空，就是 Unclosed Mark。
特判 [quote]：遇到 [quote] 就压栈后直接扫到 [/quote] 为止（数据保证 [quote] 标签不会出现错误），然后直接弹出。
Step 3
转换 Markdown。
遍历 Token，标签基本都可以替换，如 [h1] 换成 #，[/h1] 换成 # 等。
带参数的标签（[url 和 [img]），由于 Markdown 的参数是后置的，要让结束标签知道匹配的是哪个，所以还要用一个栈，遇到带参数的开始标签就把参数压入栈，遇到对应的结束标签就弹出参数输出。
特判 [quote]：如果遇到的 [quote] 不是整个程序中的第一个 Token，而且它的前一个 Token 结尾不是换行符，就在前面补一个换行，然后把一对 [quote] 之间的所有 Token 转换成纯文本，去掉前导、后缀换行之后，每换一行加 >，开头也要加。
还有一点题目没说清楚，根据常识，[/quote] 之后要补一个换行。
代码
由于没有给定范围，使用了大量 STL。
#include <cstdio>
#include <string>
#include <vector>
#include <stack>
#define fprintf(...)
using std::string;
using std::vector;
using std::stack;
string code;
unsigned cl;
enum TokType{TAG,TEXT};
struct Token{
TokType t;
string s;
string s2;
Token(){}
Token(const TokType &_t,const string &_s):
t(_t),s(_s),s2(""){}
Token(const TokType &_t,const string &_s,const string &_s2):
t(_t),s(_s),s2(_s2){}
};
vector<Token> tk;
void readall(){
char c=getchar();
while(~c){
if(c!='\r'){
code+=c;
}
c=getchar();
}
}
inline void ps(const string &s){
fputs(s.c_str(),stdout);
}
bool istag(string s){
string s4;
if(s.size()>4){
s4=s.substr(0,4);
}
else{
s4="";
}
if(
s=="h1"||s=="/h1"||
s=="h2"||s=="/h2"||
s=="i"||s=="/i"||
s=="b"||s=="/b"||
s4=="url="||s=="/url"||
s4=="img="||s=="/img"||
s=="quote"||s=="/quote"||
0){
return 1;
}
return 0;
}
void divide(){
char c;
string buf;
cl=code.size();
for(unsigned i=0;i<cl;){
c=code[i];
if(c=='['){
buf="";
for(++i;code[i]!=']';++i){
buf+=code[i];
}
if(istag(buf)){
if(buf[3]=='='){
tk.push_back(Token(TAG,buf.substr(0,3),buf.substr(4)));
}
else{
tk.push_back(Token(TAG,buf));
}
}
else{
tk.push_back(Token(TEXT,string()+"["+buf+"]"));
}
++i;
}
else{
buf="";
for(;code[i]!='['&&i<cl;++i){
buf+=code[i];
}
tk.push_back(Token(TEXT,buf));
}
}
}
int check(){
static stack<string> stk;
for(unsigned i=0;i<tk.size();++i){
if(tk[i].t==TAG){
if(tk[i].s[0]=='/'){
if(stk.empty()){
puts("Match Error");
return 1;
}
if(tk[i].s.substr(1)!=stk.top()){
puts("Match Error");
return 2;
}
stk.pop();
}
else{
stk.push(tk[i].s);
if(tk[i].s=="quote"){
for(++i;tk[i].s!="/quote";++i);
stk.pop();
}
}
}
}
if(!stk.empty()){
ps("Unc");
puts("losed Mark");
return 3;
}
return 0;
}
string plain(const Token &t){
string r="";
if(t.t==TEXT){
r+=t.s;
}
else{
r+='[';
r+=t.s;
if(t.s2.size()){
r+='=';
r+=t.s2;
}
r+=']';
}
return r;
}
void quote(const string &t){
unsigned i=0,s=t.size();
while(t[i]=='\n'){
++i;
}
while(t[s-1]=='\n'){
--s;
}
ps("> ");
for(;i<s;++i){
putchar(t[i]);
if(t[i]=='\n'){
ps("> ");
}
}
puts("");
}
void trans(){
static stack<string> stk;
for(unsigned i=0;i<tk.size();++i){
if(tk[i].t==TAG){
if(tk[i].s=="h1"){
ps("# ");
}
else if(tk[i].s=="/h1"){
ps(" #");
}
else if(tk[i].s=="h2"){
ps("## ");
}
else if(tk[i].s=="/h2"){
ps(" ##");
}
else if(tk[i].s=="i"){
ps("*");
}
else if(tk[i].s=="/i"){
ps("*");
}
else if(tk[i].s=="b"){
ps("__");
}
else if(tk[i].s=="/b"){
ps("__");
}
else if(tk[i].s=="url"){
ps("[");
stk.push(tk[i].s2);
}
else if(tk[i].s=="/url"){
ps("](");
ps(stk.top());
putchar(')');
stk.pop();
}
else if(tk[i].s=="img"){
ps("![");
stk.push(tk[i].s2);
}
else if(tk[i].s=="/img"){
ps("](");
ps(stk.top());
putchar(')');
stk.pop();
}
else if(tk[i].s=="quote"){
string t="";
int f=666666;
if(i){
if(tk[i-1].t==TEXT&&tk[i-1].s[tk[i-1].s.size()-1]=='\n'){
f=0;
}
}
else{
f=0;
}
if(f){
puts("");
}
for(++i;!(tk[i].t==TAG&&tk[i].s=="/quote");++i){
t+=plain(tk[i]);
}
quote(t);
}
}
else{
ps(tk[i].s);
}
}
}
int main(){
readall();
divide();
if(check()){
return 0;
}
trans();
return 0;
}