#include<stdio.h> 
#include<math.h> 
#include<iostream>
#include<stack>
#include<map>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<sstream>
using namespace std;

typedef struct{    //PolandExp_Node
	string s;
	int type;     //0:operatorChar;1:number
}expNode;
typedef struct{      //calPolandExp_NumStack_union
	int start;
	int end; 
	//char c;
}pairs;
typedef struct{      //ClassMapt_node
	char way;
	int type;  //1:end
}mapNode;
class mapt{      //map
	public :
		mapNode node[100][100];
		int start;
		int used;
		mapt(){
			for(int i=0;i<100;i++){
				for(int j=0;j<100;j++){
					node[i][j].way='#';
				}
			}
			used=0;
		}
};
mapt calPoland(stack<expNode> t);
int operatorPriority(char c){
	switch(c){
		case '#':return 1;
		case '|':return 2;
		case '+':return 3;		
		case '*':return 4;
		default:return 1;
	}
}
/*float calculate(float a,float b,char c){
	switch(c){
		case '+':return a+b;
		case '-':return a-b;
		case '*':return a*b;
		case '/':return a/b;	
		default:; 
	}
}*/
stack<expNode>  makePoland(string t){
	int len=t.length(),i; 
	char c;
	stack<expNode> expStack;
	stack<char> charStack;
	charStack.push('#');
	for(i=0;i<len;i++){
		c=t[i]; 
		if(c=='(') {              
			charStack.push(c);
		}
		else if(c==')'){
			while(1){
				c=charStack.top();
				charStack.pop();
				if(c=='(')					
					break;
				expNode node;				
				node.s.append(1,c);
				node.type=0;
				expStack.push(node);
			}			
		}
		else if(c=='c'||c=='d'){
			expNode node;				
			node.s.append(1,c);
			node.type=1;						
			expStack.push(node);
		}
		else if(operatorPriority(c)>operatorPriority(charStack.top())) {
			charStack.push(c);
		}
		else if(operatorPriority(c)<=operatorPriority(charStack.top()))  {
			while(1){
				char topc=charStack.top();			
				if(operatorPriority(c)>operatorPriority(topc)){
					charStack.push(c);
					break;
				}								
				expNode node;				
				node.s.append(1,topc);
				node.type=0;			
				expStack.push(node);
				charStack.pop();
			}	
		}		
			printf("%d :",i);
			stack<expNode> x=expStack;
			while(!x.empty()){
				expNode node=x.top();
				cout<<node.s<<' ';
				x.pop();
			}  				
			printf("\n");
	}
	while(!charStack.empty()){
		c=charStack.top();
		charStack.pop();
		if(c=='#')
			break;
		expNode node;				
		node.s.append(1,c);
		node.type=0;
		expStack.push(node);
	}
	stack<expNode> x=expStack;
	while(!expStack.empty())
		expStack.pop();
	while(!x.empty()){
		expNode node=x.top();
		x.pop();
		expStack.push(node);
	}  				
/*	while(!expStack.empty()){
		expNode node=expStack.top();
		cout<<node.s;
		expStack.pop();
	} 
	printf("\n"); 
	//printf("%f\n",calPoland(expStack));
*/
    return expStack; 
}

mapt calPoland(stack<expNode> t){
	stack<pairs> numStack;	
	class mapt mp;
	int i=0,j,k;
	while(!t.empty()){
		expNode node=t.top();
		t.pop();
		if(node.type==1){
			i=mp.used++;
			j=mp.used++;
			mp.node[i][j].way=node.s[0];
			mp.node[i][0].type=0;
			mp.node[j][0].type=1;
			pairs p;
			p.start=i;
			p.end=j;
			numStack.push(p);
		}
		else if(node.type==0){
			if(node.s[0]=='|'){
				i=mp.used++;
				j=mp.used++;
				mp.node[i][0].type=0;
				mp.node[j][0].type=1;
				pairs pl=numStack.top();
				numStack.pop();
				pairs pr=numStack.top();
				numStack.pop();
				mp.node[i][pl.start].way='-';
				mp.node[i][pr.start].way='-';
				mp.node[pl.end][j].way='-';
				mp.node[pr.end][j].way='-';
				mp.node[pl.end][0].type=0;
				mp.node[pr.end][0].type=0;
				pairs p;
				p.start=i;
				p.end=j;
				numStack.push(p);
				mp.start=i;
			}
			else if(node.s[0]=='*'){
				i=mp.used++;
				j=mp.used++;
				mp.node[i][0].type=0;
				mp.node[j][0].type=1;
				pairs p1=numStack.top();
				numStack.pop();
				mp.node[p1.end][0].type=0;
				mp.node[p1.end][p1.start].way='-';
				mp.node[i][p1.start].way='-';
				mp.node[i][j].way='-';
				pairs p;
				p.start=i;
				p.end=p1.end;
				numStack.push(p);
				mp.start=i;		
			}
			else if(node.s[0]=='+'){
				pairs pr=numStack.top();
				numStack.pop();
				pairs pl=numStack.top();
				numStack.pop();
				mp.node[pl.end][pr.start].way='-';
				mp.node[pl.end][0].type=0;
				mp.start=pl.start;
			}
		}
		else {
			printf("error:expStack type error!\n");
		}			
	}
	return mp;
}
void writeMapt(mapt t){
	int i,k;	
	printf("Start: %d\n",t.start);
	printf("   ");
	for(j=0;j<t.used;j++){
		printf("%2d",j);
	}
	printf("\n");
	for(i=0;i<t.used;i++){
		printf("%2d :",i);
		for(j=0;j<t.used;j++){
			printf("%c ",t.node[i][j].way);
		}
		printf("%d \n",t.node[i][0].type);
	}
}
int main(){
	string s="c+(c|d)*" ;
	stack<expNode> expStack=makePoland(s);
	class mapt ans=calPoland(expStack);
	writeMapt(ans);
//	printf("%f\n",ans);
	
}