public class Main {
	public static void main(String[] args) {
		String exp = "x + 2 * (y - 5)";
		SuffixExpression se = compile(exp);
		Map<String, Integer> env = Map.of("x", 1, "y", 9);
		int result = se.execute(env);
		
		System.out.println(exp + " = " + result + " " + (result == 1 + 2 * (9 - 5) ? "✓" : "✗"));
	}

	static SuffixExpression compile(String exp) {
		// TODO:
		Deque<String> nums = new LinkedList<>();
		Deque<String> symbols = new LinkedList<>();
		for(int i=0;i<exp.length();i++) {
			String n = exp.charAt(i)+"";
			if (n.equals(" ")|| n.equals("(")|| n.equals(")"))continue;
			if(n.equals("+")||n.equals("-")||n.equals("*")||n.equals("/")) {
				symbols.push(n);
				continue;
			}
			
			nums.push(n);
		}
		
		
		return new SuffixExpression(nums, symbols);
	}
}

class SuffixExpression {
	Deque<String> nums;
	Deque<String> symbols;
	int execute(Map<String, Integer> env) {
		// TODO:
		int res = 0;
		
		for(int i=0;i<nums.size()+1;i++) {
			String last = nums.pop();
			String pre = nums.pop();
			String symb = (String)symbols.pop();
			int lastV = env.get(last) ==null ?Integer.parseInt(last): env.get(last);
			int preV = env.get(pre) ==null? Integer.parseInt(pre): env.get(pre);
			
			switch(symb) {
				case "+": 
					res = preV + lastV;
					break;
				case "-": 
					res = preV - lastV;
					break;
				case "*": 
					res = preV * lastV;
					break;
				case "/": 
					res = preV / lastV;
					break;
			}
			if(nums.size()==0) break;
			nums.push(res+"");
		}
		return res;
	}
	
	public SuffixExpression(Deque<String> nums, Deque<String> symbols) {
		this.nums = nums;
		this.symbols = symbols;
	}
}