import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;

public class tmp {
	private static Map<Character, Integer> charVal= new HashMap<>();
	
	/**
	 * 取得当前操作符的栈内优先级
	 * @param ch
	 * @return
	 */
	private static int getInStackPriority(char ch) {
		switch(ch) {
			case '#':return 0;
			case '(':return 1;
			case '*':return 5;
			case '/':return 5;
			case '+':return 3;
			case '-':return 3;
			case ')':return 6;
			default: return -1;
		}
	}
	/**
	 * 取得当前操作符的栈外优先级
	 * @param ch
	 * @return
	 */
	private static int getOutStackPriority(char ch) {
		switch(ch) {
			case '#':return 0;
			case '(':return 6;
			case '*':return 4;
			case '/':return 4;
			case '+':return 2;
			case '-':return 2;
			case ')':return 1;
			default: return -1;
		}
	}
	
	private static boolean isWord(char ch) {
		if((ch==' ')||('a'<=ch&&'z'<=ch)||('A'<=ch&&'Z'<=ch)) return true;
		else return false;
	}
	//中缀表达式转为后缀表达式
	private static String inorderToPostOrderExpression(String inorderExpression) {
		Stack<Character> opStack = new Stack<Character>();
		StringBuilder postOrderExpression = new StringBuilder();
		
		for(int i=0;i<inorderExpression.length();i++) {
			char ch = inorderExpression.charAt(i);
			//如果遇到操作数，直接加入后缀表达式
			if(isWord(ch)) {System.out.print(ch);postOrderExpression.append(ch);
				//附加操作，给这个操作数随机赋值
				if(charVal.get(ch)==null) {
					charVal.put(ch, (int)(10*Math.random()));
				}
			}
			//如果遇到左括号，直接入栈
			if(ch=='(') opStack.push(ch);
			//ch 将会是 + - * /  )中的一项
			else if(getInStackPriority(ch)!=-1) {
				//如果ch是其他运算符（不是右括号）
				if(ch!=')') {
					//将栈中所有优先级大于等于当前运算符的符号全部加入后缀表达式，直到栈空或遇到左括号为止
					while(!opStack.isEmpty()&&getInStackPriority(opStack.peek())>=getInStackPriority(ch)) {
						if(opStack.peek()=='(') {
							//左括号也要出栈
							opStack.pop();
							break;
						}
						postOrderExpression.append(opStack.peek());
						System.out.print(opStack.pop());
					}
					//将当前符号入栈
					opStack.push(ch);
				}else {//如果ch是右括号
					//将栈中所有符号依次加入后缀表达式，直到遇到左括号为止
					while(!opStack.isEmpty()&&opStack.peek()!='(') {
						postOrderExpression.append(opStack.peek());
						System.out.print(opStack.pop());
					}
					//左括号也要出栈
					opStack.pop();
				}
			}
		}
		while(!opStack.isEmpty()) {
			if(opStack.peek()!='(') {
				postOrderExpression.append(opStack.peek());
				System.out.print(opStack.peek());
			}
			opStack.pop();
		}
		
		return postOrderExpression.toString();
	}
	
	/**
	 * 后缀表达式求值
	 * @return
	 */
	private static int postOrderExpressionToVal(String postOrderExpression) {
		System.out.println(charVal);
		Stack<Integer> exp = new Stack<Integer>();
		for(int i=0;i<postOrderExpression.length();i++) {
			char ch = postOrderExpression.charAt(i);
			if(isWord(ch)) exp.push(charVal.get(ch));
			else if(getInStackPriority(ch)!=-1) {
				int op2 = exp.pop();
				int op1 = exp.pop();
				switch(ch) {
					case '+':exp.push(op1 + op2);break;
					case '-':exp.push(op1 - op2);break;
					case '*':exp.push(op1 * op2);break;
					case '/':exp.push(op1 / op2);break;
				}
			}
		}
		return exp.pop(