package com.kingdz.algorithm.time201702;import java.util.HashMap;import java.util.HashSet;import java.util.List;import java.util.Map;import java.util.Set;/** * 算數表達式求值<br/> * 求解思路：按照計算表達式的思考模式，從左到右一次計算，判斷每個運算符前后兩個臨近運算符的優先級來判斷計算的方式<br/> * 缺陷：目前在處理中括號和大括號時會有困難 *  * @author kingdz *  */public class Algo08 {	// 優先級map	public static final Map<String, Integer> PRiorMap;	static {		priorMap = new HashMap<String, Integer>();		priorMap.put("+", 0);		priorMap.put("-", 0);		//		priorMap.put("*", 1);		priorMap.put("/", 1);		//		priorMap.put("(", 2);		priorMap.put(")", 2);		//		priorMap.put("[", 3);		priorMap.put("]", 3);		//		priorMap.put("{", 4);		priorMap.put("}", 4);	}	public static void main(String[] args) {		String question = "1+2*(3+4)*5-6";		// 將字符串轉化為list		List<String> list = Algo07.dismantle(question);		System.out.print(" ");		// 首先打印需要計算的結果		printList(list, false);		int result = cal(list);		// 輸出最終計算的結果		System.out.println(result);	}	/**	 * 打印list，類似于算術	 * 	 * @param list	 * @param isPrintEquals	 *            是否在前面打印“=”符號	 */	private static void printList(List<String> list, boolean isPrintEquals) {		StringBuilder strb = new StringBuilder();		for (String str : list) {			strb.append(str);		}		if (isPrintEquals) {			System.out.println("=" + strb);		} else {			System.out.println(strb);		}	}	/**	 * 打印list，類似于算術	 * 	 * @param list	 */	private static void printList(List<String> list) {		printList(list, true);	}	/**	 * 計算list表達式	 * 	 * @param list	 * @return	 */	private static int cal(List<String> list) {		// 將所有運算符存入set，方便判斷是否是運算符		Set<String> set = new HashSet<String>();		for (String str : Algo07.separator) {			set.add(str);		}		// 用于標記當前處理的位置		int index = 0;		// 當list的大小為1時表示計算完成		while (list.size() > 1) {			if (index >= list.size()) {				// 如果已經處理到結尾，但是依然沒有計算出結果則重新計算				index = 0;			}			// 獲得當前處理的字符串			String now = list.get(index);			{				String before2 = index - 2 >= 0 ? list.get(index - 2) : null;				String before1 = index - 1 >= 0 ? list.get(index - 1) : null;				String after1 = index + 1 < list.size() ? list.get(index + 1) : null;				String after2 = index + 2 < list.size() ? list.get(index + 2) : null;				if (before1 != null && after1 != null) {					{						// 用于去括號						boolean accord = false;						if (before1.equals("(") && after1.equals(")")) {							accord = true;						} else if (before1.equals("[") && after1.equals("]")) {							accord = true;						} else if (before1.equals("{") && after1.equals("}")) {							accord = true;						}						if (accord) {							list.remove(index + 1);							list.remove(index - 1);							// index--;							index = 0;							// System.out.println(list);							printList(list);							continue;						}					}					// 是運算符					if (set.contains(now)) {						// 計算前后的優先級						int beforePrior2 = getPriority(before2);						// int beforePrior1 = getPriority(before1);						int nowPrior = getPriority(now);						// int afterPrior1 = getPriority(after1);						int afterPrior2 = getPriority(after2);						if (nowPrior == 1 || (nowPrior == 0 && beforePrior2 != 1 && afterPrior2 != 1)) {							int beforeInt;							int afterInt;							try {								beforeInt = Integer.parseInt(list.get(index - 1));								afterInt = Integer.parseInt(list.get(index + 1));							} catch (NumberFormatException e) {								index++;								continue;							}							// 實際進行計算處理							boolean accord = false;							if ("+".equals(now)) {								list.set(index, "" + (beforeInt + afterInt));								accord = true;							} else if ("-".equals(now)) {								list.set(index, "" + (beforeInt - afterInt));								accord = true;							} else if ("*".equals(now)) {								list.set(index, "" + (beforeInt * afterInt));								accord = true;							} else if ("/".equals(now)) {								list.set(index, "" + (beforeInt / afterInt));								accord = true;							}							if (accord) {								list.remove(index + 1);								list.remove(index - 1);								// index--;								index = 0;								// System.out.println(list);								printList(list);								continue;							}						}					}				}			}			index++;		}		return Integer.parseInt(list.get(0));	}	/**	 * 根據運算符判斷優先級數字	 * 	 * @param str	 * @return 如果是空則返回-1，如果沒有則返回-2	 * 	 */	private static int getPriority(String str) {		if (str == null) {			return -1;		}		if (priorMap.containsKey(str)) {			return priorMap.get(str);		} else {			return -2;		}	}}