#include<iostream>
#include<string.h>
#include<vector>
using namespace std;

struct LNode                     //tagnodelist
{
	char key;
	LNode *pNext;
};

struct TNode
{
	char key;
	TNode *pLeft;
	TNode *pRight;
	TNode *pNext;
};

struct Stack
{
	LNode *pHead;
	LNode *pTail;
};

struct Queue
{
	LNode *pHead;
	LNode *pTail;
};

struct StackTree
{
	TNode *pHead;
	TNode *pTail;
};

LNode* CreateNode(char x)
{
	LNode *p= new LNode;
	if (p == NULL);
	else
	{
		p->key = x;
		p->pNext = NULL;
	}
	return p;
}

TNode* CreateTNode(char x)
{
	TNode *p = new TNode;
	p->key = x;
	p->pLeft = p->pRight = NULL;
	p->pNext = NULL;
	return p;
}

void CreateStack(Stack &S)
{
	S.pHead = NULL;
	S.pTail = NULL;
}

void CreateQueue(Queue &Q)
{
	Q.pHead = NULL;
	Q.pTail = NULL;
}

void CreateStackTree(StackTree &ST)
{
	ST.pHead = NULL;
	ST.pTail = NULL;
}

void PushStack(Stack &S, char x)
{
	LNode *p = CreateNode(x);
	if (S.pHead == NULL)
	{
		S.pHead = p;
		S.pTail = S.pHead;
	}
	else
	{
		p->pNext = S.pHead;
		S.pHead = p;
	}
}

char PopStack(Stack &S)
{
	char a = S.pHead->key;
	LNode *p = S.pHead;
	if (S.pHead == S.pTail)
	{
		delete p;
		p = NULL;
		S.pHead = S.pTail = NULL;
	}
	else
	{
		S.pHead = S.pHead->pNext;
		delete p;
		p = NULL;
	}
	return a;
}

void EnQueue(Queue &Q, char x)
{
	LNode *p = CreateNode(x);
	if (Q.pHead == NULL)
	{
		Q.pHead = p;
		Q.pTail = Q.pHead;
	}
	else
	{
		Q.pTail->pNext = p;
		Q.pTail = p;
	}
}

char DeQueue(Queue &Q)
{
	char a = Q.pHead->key;
	LNode *p = Q.pHead;
	if (Q.pHead == Q.pTail)
	{
		delete p;
		p = NULL;
		Q.pHead = Q.pTail = NULL;
	}
	else
	{
		Q.pHead = Q.pHead->pNext;
		delete p;
		p = NULL;
	}
	return a;
}

int Pritoty(char x)
{
	if (x == '*' || x == '/')
		return 2;
	else if (x == '+' || x == '-')
		return 1;
	else
		return 0;
}

int Operator(char x)
{

	if (Pritoty(x) == 0)
	{
		if (x == '(' || x == ')')
			return 0;
		else
			return 1;
	}
	else
		return 2;
}

void InFixToPostFix(vector<char> a, Queue &Q)
{
	Stack S;
	CreateStack(S);
	for (int i = 0; i < a.size(); i++)
	{
		if (Operator(a[i]) == 1)
		{
			EnQueue(Q, a[i]);
		}
		else if (Operator(a[i]) == 2)
		{
			if (S.pHead != NULL)
			{
				while (Pritoty(a[i]) <= Pritoty(S.pHead->key))
				{
					char t = PopStack(S);
					EnQueue(Q, t);
					if (S.pHead == NULL)
						break;
				}
			}
			PushStack(S, a[i]);
		}
		else if (Operator(a[i]) == 0)
		{
			if (a[i] == '(')
				PushStack(S, a[i]);
			else
			{
				while (S.pHead->key != '(')
				{
					char t = PopStack(S);
					EnQueue(Q, t);
				}
				PopStack(S);
			}
		}

	}
	while (S.pHead != NULL)
	{
		char t = PopStack(S);
		EnQueue(Q, t);
	}
}

void PushStackTree(StackTree &ST, TNode *TN)
{
	if (ST.pHead == NULL)
	{
		ST.pHead = TN;
		ST.pTail = ST.pHead;
	}
	else
	{
		TN->pNext = ST.pHead;
		ST.pHead = TN;
	}
}

TNode* PopStackTree(StackTree &ST)
{
	if (ST.pHead == NULL)
	{
		return NULL;
	}
	else if (ST.pHead == ST.pTail)
	{
		return ST.pHead;
	}

	TNode *p = ST.pHead;
	ST.pHead = p->pNext;
	return p;
}

void CreateTree(StackTree &ST, Queue Q)
{
	LNode *p = Q.pHead;
	while (p != NULL)
	{
		if (Operator(p->key) == 1)
		{
			PushStackTree(ST, CreateTNode(p->key));
		}
		else if (Operator(p->key) == 2)
		{
			TNode *A = CreateTNode(p->key);
			A->pRight = ST.pHead;
			PopStackTree(ST);
			A->pLeft = ST.pHead;
			PopStackTree(ST);
			PushStackTree(ST, A);
		}
		p = p->pNext;
	}
}

void LRN(TNode *T)
{
	if (T != NULL)
	{
		LRN(T->pLeft);
		LRN(T->pRight);
		cout << T->key;
	}
}

void NLR(TNode *T)
{
	if (T != NULL)
	{
		cout << T->key;
		NLR(T->pLeft);
		NLR(T->pRight);
	}
}

void NhapBT(vector<char> &a)
{
	char x;
	cin >> x;
	while (x != '#')
	{
		a.push_back(x);
		cin >> x;
	}
}

int main()
{
	Queue Q;
	StackTree ST;
	vector<char> A;

	CreateQueue(Q);
	CreateStackTree(ST);

	NhapBT(A);

	InFixToPostFix(A, Q);

	CreateTree(ST, Q);

	TNode *a = ST.pHead;
	NLR(a);
	cout << endl;
	LRN(a);
	return 0;
}