[2017-10-04] Decision Tree

스몰 : https://www.acmicpc.net/problem/12643

라지 : https://www.acmicpc.net/problem/12644

풀이는 그냥 문제에서 시키는 거 따라서 구현하면 되는데 주어진 decision tree 파싱하는게 귀찮았던 문제. 파싱하고 나면 진짜 문제에서 시키는 거 그대로 따라서 확률 계산만 해주면 된다. 파싱도 사실 공백 기준으로 토큰만 잘 분리하면 트리 구성하는 것 자체는 그렇게 어렵지 않다.

	#include <stdio.h>
	#include <vector>
	#include <queue>
	#include <algorithm>
	#include <iostream>
	#include <string>
	#include <bitset>
	#include <map>
	#include <set>
	#include <tuple>
	#include <string.h>
	using namespace std;
	using i64 = long long int;
	using ii = pair<int, int>;
	using ii64 = pair<i64, i64>;
	struct Tree
	{
	float weight;
	~Tree()
	{
	if (left != nullptr)
	delete left;
	if (right != nullptr)
	delete right;
	}
	float prob(const set<string>& features)
	{
	float p = weight;
	if (left == nullptr && right == nullptr)
	return p;
	if (features.find(feature) == features.end())
	return p * right->prob(features);
	else
	return p * left->prob(features);
	}
	string feature;
	Tree* left;
	Tree* right;
	};
	Tree* makeTree(vector<string>& tokens, int& index)
	{
	Tree* res = new Tree();
	index++;
	res->weight = stof(tokens[index]);
	index++;
	if (tokens[index] == ")")
	{
	index++;
	return res;
	}
	res->feature = tokens[index];
	index ++;
	res->left = makeTree(tokens, index);
	res->right = makeTree(tokens, index);
	index++;
	return res;
	}
	void solve()
	{
	int l;
	scanf("%d\n", &l);
	vector<string> treeDesc(l);
	for (int i = 0; i < l; i++)
	getline(cin, treeDesc[i]);
	vector<string> tokens;
	for (auto& d : treeDesc)
	{
	d.push_back(' ');
	int prev = 0;
	for (int i = 0; i < d.size(); i++)
	{
	if (d[i] == ' ')
	{
	if (i > prev)
	{
	tokens.push_back(d.substr(prev, i - prev));
	}
	prev = i + 1;
	}
	else if (d[i] == '(' || d[i] == ')')
	{
	if (i > prev)
	{
	tokens.push_back(d.substr(prev, i - prev));
	}
	tokens.push_back(d.substr(i, 1));
	prev = i + 1;
	}
	}
	}
	int index = 0;
	auto tree = makeTree(tokens, index);
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
	string name;
	int a;
	cin >> name >> a;
	set<string> features;
	for (int i = 0; i < a; i++)
	{
	string feature;
	cin >> feature;
	features.insert(feature);
	}
	printf("%f\n", tree->prob(features));
	}
	delete tree;
	}
	int main()
	{
	int t;
	scanf("%d", &t);
	for (int i = 1; i <= t; i++)
	{
	printf("Case #%d:\n", i);
	solve();
	}
	return 0;
	}

view raw 12643-12644.cpp hosted with ❤ by GitHub