题目链接

https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=3371&mosmsg=Submission+received+with+ID+26550245

使用 \((hash,left,right)\) 表示一个子树，存入 \(map\) 中，就可以判断一个子树是否出现过

剩下的就是字符串处理的部分，利用字符串指针递归处理，很巧妙

\(s.c_str()\) 返回指向字符串 \(s\) 的指针

\(vis[i] == kase\) 可以避免 \(memset(vis, 0, sizeof(vis))\)

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

const int maxn = 60000;

int T, kase, cnt;
char expr[maxn * 5], *p;
int done[maxn];

struct Node{
	string s;
	int hash, left, right;
	
	bool operator < (const Node& x) const{
		if(hash != x.hash) return hash < x.hash;
		if(left != x.left) return left < x.left;
		return right < x.right;
	} 
}node[maxn];

map<Node, int> mp;

int parse(){
	int id = ++cnt;
	Node& u = node[id];
	u.left = u.right = -1;
	u.s = "";
	u.hash = 0;
	
	while(isalpha(*p)){
		u.hash = u.hash * 27 + *p - ‘a‘ + 1;
		u.s.push_back(*p);
		p++;
	}
	
	if(*p == ‘(‘){
		p++; u.left = parse(); p++; u.right = parse(); p++;
	}
	
	if(mp.count(u) != 0){
		cnt--;
		return mp[u];
	}
	return mp[u] = id;
}

void print(int v){
	if(done[v] == kase){
		printf("%d", v);
	} else{
		done[v] = kase;
		printf("%s", node[v].s.c_str());
		
		if(node[v].left != -1){
			putchar(‘(‘);
			print(node[v].left);
			putchar(‘,‘);
			print(node[v].right);
			putchar(‘)‘);			
		}
	}
}

ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < ‘0‘ || ch > ‘9‘){ if(ch == ‘-‘) f = -1; ch = getchar(); } while(ch >= ‘0‘ && ch <= ‘9‘){ s = s * 10 + ch - ‘0‘; ch = getchar(); } return s * f; }

int main(){
	scanf("%d", &T);
	for(kase = 1 ; kase <= T ; ++kase){
		scanf("%s", expr);
		p = expr;
		
		cnt = 0;
		mp.clear();
		
		print(parse());
		putchar(‘\n‘);
	}
	return 0;
}

UVa 12219 Common Subexpression Elimination (杂)