#include<iostream>

using namespace std;

typedef char MyData;


struct TreeNode
{
	MyData Key;
	TreeNode *Next; // Con tro dong vai tro lien ket 1 danh sach lien ket don
	TreeNode *Left; // -------------------- lien ket tren cay ---------------
	TreeNode *Right;// ------------------------------------------------------
}; // Node vua la Node trong LinkList vua la Node cua Tree.

TreeNode* MakeTNode(MyData Data) // Tao mot node moi
{
	TreeNode *p = new TreeNode;
	p->Key = Data;
	p->Left = NULL;
	p->Right = NULL;
	p->Next = NULL;
	return p;
}

void PushToStack(TreeNode *&pHead, TreeNode *pNode) // Day mot nut vao Stack (AddHead)
{
	if (pHead == NULL)
	{
		pHead = pNode;
	}
	else
	{
		pNode->Next = pHead;
		pHead = pNode;
	}
}

MyData PopDataFromStack(TreeNode *&pHead) // Lay du lieu ra tu dinh cua Stack
{
	if (pHead != NULL)
	{
		char tmp = pHead->Key;
		TreeNode *p = pHead;
		pHead = pHead->Next;
		delete p;
		return tmp;
	}
}

TreeNode* PopNodeFromStack(TreeNode *&pHead) // Lay mot node ra tu dinh cua Stack
{
	if (pHead != NULL)
	{
		TreeNode *p = pHead;
		pHead = pHead->Next;
		p->Next = NULL;
		return p;
	}
}

TreeNode *CreateTreeNode(TreeNode *& Operator, TreeNode *& Node)
{
	MyData tmp;

	tmp = PopDataFromStack(Operator);
	TreeNode *p = MakeTNode(tmp);

	TreeNode *ptmp;

	ptmp = PopNodeFromStack(Node);
	p->Right = ptmp;

	ptmp = PopNodeFromStack(Node);
	p->Left = ptmp;

	return p;
} // Tao mot cay moi bang cach lay tu Operator Stack 1 phan tu va Node Stack 2 phan tu 



void PreOrderTrav(TreeNode* root) // Duyet NLR
{
	if (root != NULL)
	{
		cout << root->Key;
		PreOrderTrav(root->Left);
		PreOrderTrav(root->Right);

	}
}

void PostOrderTrav(TreeNode *root) //Duyet LRN
{
	if (root != NULL)
	{
		PostOrderTrav(root->Left);
		PostOrderTrav(root->Right);
		cout << root->Key;
	}
}
void TraverseInStack(TreeNode *Head)
{
	while (Head)
	{
		cout << Head->Key;
		Head = Head->Next;
	}
}

int main()
{
	TreeNode *OperatorStack = NULL , *NodeStack = NULL;
	// Khoi tao 2 stack 

	char x;
	char tmp;


	do
	{
		cin >> x;
		if (x == '#')
			break;

		if (x == '*' || x == '/' || x == '+' || x == '-' || x == '(' || x == ')') // Neu la toan tu
		{
			if (OperatorStack == NULL || x == '(')

				PushToStack(OperatorStack, MakeTNode(x));


			else

				if (x == '+' || x == '-')

				{
					while (OperatorStack != NULL && OperatorStack->Key != '(')

						PushToStack(NodeStack, CreateTreeNode(OperatorStack, NodeStack));

					PushToStack(OperatorStack, MakeTNode(x));

				}
				else
					if ((x=='*'|| x=='/') && (OperatorStack->Key =='*' || OperatorStack->Key == '/'))
					{ 
						while (OperatorStack != NULL && (OperatorStack->Key == '*' || OperatorStack->Key == '/'))

							PushToStack(NodeStack, CreateTreeNode(OperatorStack, NodeStack));

						PushToStack(OperatorStack, MakeTNode(x));

					}
					else

					if (x == ')')
					{
						while (OperatorStack->Key != '(')

							PushToStack(NodeStack, CreateTreeNode(OperatorStack, NodeStack));


						tmp = PopDataFromStack(OperatorStack);
					}
					else
						PushToStack(OperatorStack, MakeTNode(x));



		}
		else // Neu la toan hang
			PushToStack(NodeStack, MakeTNode(x));

		// Bo comment neu muon kiem tra stack hoat dong

		//////cout << "operstack: ";
		//////TraverseInStack(OperatorStack);
		//////cout << endl;
		//////cout << "nodestack: ";
		//////TraverseInStack(NodeStack);
		//////cout << endl;

	} while (x != '#');


	while (OperatorStack != NULL)
		PushToStack(NodeStack, CreateTreeNode(OperatorStack, NodeStack));



	PreOrderTrav(NodeStack);
	cout << endl;
	PostOrderTrav(NodeStack);

	system("pause");
	return 0;
}