一、表達式的組成
1、數字
2、運算符：+ - / * ^ % =
3、圓括号
4、變量
二、運算符優先級
由高到低分别為：+-(正負号)、^、*/%、+-、=
優先級相等的運算符按照從左到右的順序計算
三、關鍵技術點
1、确定運算的優先級，從高到低分别為：原子元素表達式，包括數字和變量；括号表達式；一進制表達式，取數的負數；指數表達式；乘、除、取模表達式；加、減表達式；指派表達式。
2、對于每一級别的運算，都由一個方法實作，在方法中先完成比自己高一級别的運算，再處理本級别的運算。是以，在計算整個表達式的主方法中，隻需要調用最低級别的運算的實作方法即可。
3、确定表達式中的分隔符，（+、-、*、/、%、^、=、(、)、）。利用這些分隔符将表達式分成多段，每一段叫做一個token，分隔符也算token。
4、用長度為26的int數組vars存儲變量的值。
5、Character的isWhitespace方法判斷字元是否為空白符，用于去掉表達式中的空白符。
6、Character的isLetter方法判斷字元是否為字母，用于提取表達式中的變量
7、Character的isDigit方法判斷字元是否為數字，用于擷取表達式中的數字
四、示範執行個體
package book.oo.String;
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; //表達式為空錯誤
public static final int DIVBYZERO_ERROR = 3; //被0除錯誤
//針對4種錯誤類型定義的4個錯誤提示
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]; //變量數組
public ExpressionParser() {
}
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);
}
result = this.parseAssign(); //處理指派語句
//處理完指派語句，應該就是表達式結束符，如果不是，則傳回異常
if(!this.token.equals(EOE)) {
this.handleError(SYNTAX_ERROR);
}
return result;
}
public 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.pareseMulOrDiv(); //用乘除法計算目前表達式的值
//如果目前标記的第一個字母是加減号，則繼續進行加減運算
while ((op = this.token.charAt(0)) == ''+'' || op == ''-'') {
this.getToken(); //取下一個标記
//用乘除法計算目前子表達式的值
partialResult = this.pareseMulOrDiv();
switch(op) {
case ''-'':
//如果是減法，則用已處理的子表達式的值減去目前子表達式的值
result = result - partialResult;
break;
case ''+'':
//如果是加法，用已處理的子表達式的值加上目前子表達式的值
result = result + partialResult;
break;
}
}
return result;
}
private double pareseMulOrDiv() 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除異常
if(partialResult == 0.0) {
this.handleError(DIVBYZERO_ERROR);
}
//除數不為0，則進行除法運算
result = result / partialResult;
break;
case ''%'':
//如果是取模運算，也要判斷目前子表達式的值是否為0
if(partialResult == 0.0) {
this.handleError(DIVBYZERO_ERROR);
}
result = result % partialResult;
break;
}
}
return result;
}
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;
}
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;
}
private double findVar(String vname) throws Exception {
if (!Character.isLetter(vname.charAt(0))) {
this.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--;
}
}
private void handleError(int errorType) throws Exception {
//遇到異常情況時，根據錯誤類型，取得異常提示資訊，将提示資訊封裝在異常中抛出
throw new Exception(ERROR_MESSAGES[errorType]);
}
private void getToken() {
//設定初始值
this.token = "";
this.tokenType = NONE_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;
}
}
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 = 5.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));
}
}
輸出結果：
exp1("a = 5.0") = 5.0
exp2("b = 3.0") = 3.0
exp3("(a + b) * (a - b)") = 16.0
exp4("3*5-4/2") = 13.0
exp5("(4 - 2) * ((a + b) / (a - b))") = 8.0
exp6("5 % 2") = 1.0
exp7("3^2 * 5 + 4") = 49.0
五、執行個體分析
表達式的解析，實際就是一個表達式的分解過程。根據分隔符将表達式分成若幹段。然後計算每一段的值，最後都會歸結到一個原子表達式。
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)