3563759_ac_297ms_2656k.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;

public class Main {
	private Scanner in;

	public static void main(String[] args) {
		new Main().run();
	}

	private String sort(String str) {
		char [] ret = str.substring(1, str.length() - 1).toCharArray();

		Arrays.sort(ret);
		return "{" + new String(ret) + "}";
	}

	private void run() {
		in = new Scanner(System.in);

		while (in.hasNext()) {
			System.out.println(sort(calc(in.next())));
		}
	}

	private String calc(String str) {
		while (true) {
			int i = str.indexOf(')');
			if (i == -1) {
				break;
			}
			int j = str.substring(0, i).lastIndexOf('(');
			str = str.substring(0, j) + solve(str.substring(j + 1 , i))
				+ (i + 1 == str.length() ? "" : str.substring(i + 1));
		}
		return solve(str);
	}

	private String solve(String str) {
		int i;
		int p1, p2;
		
		i = str.indexOf('*');
		if (i != -1) {
			p1 = i;
			while (str.charAt(p1) != '{') {
				p1--;
			}
			p2 = i;
			while (str.charAt(p2) != '}') {
				p2++;
			}
			str = str.substring(0, p1)
				+ getIntersection(str.substring(p1 + 1, i - 1), str.substring(i + 2, p2))
				+ (p2 + 1 != str.length() ? str.substring(p2 + 1) : "");
			return solve(str);
		}

		for (i = 0; i < str.length(); i++) {
			if (str.charAt(i) == '+' || str.charAt(i) == '-') {
				p1 = i;
				while (str.charAt(p1) != '{') {
					p1--;
				}
				p2 = i;
				while (str.charAt(p2) != '}') {
					p2++;
				}
				str = str.substring(0, p1)
					+ (str.charAt(i) == '+' 
					? getUnion(str.substring(p1 + 1, i - 1), str.substring(i + 2, p2))
					: getDiffer(str.substring(p1 + 1, i - 1), str.substring(i + 2, p2)))
					+ (p2 + 1 != str.length() ? str.substring(p2 + 1) : "");
				return solve(str);
			}
		}
		return str;
	}

	private String getIntersection(String a, String b) {
		String ret = "";

		for (int i = 0; i < a.length(); i++) {
			if (b.indexOf(a.charAt(i)) != -1) {
				ret += a.charAt(i);
			}
		}
		return "{" + ret + "}";
	}

	private String getUnion(String a, String b) {
		String ret;

		ret = a;
		for (int i = 0; i < b.length(); i++) {
			if (a.indexOf(b.charAt(i)) == -1) {
				ret += b.charAt(i);
			}
		}
		return "{" + ret + "}";
	}

	private String getDiffer(String a, String b) {
		String ret = "";

		for (int i = 0; i < a.length(); i++) {
			if (b.indexOf(a.charAt(i)) == -1) {
				ret += a.charAt(i);
			}
		}
		return "{" + ret + "}";
	}
}