package book.string;

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

	// 4種標(biāo)記類型
	/**	標(biāo)記為空或者結(jié)束符	*/
	public static final int NONE_TOKEN = 0;
	/**	標(biāo)記為分隔符*/
	public static final int DELIMITER_TOKEN = 1;
	/**	標(biāo)記為變量*/
	public static final int VARIABLE_TOKEN = 2;
	/**	標(biāo)記為數(shù)字*/
	public static final int NUMBER_TOKEN = 3;

	// 4種錯誤類型
	/**	語法錯誤	*/
	public static final int SYNTAX_ERROR = 0;
	/**	括號沒有結(jié)束錯誤	*/
	public static final int UNBALPARENS_ERROR = 1;
	/**	表達(dá)式為空錯誤	*/
	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" };
	/**	表達(dá)式的結(jié)束標(biāo)記*/
	public static final String EOE = "\0";
	
	/**	表達(dá)式字符串*/
	private String exp;  
	/**	解析器當(dāng)前指針在表達(dá)式中的位置*/
	private int expIndex;   
	/**	解析器當(dāng)前處理的標(biāo)記*/
	private String token;  
	/**	解析器當(dāng)前處理標(biāo)記的類型*/
	private int tokenType; 

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

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

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

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

		return result;
	}

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

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

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

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

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

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

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

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

		return result;
	}

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

		return result;
	}

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

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

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

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

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

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

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

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

	/**
	 * 判斷一個字符是否為分隔符。
	 * 表達(dá)式中的字符包括: 
	 * 加"+"、減"-"、乘"*"、除"/"、取模"%"、指數(shù)"^"、賦值"="、左括號"("、右括號")"
	 * @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));
		
		/**
		 * 一個簡單的表達(dá)式根據(jù)運算時的優(yōu)先級從高到底為：
		 * （1）原子元素表達(dá)式，包括數(shù)字和變量；
		 * （2）括號表達(dá)式；
		 * （3）一元表達(dá)式，取數(shù)的負(fù)數(shù)；
		 * （4）指數(shù)表達(dá)式；
		 * （5）乘、除、取模表達(dá)式；
		 * （6）加、減表達(dá)式
		 * （7）賦值表達(dá)式；
		 * 因此，在計算一個表達(dá)式的值時，應(yīng)該按優(yōu)先級從高到底進(jìn)行運算。
		 * 在本程序中，每個優(yōu)先級的表達(dá)式的運算都用一個私有方法實現(xiàn)。在私有方法中，首先計算更高優(yōu)先級的表達(dá)式。
		 * 即采用了類似遞歸調(diào)用的方式，盡管在evaluate方法中最先調(diào)用的是優(yōu)先級最低的表達(dá)式的值，
		 * 但在實質(zhì)上卻是優(yōu)先級最高的表達(dá)式的私有方法最先被執(zhí)行完。這就保證了表達(dá)式的運算是按照優(yōu)先級從高到底的順序執(zhí)行的。
		 */
	}
}