package book.string;

/**
 * 一個簡單的表達式解析器，這個解析器可以計算由數字、運算符和括號組成的表達式的值，并能處理變量，
 * 為了處理簡單，本解析器只支持一個字母的變量，不區分變量字母的大小寫。因此，最多只能存儲26個變量。
 * 如果用戶的變量名長度大于一個字母，則只取第一個字母當作變量。
 */
public class ExpressionParser {

	// 4種標記類型
	/**	標記為空或者結束符	*/
	public static final int NONE_TOKEN = 0;
	/**	標記為分隔符*/
	public static final int DELIMITER_TOKEN = 1;
	/**	標記為變量*/
	public static final int VARIABLE_TOKEN = 2;
	/**	標記為數字*/
	public static final int NUMBER_TOKEN = 3;

	// 4種錯誤類型
	/**	語法錯誤	*/
	public static final int SYNTAX_ERROR = 0;
	/**	括號沒有結束錯誤	*/
	public static final int UNBALPARENS_ERROR = 1;
	/**	表達式為空錯誤	*/
	public static final int NOEXP_ERROR = 2;
	/**	被0除錯誤	*/
	public static final int DIVBYZERO_ERROR = 3;
	//針對四種錯誤類型，定義的四個錯誤提示
	public static final String[] ERROR_MESSAGES = { "Syntax Error", "Unbalanced Parentheses",
			"No Expression Present", "Division by Zero" };
	/**	表達式的結束標記*/
	public static final String EOE = "\0";
	
	/**	表達式字符串*/
	private String exp;  
	/**	解析器當前指針在表達式中的位置*/
	private int expIndex;   
	/**	解析器當前處理的標記*/
	private String token;  
	/**	解析器當前處理標記的類型*/
	private int tokenType; 

	/**	變量的數組*/  
	private double vars[] = new double[26];

	/**
	 * 解析一個表達式，返回表達式的值。
	 * @param expStr	表達式字符串
	 * @return
	 * @throws Exception
	 */  
	public double evaluate(String expStr) throws Exception {
		double result;
		this.exp = expStr;
		this.expIndex = 0;

		//獲取第一個標記
		this.getToken();
		if (this.token.equals(EOE)){
			//沒有表達式異常
			this.handleError(NOEXP_ERROR); // no expression present
		}

		//處理賦值語句
		result = this.parseAssign();
		//處理完賦值語句，應該就是表達式結束符，如果不是，則返回異常
		if (!this.token.equals(EOE)){  
			this.handleError(SYNTAX_ERROR);
		}

		return result;
	}

	/**
	 * 處理賦值語句
	 */  
	private double parseAssign() throws Exception {
		double result;//結果
		int varIndex;//變量下標
		String oldToken;//舊標記
		int oldTokenType;//舊標記的類型

		//如果標記類型是變量
		if (this.tokenType == VARIABLE_TOKEN) {
			// 保存當前標記  
			oldToken = new String(this.token);
			oldTokenType = this.tokenType;
			// 取得變量的索引，本解析器只支持一個字目的變量，
			//如果用戶的變量字母長度大于1，則取第一個字母當作變量  
			varIndex = Character.toUpperCase(this.token.charAt(0)) - 'A';
			
			//獲得下一個標記
			this.getToken();
			//如果當前標記不是等號=
			if (!this.token.equals("=")) {
				//回滾
				this.putBack();  
				// 不是一個賦值語句，將標記恢復到上一個標記  
				this.token = new String(oldToken);
				this.tokenType = oldTokenType;
			} else {
				//如果當前標記是等號=，即給變量賦值，形式如a = 3 + 5;
				//則計算等號后面表達式的值，然后將得到的值賦給變量
				this.getToken();
				//因為加減法的優先級最低，所以計算加減法表達式。
				result = this.parseAddOrSub();
				//將表達式的值賦給變量，并存在實例變量vars中。
				this.vars[varIndex] = result;
				//返回表達式的值
				return result;
			}
		}
		//如果當前標記類型不是變量，或者不是賦值語句，則用加減法計算表達式的值。
		return this.parseAddOrSub();
	}

	/**
	 * 計算加減法表達式
	 */ 
	private double parseAddOrSub() throws Exception {
		char op;//操作符
		double result;//結果
		double partialResult;//子表達式的結果
		//用乘除法計算當前子表達式的值
		result = this.parseMulOrDiv();
		//如果當前標記的第一個字母是加減號，則繼續進行加減法運算。
		while ((op = this.token.charAt(0)) == '+' || op == '-') {
			//取下一個標記
			this.getToken();
			//用乘除法計算當前子表達式的值
			partialResult = this.parseMulOrDiv();
			switch (op) {
			case '-':
				//如果是減法，則用已處理的子表達式的值減去當前子表達式的值
				result = result - partialResult;
				break;
			case '+':
				//如果是加法，用已處理的子表達式的值加上當前子表達式的值
				result = result + partialResult;
				break;
			}
		}
		return result;
	}

	/**
	 * 計算乘除法表達式，包括取模運算
	 */ 
	private double parseMulOrDiv() throws Exception {
		char op;//操作符
		double result;//結果
		double partialResult;//子表達式的結果
		//用指數運算計算當前子表達式的值
		result = this.parseExponent();
		//如果當前標記的第一個字母是乘、除或者取模運算符，則繼續進行乘除法運算。
		while ((op = this.token.charAt(0)) == '*' || op == '/' || op == '%') {
			//取下一個標記
			this.getToken();
			//用指數運算計算當前子表達式的值
			partialResult = this.parseExponent();
			switch (op) {
			case '*':
				//如果是乘法，則用已處理子表達式的值乘以當前子表達式的值
				result = result * partialResult;
				break;
			case '/':
				//如果是除法，先判斷當前子表達式的值是否為0，如果為0，則拋出被0除異常
				//除數不能為0
				if (partialResult == 0.0){
					this.handleError(DIVBYZERO_ERROR);
				}
				//除數不為0，則進行除法運算
				result = result / partialResult;
				break;
			case '%':
				//如果是取模運算，也要判斷當前子表達式的值是否為0
				//如果為0，則拋出被0除異常
				if (partialResult == 0.0){
					this.handleError(DIVBYZERO_ERROR);
				}
				//進行取模運算
				result = result % partialResult;
				break;
			}
		}
		return result;
	}

	/**
	 * 計算指數表達式
	 * @throws Exception
	 */  
	private double parseExponent() throws Exception {
		double result;//結果
		double partialResult;//子表達式的值
		double ex;//指數的底數
		int t;//指數的冪

		//用一元運算計算當前子表達式的值（底數）
		result = this.parseUnaryOperator();
		//如果當前標記為"^"運算符，則為指數計算
		if (this.token.equals("^")) {
			//獲取下一個標記，即獲取指數的冪
			this.getToken();
			partialResult = this.parseExponent();
			ex = result;
			if (partialResult == 0.0) {
				//如果指數的冪為0，則指數的值為1
				result = 1.0;
			} else {
				//否則，指數的值為個數為指數冪的底數相乘的結果。
				for (t = (int) partialResult - 1; t > 0; t--){
					result = result * ex;
				}
			}
		}
		return result;
	}

	/**
	 * 計算一元運算，+，-，表示正數和復數
	 */  
	private double parseUnaryOperator() throws Exception {
		double result;//結果
		String op;//操作符

		op = "";
		//如果當前標記類型為分隔符，而且分隔符的值等于+或者-。
		if ((this.tokenType == DELIMITER_TOKEN) && 
				this.token.equals("+") || this.token.equals("-")) {
			op = this.token;
			this.getToken();
		}
		//用括號運算計算當前子表達式的值
		result = this.parseBracket();
		if (op.equals("-")){
			//如果操作符為-，則表示負數，將子表達式的值變為負數
			result = -result;
		}

		return result;
	}

	/**
	 * 計算括號運算
	 */  
	private double parseBracket() throws Exception {
		double result;//結果
		//如果當前標記為左括號，則表示是一個括號運算
		if (this.token.equals("(")) {
			//取下一個標記
			this.getToken();
			//用加減法運算計算子表達式的值
			result = this.parseAddOrSub();
			//如果當前標記不等于右括號，拋出括號不匹配異常
			if (!this.token.equals(")")){
				this.handleError(UNBALPARENS_ERROR);
			}
			//否則取下一個標記
			this.getToken();
		} else {
			//如果當前標記不是左括號，表示不是一個括號運算，則用原子元素運算計算子表達式的值
			result = this.parseAtomElement();
		}

		return result;
	}

	/**
	 * 計算原子元素運算，包括變量和數字
	 * @return
	 * @throws Exception
	 */  
	private double parseAtomElement() throws Exception {
		double result = 0.0;//結果
		
		switch (this.tokenType) {
		case NUMBER_TOKEN:
			//如果當前標記類型為數字
			try {
				//將數字的字符串轉換成數字值
				result = Double.parseDouble(this.token);
			} catch (NumberFormatException exc) {
				this.handleError(SYNTAX_ERROR);
			}
			//取下一個標記
			this.getToken();
			break;
		case VARIABLE_TOKEN:
			//如果當前標記類型是變量，則取變量的值
			result = this.findVar(token);
			this.getToken();
			break;
		default:
			this.handleError(SYNTAX_ERROR);
			break;
		}
		return result;
	}

	/**
	 * 根據變量名獲取變量的值，如果變量名長度大于1，則只取變量的第一個字符
	 * @param vname	變量名
	 * @throws Exception
	 */ 
	private double findVar(String vname) throws Exception {
		//如果變量的第一個字符不是字母，則拋出語法異常
		if (!Character.isLetter(vname.charAt(0))) {
			handleError(SYNTAX_ERROR);
			return 0.0;
		}
		//從實例變量數組vars中取出該變量的值
		return vars[Character.toUpperCase(vname.charAt(0)) - 'A'];
	}

	/**
	 * 回滾，將解析器當前指針往前移到當前標記位置
	 */
	private void putBack() {
		if (this.token == EOE){
			return;
		}
		//解析器當前指針往前移動
		for (int i = 0; i < this.token.length(); i++) {
			this.expIndex--;
		}
	}

	/**
	 * 處理異常情況
	 * @param errorType	錯誤類型
	 * @throws Exception
	 */
	private void handleError(int errorType) throws Exception {
		//遇到異常情況時，根據錯誤類型，取得異常提示信息，將提示信息封裝在異常中拋出
		//可以考慮用自定義異常，而不用Exception
		throw new Exception(ERROR_MESSAGES[errorType]);
	}

	/**
	 * 獲取下一個標記
	 */  
	private void getToken() {
		//初始值
		this.tokenType = NONE_TOKEN;
		this.token = "";

		// 檢查表達式是否結束
		// 如果解析器當前指針已經到達了字符串的長度，則表明表達式已經結束，置當前標記的置為EOE
		if (this.expIndex == this.exp.length()) {
			this.token = EOE;
			return;
		}

		// 跳過表達式中的空白符 
		while (this.expIndex < this.exp.length()
				&& Character.isWhitespace(this.exp.charAt(this.expIndex))) {
			++this.expIndex;
		}

		// 再次檢查表達式是否結束 
		if (this.expIndex == this.exp.length()) {
			this.token = EOE;
			return;
		}
		
		//取得解析器當前指針指向的字符
		char currentChar = this.exp.charAt(this.expIndex);
		//如果當前字符是一個分隔符，則認為這是一個分隔符標記，給當前標記和標記類型賦值，并將指針后移
		if (isDelim(currentChar)) {  
			this.token += currentChar;
			this.expIndex++;
			this.tokenType = DELIMITER_TOKEN;
			
		} else if (Character.isLetter(currentChar)) {
			//如果當前字符是一個字母，則認為是一個變量標記。
			//將解析器指針往后移，直到遇到一個分隔符，之間的字符都是變量的組成部分
			while (!isDelim(currentChar)) {
				this.token += currentChar;
				this.expIndex++;
				if (this.expIndex >= this.exp.length()) {
					break;
				} else {
					currentChar = this.exp.charAt(this.expIndex);
				}
			}
			//設置標記類型為變量
			this.tokenType = VARIABLE_TOKEN;
			
		} else if (Character.isDigit(currentChar)) { 
			// 如果當前字符是一個數字，則認為當前標記的類型為數字
			// 將解析器指針往后移，直到遇到一個分隔符，之間的字符都是該數字的組成部分
			while (!isDelim(currentChar)) {
				this.token += currentChar;
				this.expIndex++;
				if (this.expIndex >= this.exp.length()){
					break;
				} else {
					currentChar = this.exp.charAt(this.expIndex);
				}
			}
			//設置標記類型為數字
			this.tokenType = NUMBER_TOKEN;
		} else { 
			//無法識別的字符，則認為表達式結束
			this.token = EOE;
			return;
		}
	}

	/**
	 * 判斷一個字符是否為分隔符。
	 * 表達式中的字符包括: 
	 * 加"+"、減"-"、乘"*"、除"/"、取模"%"、指數"^"、賦值"="、左括號"("、右括號")"
	 * @param c
	 * @return
	 */ 
	private boolean isDelim(char c) {
		if ((" +-/*%^=()".indexOf(c) != -1))
			return true;
		return false;
	}

	public static void main(String[] args) throws Exception {
		ExpressionParser test = new ExpressionParser();
		String exp1 = "a = 5.0";
		System.out.println("exp1(\"a = 4.0\") = " + test.evaluate(exp1));
		String exp2 = "b = 3.0";
		System.out.println("exp2(\"b = 3.0\") = " + test.evaluate(exp2));

		String exp3 = "(a+b) * (a-b)";
		System.out.println("exp3(\"(a+b) * (a-b)\") = " + test.evaluate(exp3));

		String exp4 = "3*5-4/2";
		System.out.println("exp4(\"3*5-4/2\") = " + test.evaluate(exp4));

		String exp5 = "(4-2)*((a+b)/(a-b))";
		System.out.println("exp5(\"(4-2)*((a+b)/(a-b))\") = " + test.evaluate(exp5));
		
		String exp6 = "5 % 2";
		System.out.println("exp6(\"5%2\") = " + test.evaluate(exp6));
		String exp7 = "3^2 * 5 + 4";
		System.out.println("exp7(\"3^2 * 5 + 4\") = " + test.evaluate(exp7));
		
		/**
		 * 一個簡單的表達式根據運算時的優先級從高到底為：
		 * （1）原子元素表達式，包括數字和變量；
		 * （2）括號表達式；
		 * （3）一元表達式，取數的負數；
		 * （4）指數表達式；
		 * （5）乘、除、取模表達式；
		 * （6）加、減表達式
		 * （7）賦值表達式；
		 * 因此，在計算一個表達式的值時，應該按優先級從高到底進行運算。
		 * 在本程序中，每個優先級的表達式的運算都用一個私有方法實現。在私有方法中，首先計算更高優先級的表達式。
		 * 即采用了類似遞歸調用的方式，盡管在evaluate方法中最先調用的是優先級最低的表達式的值，
		 * 但在實質上卻是優先級最高的表達式的私有方法最先被執行完。這就保證了表達式的運算是按照優先級從高到底的順序執行的。
		 */
	}
}