#include <iostream>
#include <string>
using namespace std;

struct Node
{
	string value;
	Node *parent;
	Node *first;
	Node *next;

	Node(const string &v, Node *p = nullptr, Node *f = nullptr, Node *n = nullptr):
			value(v), parent(p), first(f), next(n) {}
};

class Arbre
{
// PARTIE PRIVÉE
private:
	Node *root; // Racine de l'arbre

	// Vider [récursivement] l'arbre
	void clear(Node *node)
	{
		if(node != nullptr)
		{
			for(auto ptr = node; ptr != nullptr; ptr = ptr->next)
				clear(ptr->first);
			delete node; node = nullptr;
		}
	} // clear()

	// Fonction pour ignorer espaces, tabulations, retours à la ligne
	// et retours chariot
	void skipSpaces(const string &s, size_t &i)
	{
		while(i < s.size() && (s[i] == ' ' || s[i] == '\t' || s[i] == '\n'
				|| s[i] == '\r'))
			i++;
	} // skipSpaces()

	// Analyse de token
	string parseToken(const string &s, size_t &i)
	{
		skipSpaces(s, i);
		string tok;
		while(i < s.size() && !(s[i] == '(' || s[i] == ')' || s[i] == ' '
				|| s[i] == '\t' || s[i] == '\n' || s[i] == '\r'))
		{
			tok.push_back(s[i]);
			i++;
		}
		return tok;
	} // parseToken()

	// Parcours récursif d'un nœud
	Node *parseNode(const string &s, size_t &i)
	{
		skipSpaces(s, i);

		if(i >= s.size() || s[i] != '(') return nullptr;
			i++;  // Sauter '('

		string val = parseToken(s, i); // Valeur du nœud
		auto node = new Node(val);

		while(true) // Tant qu'il y a des enfants : jusqu'à ')'
		{
			skipSpaces(s, i);
			if(i >= s.size()) break;

			if(s[i] == '(')
			{
				Node *child = parseNode(s, i);
				if(child) // ajouter un enfant
				{
					if(node->first == nullptr)
					{
						// node n'a pas encore d'enfant
						node->first = child;
					}
					else // node a un ou plusieurs enfants
					{
						auto ptr = node->first;
						while(ptr->next != nullptr)
							ptr = ptr->next;
						ptr->next = child;
					}
					child->parent = node;
				}
			}
			else if(s[i] == ')')
			{
				i++;  // Sauter ')'
				break;
			}
			else
			{
				i++; // token non prévu, on ignore
			}
		}

		return node;
	} // parseNode()

	// Nombre de nœuds
	int nodeCountHelp(const Node *node) const
	{
		if(node == nullptr) return 0;

		int ns = 0;
		for(auto ptr = node; ptr != nullptr; ptr = ptr->next)
			ns += 1 + nodeCountHelp(ptr->first);

		return ns;
	} // nodeCountHelp()

	// Affichage visuel
	void printTreeHelp(const Node *node, const int depth = 0) const
	{
		if(node == nullptr) return;
		cout << string(depth * 2, ' ') << node->value << "\n";
		for(auto ptr = node->first; ptr != nullptr; ptr = ptr->next)
		{
			printTreeHelp(ptr, depth + 1);
		}
	} // printTree()

	// Parcours infixe
	void prefixHelp(const Node *node) const
	{
		if(node != nullptr)
		{
			cout << node->value << ' ';
			for(auto ptr = node->first; ptr != nullptr; ptr = ptr->next)
				prefixHelp(ptr);
		}
	} // prefixHelp()

	// Parcours postfixe
	void postfixHelp(const Node *node) const
	{
		if(node != nullptr)
		{
			for(auto ptr = node->first; ptr != nullptr; ptr = ptr->next)
				postfixHelp(ptr);
			cout << node->value << ' ';
		}
	} // postfixHelp()

	// Parcours préfixe parenthésé (ou en profondeur)
	void printHelp(const Node *node) const
	{
		if(node != nullptr)
		{
			cout << '(' << ' ';
			cout << node->value << ' ';
			for(auto ptr = node->first; ptr != nullptr; ptr = ptr->next)
				printHelp(ptr);
			cout << ')' << ' ';
		}
	} // printHelp()

	Node *findHelp(Node *node, const string &target,
			int currentLevel, int &foundLevel) const
	{

		// À COMPLÉTER

	} // findHelp()

// PARTIE PUBLIQUE
public:
	Arbre(): root(nullptr) {} // constructeur par défaut

	Arbre(const string &expr) // constructeur paramétré
	{
		size_t idx = 0;
		root = parseNode(expr, idx);
	}

	// Constructeur paramétré
	Arbre(Node *rt): root(rt) {}

	// Destructeur
	~Arbre() { clear(root); }

	// Nombre de nœuds de l'arbre
	int nodeCount() const { return nodeCountHelp(root); }

	void printTree() const { printTreeHelp(root); }

	// Affichage préfixe parenthésé
	void print() const
	{
		printHelp(root);
		cout << '\n';
	}

	// Affichage préfixe
	void prefix() const
	{
		prefixHelp(root);
		cout << '\n';
	}

	// Affichage postfixe
	void postfix() const
	{
		postfixHelp(root);
		cout << '\n';
	}

	// Deux nœuds sont cousins s'ils sont au même niveau avec des parents distincts
	bool areCousins(const string &x, const string &y) const
	{

		// À COMPLÉTER à l'aide de findHelp()

	} // areCousins()
}; // class Arbre