ExpCompare.java

import java.util.*;

interface Node {}
class LeafNode implements Node {
	String operand;
	public LeafNode(String o) {
		operand = o;
	}
	public String toString() {
		return String.format("(%s)", operand);
	}
}
class BinaryNode implements Node {
	Node left;
	Node right;
	String operator;
	public BinaryNode(String l, String r, String o) {
		this(new LeafNode(l), new LeafNode(r), o);
	}
	public BinaryNode(Node l, Node r, String o) {
		left = l;
		right = r;
		operator = o;
	}
	public String toString() {
		return String.format("(%s%s%s)", left, operator, right);
	}
}
class ExpCompare {
	public static void main(String[] args) {
		test1();
		test2();
		test3();
	}
	private static void test1() {
		//System.out.println(new BinaryNode(new LeafNode("a"), new LeafNode("b"), "+"));
		Node aPlusB = new BinaryNode(new LeafNode("a"), new LeafNode("b"), "+");
		Node aMinusB = new BinaryNode(new LeafNode("a"), new LeafNode("b"), "-");
		System.out.println(isSame(aPlusB, aMinusB)); // false
	}

	private static void test2() {
		Node aPlusB = new BinaryNode(new LeafNode("a"), new LeafNode("b"), "+");
		Node cMinusD = new BinaryNode(new LeafNode("c"), new LeafNode("d"), "-");
		//System.out.println(aPlusBMinusC);
		Node aPlusBMinusCMinusD = new BinaryNode(aPlusB, cMinusD, "-");
		Node aPlusD = new BinaryNode(new LeafNode("a"), new LeafNode("d"), "+");
		Node aPlusDPlusB = new BinaryNode(aPlusD, new LeafNode("b"), "+");
		Node aPlusDPlusBMinusC = new BinaryNode(aPlusDPlusB, new LeafNode("c"), "-");

		System.out.println(isSame(aPlusBMinusCMinusD, aPlusDPlusBMinusC));
	}
	private static void test3() {
		Node aMinusB = new BinaryNode(new LeafNode("a"), new LeafNode("b"), "-");
		Node cMinusD = new BinaryNode(new LeafNode("c"), new LeafNode("d"), "-");
		Node aMinusBPlusCMinusD = new BinaryNode(aMinusB, cMinusD, "+");

		Node bMinusCMinusD = new BinaryNode(new LeafNode("b"), cMinusD, "-");
		Node aMinusBMinusCMinusD = new BinaryNode(new LeafNode("a"), bMinusCMinusD, "-");
		System.out.println(isSame(aMinusBPlusCMinusD, aMinusBMinusCMinusD));
	}

	public static boolean isSame(Node a, Node b) {
		Map<String, Integer> map1 = new HashMap<>();
		count(a, map1, 0);
		Map<String, Integer> map2 = new HashMap<>();
		count(b, map2, 0);
		return map1.equals(map2);
	}

	private static void count(Node root, Map<String, Integer> map, int minusCount) {
		if(root instanceof LeafNode) {
			LeafNode leaf = (LeafNode)root;
			int count = map.getOrDefault(leaf.operand, 0);
			int newCount = minusCount%2==0 ? count+1 : count-1;
			if(newCount==0 && map.containsKey(leaf.operand)) {
				map.remove(leaf.operand);
			} else {
				map.put(leaf.operand, newCount);
			}
		} else if(root instanceof BinaryNode) {
			BinaryNode binary = (BinaryNode)root;
			int ext = binary.operator.equals("-") ? 1 : 0;
			count(binary.left, map, minusCount);
			count(binary.right, map, minusCount+ext);
		}
	}
}