紫书例题 11-1 UVa 12219 （表达式树）

这道题看了刘汝佳的代码真的是天秀，很值得学习。

具体看代码

#include<cstdio>

#include<iostream>

#include<cctype>

#include<map>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 51234;

struct node

{

	string s;

	int l, r;

	node(string s = "", int l = 0, int r = 0) : s(s), l(l), r(r) {}

	bool operator < (const node& rhs) const //map用设置优先级

	{

		if(s != rhs.s) return s < rhs.s;

		if(l != rhs.l) return l < rhs.l;

		return r < rhs.r;

	}

}s[MAXN];

map<node, int> g;

int done[MAXN], kase, cnt, k;

string str;

int solve()

{

	string cur;

	while(isalpha(str[k])) cur += str[k++]; //string很方便， 当作一个数直接加就ok了

	int id = ++cnt; //不知道要不要的时候先预留一个id， 然后不要cnt--， 很轻松就删除了。 

	node& t = s[id] = node(cur, 0, 0);  //变量名不想打那么长所以引用来偷懒

	if(str[k] == '(') //根据括号来拓展

	{

		k++;

		t.l = solve(); k++;

		t.r = solve(); k++;

	}

	if(g[t]) { cnt--; return g[t]; } //去掉重复

	return g[t] = id;

}

void print(int u)

{

	if(done[u] == kase) //省去了清零， 秀！

	{

		printf("%d", u);

		return;

	}

	done[u] = kase;

	cout << s[u].s; //学习这种输出方式，先输出根节点， 然后递归。

	if(s[u].l != 0)

	{

		putchar('(');

		print(s[u].l);

		putchar(',');

		print(s[u].r);

		putchar(')');

	}

}

int main()

{

	int T;

	scanf("%d", &T);

	for(kase = 1; kase <= T; kase++)

	{

		g.clear();

		cin >> str;

		k = cnt = 0;

		print(solve()); //两个函数一起写

		puts("");

	}

	return 0;

}

巴特西

紫书例题 11-1 UVa 12219 （表达式树）

最新文章

热门文章

巴特西

紫书 例题 11-1 UVa 12219 （表达式树）

最新文章

热门文章

紫书例题 11-1 UVa 12219 （表达式树）