import java.io.IOException;
import java.io.*;

public class Aexpression
{
	private static Node head; //points to the first node of a linked list
	private static Node tail; //use as a pointer that is pointing to the current node
        private static Node counter[] = new Node[10]; //use as a stack to store nodes
        private static int count = 0;
        private static int balance = 0; //the parentheses are balanced when it is equal to 0
        private static Node head1; //points to the first node of linked list F
        private static Node head2; //points to the first node of linked list R
        
	public static void main(String[] args) throws IOException {
		BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
		String str = stdin.readLine(); //read an expression from the user
		head1 = GETEXPR(str); //use 'head1' to store the first node of the linked list F containing the expression
		head = null;
		//check the user input's expression is a valid one or not, if it is not, prompt the user to input again
		while (balance != 0 || head1 == null || tail.getInfo() == '+' || tail.getInfo() == '-' ||tail.getInfo() == '*' ||tail.getInfo() == '/') {
			balance = 0;
			System.out.println("Invalid expression. Please enter again.");
			str = stdin.readLine();
			head1 = GETEXPR(str);
			head = null;
		}
		System.out.println();
		System.out.print("The original expression : ");
		DISP(head1); //display the linked list F representing the expression
		System.out.println();
		System.out.print("Do you want to do any substitution (Yy/Nn)? ");
		//variables to store the decision of the user to continue or not
		String go = stdin.readLine();
		char gogo = go.charAt(0);
		String str2; //a variable to store the substitution's linked list R
		char chr2; //a variable to store the letter being replaced
		char firstchar2; //a variable to store the first char of the linked list R
		while (gogo == 'Y' || gogo == 'y') {
			System.out.println("Please enter a variable and its substitution.");
			str2 = stdin.readLine();
			chr2 = str2.charAt(0);
			firstchar2 = str2.charAt(2);
			head2 = GETEXPR(str2.substring(2)); //use 'head2' to store the first node of the linked list R containing the expression
			head = null;
			//check the user input's expression is a valid one or not, if it is not, prompt the user to input again
			while (balance != 0 || head2 == null || tail.getInfo() == '+' || tail.getInfo() == '-' || tail.getInfo() == '*' ||tail.getInfo() == '/') {
				balance = 0;
				System.out.println("Invalid expression");
				System.out.println("Please enter a variable and its substitution again.");
				str2 = stdin.readLine();
				chr2 = str2.charAt(0);
				firstchar2 = str2.charAt(2);
				head2 = GETEXPR(str2.substring(2));
				head = null;
			}
			REPLACE(chr2, head1, head2); //call the 'REPLACE' method
			System.out.println("The substituted expression is");
			DISP(head1); //display the expression after replaced
			System.out.println();
			System.out.println();
			System.out.print("Do you want to do any substitution (Yy/Nn)? ");
			go = stdin.readLine();
			gogo = go.charAt(0);
		}	
		System.out.println("Thanks for using the system.");
	}
	
	public static Node GETEXPR(String str)
	{
		//open the first node
		char ch;
		ch = str.charAt(0);
		//if the first char is a letter, open a node and store the char in info field
		if (Character.isLetter(ch)) {
			head = new Node(0, ch);
			tail = head;
		}
		//if the first char is an open parenthese, open a node and store '(' in info field
		//and use an array to store the current node, so that the current pointer can point back to it
		//as the pointer needs to point back to the upper level
		else if (ch == '(') {
			head = new Node(1, ch);
			tail = head;
			counter[count] = head; //use the array 'counter' store the current node
			balance++; //increment the balance when there is an open parenthese
		}
		//open the linked list
		for (int i = 1; i <= str.length()-1; i++) {
			ch = str.charAt(i);
			//if the char is a letter, then do the followings
			if (Character.isLetter(ch)) {
				//need to open the first node first
				if (head != null) {
					//if the current node is a character or an operator, use the 'rightl'
					//to reference to this new char
					if (tail.getTag() == 0) {
						addToRight0(ch);
					}
					//if the current node is an open parenthese, use the 'downl'
					//to reference to this new char
					else if (tail.getTag() == 1) {
						count++;
						addToDown0(ch);
					}
				}
			//if the char is an open parenthese, then do the followings
			} else if (ch == '(') {
				//need to open the first node first in order to run the followings
				if (head != null) {
					//if the current node is an open parenthese, use the 'downl'
					//to reference to this new open parenthese
					if (tail.getTag() == 1) {
						count++;
						addToDown1(ch);
						balance++; //increment the balance when there is an open parenthese
					}
					//if the current node is a character or an operator, use the 'rightl'
					//to reference to this new open parenthese
					else if (tail.getTag() == 0) {
						addToRight1(ch);
						counter[count] = tail;
						balance++; //increment the balance when there is an open parenthese
					}
				}
			} else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
				//if the current is also an operator, then break
				if (tail.getInfo() == '+' ||tail.getInfo() == '-' ||tail.getInfo() == '*' ||tail.getInfo() == '/')
					break;
				//use the 'rightl' to reference to this new operator
				else
					addToRight0(ch);
				
			//if the char is a closed parenthese, then the pointer points back to node
			//that containing things in the upper level and set to the most right node
			} else if (ch == ')') {
				if (balance > 0){
					balance--; //decrement the balance when there is a closed parenthese
					count--;
					if (count >= 0) {
						tail = counter[count];
						while (tail.getRight() != null) {
							tail = tail.getRight();
						}
					}
				}
			}	
		}
		return head;
	}
	
	public static void DISP(Node current) {
		while (current != null) {
			if (current.getTag() == 0) {
				System.out.print(current.getInfo());
			} else if (current.getTag() == 1) {
				System.out.print('(');
				//use recursion to print the linked list that is below every open parentheses
				DISP(current.getDown());
				System.out.print(')');
			}
		//pointer points to the right node of the upper level's node
		current = current.getRight();
		}
	}
	
	public static void REPLACE(char v, Node vhead1, Node vhead2) {
		Node current = vhead1;
		while (current != null) {
			if (current.getTag() == 0) {
				//if the info char is equal to char v
				//replace it with linked list R
				//set the 'down' of the node before the char v points to linked list R
				if (current.getInfo() == v) {
					current.setTag(1);
					current.setDown(vhead2);
				}
			}
			else if (current.getTag() == 1) {
				//use recursion to point to the nodes below every open parenthese
				REPLACE(v, current.getDown(), vhead2);
			}
			//pointer points to the right node of every level
			current = current.getRight();
		}
	}
	
	//method to open a new node if the new node is a character or an operator and update
	//the pointer
	public static void addToRight0(char info) {
		tail.setRight(new Node(0, info));
		tail = tail.getRight();
	}
	//method to open a new node if the new node is an open parenthese and update the pointer
	public static void addToRight1(char info) {
		tail.setRight(new Node(1, info));
		tail = tail.getRight();
	}

	//method to open a new node if the new node is a character or an operator,
	//use the array 'counter' to store the current node and update the pointer
	public static void addToDown0(char info) {
		tail.setDown(new Node(0, info));
		counter[count] = tail.getDown();
		tail = tail.getDown();
	}
	//method to open a new node if the new node is used to store open parenthese,
	//use the array 'counter' to store the current node and update the pointer
	public static void addToDown1(char info) {
		tail.setDown(new Node(1, info));
		counter[count] = tail.getDown();
		tail = tail.getDown();
	}
		
}