此題真可謂是練習編程語言的絕好材料 ！
import java.util.*;class Solution {
class Item {Map<String, Integer> vars = new TreeMap<>();int k = 1;String tos() {StringBuilder builder = new StringBuilder();List<String> a = new ArrayList<>();for (String i : vars.keySet()) {for (int j = 0; j < vars.get(i); j++) {a.add(i);}}if (a.size() == 0) return "";builder.append(a.get(0));for (int i = 1; i < a.size(); i++) {builder.append("*" + a.get(i));}return builder.toString();}Item copy() {Item it = new Item();it.k = k;for (Map.Entry<String, Integer> i : vars.entrySet()) {it.vars.put(i.getKey(), i.getValue());}return it;}Item mul(Item another) {Item ans = new Item();ans.k = k * another.k;for (Map.Entry<String, Integer> i : vars.entrySet()) {ans.vars.put(i.getKey(), i.getValue());}for (Map.Entry<String, Integer> i : another.vars.entrySet()) {if (ans.vars.containsKey(i.getKey())) {ans.vars.put(i.getKey(), ans.vars.get(i.getKey()) + i.getValue());} else {ans.vars.put(i.getKey(), i.getValue());}}return ans;}int getMi() {int s = 0;for (int x : vars.values()) {s += x;}return s;}Item render(Map<String, Integer> eval) {Item j = new Item();j.k = k;for (Map.Entry<String, Integer> i : vars.entrySet()) {if (eval.containsKey(i.getKey())) {j.k *= Math.pow(eval.get(i.getKey()), i.getValue());} else {j.vars.put(i.getKey(), i.getValue());}}return j;}
}class Exp {List<Item> items = new ArrayList<>();Exp add(Exp another) {Exp exp = new Exp();Map<String, Item> ma = new TreeMap<>();for (Item i : another.items) {Item j = i.copy();exp.items.add(j);ma.put(j.tos(), j);}for (Item i : items) {String k = i.tos();if (ma.containsKey(k)) {ma.get(k).k += i.k;} else {Item j = i.copy();ma.put(k, j);exp.items.add(j);}}return exp;}Exp sub(Exp another) {another.mul(-1);Exp ans = add(another);another.mul(-1);ans.mul(-1);return ans;}void mul(int x) {for (Item i : items) {i.k *= x;}}Exp mul(Exp another) {Exp ans = new Exp();for (Item i : items) {for (Item j : another.items) {ans.items.add(i.mul(j));}}return ans;}@Overridepublic String toString() {List<String> a = tos(this);StringBuilder builder = new StringBuilder();for (String i : a) {builder.append("+" + i);}return builder.toString();}
}List<String> tokenize(String expression) {List<String> ans = new ArrayList<>();for (int i = 0; i < expression.length(); i++) {if ("()+-*".indexOf(expression.charAt(i)) != -1) {ans.add(expression.charAt(i) + "");} else if (Character.isDigit(expression.charAt(i))) {int j = i;while (j < expression.length() && Character.isDigit(expression.charAt(j))) {j++;}ans.add(expression.substring(i, j));i = j - 1;} else if (Character.isLetter(expression.charAt(i))) {int j = i;while (j < expression.length() && Character.isLetter(expression.charAt(j))) {j++;}ans.add(expression.substring(i, j));i = j - 1;}}return ans;
}int getPriority(String i) {if (i.equals("*")) return 1;if (i.equals("+") || i.equals("-")) return 0;if (i.equals("(")) return 2;if (i.equals(")")) return -1;throw new RuntimeException("無法操作符號" + i);
}boolean isNumber(String s) {for (int i = 0; i < s.length(); i++) {if (!Character.isDigit(s.charAt(i))) {return false;}}return true;
}Exp number2Exp(int x) {Exp exp = new Exp();Item it = new Item();it.k = x;exp.items.add(it);return exp;
}Exp var2Exp(String var) {Exp exp = new Exp();Item it = new Item();it.vars.put(var, 1);exp.items.add(it);return exp;
}Exp calculate(Exp m, Exp n, String op) {if (op.equals("*")) return m.mul(n);else if (op.equals("+")) return m.add(n);else if (op.equals("-")) return m.sub(n);throw new RuntimeException("無法處理" + op + "運算");
}Exp parse(List<String> token) {Stack<Exp> num = new Stack<>();Stack<String> op = new Stack<>();for (String i : token) {if (i.equals(")")) {while (!op.peek().equals("(")) {num.push(calculate(num.pop(), num.pop(), op.pop()));}op.pop();} else if ("+-*(".indexOf(i.charAt(0)) != -1) {while (!op.empty() && !op.peek().equals("(") && getPriority(i) <= getPriority(op.peek())) {Exp a = num.pop(), b = num.pop();String o = op.pop();num.push(calculate(a, b, o));}op.push(i);} else if (isNumber(i)) {num.push(number2Exp(Integer.parseInt(i)));} else {num.push(var2Exp(i));}}while (!op.empty()) {num.push(calculate(num.pop(), num.pop(), op.pop()));}return num.pop();
}Exp render(Exp exp, Map<String, Integer> eval) {Exp ans = new Exp();for (Item i : exp.items) {Item j = i.render(eval);ans.items.add(j);}return ans;
}Exp sort(Exp exp) {//合并同類項Map<String, Item> vars = new TreeMap<>();for (Item i : exp.items) {if (vars.containsKey(i.tos())) {vars.get(i.tos()).k += i.k;} else {vars.put(i.tos(), i);}}//去掉0項exp.items = new ArrayList<>();for (Item i : vars.values()) {if (i.k == 0) continue;exp.items.add(i);}//排序exp.items.sort((o1, o2) -> {int mi1 = o1.getMi();int mi2 = o2.getMi();if (mi1 == mi2) {return o1.tos().compareTo(o2.tos());} else {return mi2 - mi1;}});return exp;
}List<String> tos(Exp exp) {List<String> ans = new ArrayList<>();for (Item i : exp.items) {String it = i.k + "";if (i.tos().length() > 0) {it += "*" + i.tos();}ans.add(it);}return ans;
}public List<String> basicCalculatorIV(String expression, String[] evalvars, int[] evalints) {List<String> token = tokenize(expression);Map<String, Integer> eval = new TreeMap<>();for (int i = 0; i < evalvars.length; i++) {eval.put(evalvars[i], evalints[i]);}Exp exp = parse(token);exp = render(exp, eval);exp = sort(exp);List<String> ans = tos(exp);return ans;
}void haha() {List<String> ans = basicCalculatorIV("a*b+a*b*c*d", new String[]{"b"}, new int[]{2});for (String i : ans) {System.out.print(i + " ");}
}public static void main(String[] args) {Solution s = new Solution();s.haha();
}
}
