?? expressionparser.java
字號:
package book.string;
/**
* 一個(gè)簡單的表達(dá)式解析器，這個(gè)解析器可以計(jì)算由數(shù)字、運(yùn)算符和括號組成的表達(dá)式的值，并能處理變量，
* 為了處理簡單，本解析器只支持一個(gè)字母的變量，不區(qū)分變量字母的大小寫。因此，最多只能存儲26個(gè)變量。
* 如果用戶的變量名長度大于一個(gè)字母，則只取第一個(gè)字母當(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種錯(cuò)誤類型
/** 語法錯(cuò)誤 */
public static final int SYNTAX_ERROR = 0;
/** 括號沒有結(jié)束錯(cuò)誤 */
public static final int UNBALPARENS_ERROR = 1;
/** 表達(dá)式為空錯(cuò)誤 */
public static final int NOEXP_ERROR = 2;
/** 被0除錯(cuò)誤 */
public static final int DIVBYZERO_ERROR = 3;
//針對四種錯(cuò)誤類型，定義的四個(gè)錯(cuò)誤提示
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];
/**
* 解析一個(gè)表達(dá)式，返回表達(dá)式的值。
* @param expStr 表達(dá)式字符串
* @return
* @throws Exception
*/
public double evaluate(String expStr) throws Exception {
double result;
this.exp = expStr;
this.expIndex = 0;
//獲取第一個(gè)標(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;
// 取得變量的索引，本解析器只支持一個(gè)字目的變量，
//如果用戶的變量字母長度大于1，則取第一個(gè)字母當(dāng)作變量
varIndex = Character.toUpperCase(this.token.charAt(0)) - 'A';
//獲得下一個(gè)標(biāo)記
this.getToken();
//如果當(dāng)前標(biāo)記不是等號=
if (!this.token.equals("=")) {
//回滾
this.putBack();
// 不是一個(gè)賦值語句，將標(biāo)記恢復(fù)到上一個(gè)標(biāo)記
this.token = new String(oldToken);
this.tokenType = oldTokenType;
} else {
//如果當(dāng)前標(biāo)記是等號=，即給變量賦值，形式如a = 3 + 5;
//則計(jì)算等號后面表達(dá)式的值，然后將得到的值賦給變量
this.getToken();
//因?yàn)榧訙p法的優(yōu)先級最低，所以計(jì)算加減法表達(dá)式。
result = this.parseAddOrSub();
//將表達(dá)式的值賦給變量，并存在實(shí)例變量vars中。
this.vars[varIndex] = result;
//返回表達(dá)式的值
return result;
}
}
//如果當(dāng)前標(biāo)記類型不是變量，或者不是賦值語句，則用加減法計(jì)算表達(dá)式的值。
return this.parseAddOrSub();
}
/**
* 計(jì)算加減法表達(dá)式
*/
private double parseAddOrSub() throws Exception {
char op;//操作符
double result;//結(jié)果
double partialResult;//子表達(dá)式的結(jié)果
//用乘除法計(jì)算當(dāng)前子表達(dá)式的值
result = this.parseMulOrDiv();
//如果當(dāng)前標(biāo)記的第一個(gè)字母是加減號，則繼續(xù)進(jìn)行加減法運(yùn)算。
while ((op = this.token.charAt(0)) == '+' || op == '-') {
//取下一個(gè)標(biāo)記
this.getToken();
//用乘除法計(jì)算當(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;
}
/**
* 計(jì)算乘除法表達(dá)式，包括取模運(yùn)算
*/
private double parseMulOrDiv() throws Exception {
char op;//操作符
double result;//結(jié)果
double partialResult;//子表達(dá)式的結(jié)果
//用指數(shù)運(yùn)算計(jì)算當(dāng)前子表達(dá)式的值
result = this.parseExponent();
//如果當(dāng)前標(biāo)記的第一個(gè)字母是乘、除或者取模運(yùn)算符，則繼續(xù)進(jìn)行乘除法運(yùn)算。
while ((op = this.token.charAt(0)) == '*' || op == '/' || op == '%') {
//取下一個(gè)標(biāo)記
this.getToken();
//用指數(shù)運(yùn)算計(jì)算當(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)行除法運(yùn)算
result = result / partialResult;
break;
case '%':
//如果是取模運(yùn)算，也要判斷當(dāng)前子表達(dá)式的值是否為0
//如果為0，則拋出被0除異常
if (partialResult == 0.0){
this.handleError(DIVBYZERO_ERROR);
}
//進(jìn)行取模運(yùn)算
result = result % partialResult;
break;
}
}
return result;
}
/**
* 計(jì)算指數(shù)表達(dá)式
* @throws Exception
*/
private double parseExponent() throws Exception {
double result;//結(jié)果
double partialResult;//子表達(dá)式的值
double ex;//指數(shù)的底數(shù)
int t;//指數(shù)的冪
//用一元運(yùn)算計(jì)算當(dāng)前子表達(dá)式的值（底數(shù)）
result = this.parseUnaryOperator();
//如果當(dāng)前標(biāo)記為"^"運(yùn)算符，則為指數(shù)計(jì)算
if (this.token.equals("^")) {
//獲取下一個(gè)標(biāo)記，即獲取指數(shù)的冪
this.getToken();
partialResult = this.parseExponent();
ex = result;
if (partialResult == 0.0) {
//如果指數(shù)的冪為0，則指數(shù)的值為1
result = 1.0;
} else {
//否則，指數(shù)的值為個(gè)數(shù)為指數(shù)冪的底數(shù)相乘的結(jié)果。
for (t = (int) partialResult - 1; t > 0; t--){
result = result * ex;
}
}
}
return result;
}
/**
* 計(jì)算一元運(yùn)算，+，-，表示正數(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();
}
//用括號運(yùn)算計(jì)算當(dāng)前子表達(dá)式的值
result = this.parseBracket();
if (op.equals("-")){
//如果操作符為-，則表示負(fù)數(shù)，將子表達(dá)式的值變?yōu)樨?fù)數(shù)
result = -result;
}
return result;
}
/**
* 計(jì)算括號運(yùn)算
*/
private double parseBracket() throws Exception {
double result;//結(jié)果
//如果當(dāng)前標(biāo)記為左括號，則表示是一個(gè)括號運(yùn)算
if (this.token.equals("(")) {
//取下一個(gè)標(biāo)記
this.getToken();
//用加減法運(yùn)算計(jì)算子表達(dá)式的值
result = this.parseAddOrSub();
//如果當(dāng)前標(biāo)記不等于右括號，拋出括號不匹配異常
if (!this.token.equals(")")){
this.handleError(UNBALPARENS_ERROR);
}
//否則取下一個(gè)標(biāo)記
this.getToken();
} else {
//如果當(dāng)前標(biāo)記不是左括號，表示不是一個(gè)括號運(yùn)算，則用原子元素運(yùn)算計(jì)算子表達(dá)式的值
result = this.parseAtomElement();
}
return result;
}
/**
* 計(jì)算原子元素運(yùn)算，包括變量和數(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);
}
//取下一個(gè)標(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，則只取變量的第一個(gè)字符
* @param vname 變量名
* @throws Exception
*/
private double findVar(String vname) throws Exception {
//如果變量的第一個(gè)字符不是字母，則拋出語法異常
if (!Character.isLetter(vname.charAt(0))) {
handleError(SYNTAX_ERROR);
return 0.0;
}
//從實(shí)例變量數(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)前指針往前移動(dòng)
for (int i = 0; i < this.token.length(); i++) {
this.expIndex--;
}
}
/**
* 處理異常情況
* @param errorType 錯(cuò)誤類型
* @throws Exception
*/
private void handleError(int errorType) throws Exception {
//遇到異常情況時(shí)，根據(jù)錯(cuò)誤類型，取得異常提示信息，將提示信息封裝在異常中拋出
//可以考慮用自定義異常，而不用Exception
throw new Exception(ERROR_MESSAGES[errorType]);
}
/**
* 獲取下一個(gè)標(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)前字符是一個(gè)分隔符，則認(rèn)為這是一個(gè)分隔符標(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)前字符是一個(gè)字母，則認(rèn)為是一個(gè)變量標(biāo)記。
//將解析器指針往后移，直到遇到一個(gè)分隔符，之間的字符都是變量的組成部分
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)前字符是一個(gè)數(shù)字，則認(rèn)為當(dāng)前標(biāo)記的類型為數(shù)字
// 將解析器指針往后移，直到遇到一個(gè)分隔符，之間的字符都是該數(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;
}
}
/**
* 判斷一個(gè)字符是否為分隔符。
* 表達(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));
/**
* 一個(gè)簡單的表達(dá)式根據(jù)運(yùn)算時(shí)的優(yōu)先級從高到底為：
* （1）原子元素表達(dá)式，包括數(shù)字和變量；
* （2）括號表達(dá)式；
* （3）一元表達(dá)式，取數(shù)的負(fù)數(shù)；
* （4）指數(shù)表達(dá)式；
* （5）乘、除、取模表達(dá)式；
* （6）加、減表達(dá)式
* （7）賦值表達(dá)式；
* 因此，在計(jì)算一個(gè)表達(dá)式的值時(shí)，應(yīng)該按優(yōu)先級從高到底進(jìn)行運(yùn)算。
* 在本程序中，每個(gè)優(yōu)先級的表達(dá)式的運(yùn)算都用一個(gè)私有方法實(shí)現(xiàn)。在私有方法中，首先計(jì)算更高優(yōu)先級的表達(dá)式。
* 即采用了類似遞歸調(diào)用的方式，盡管在evaluate方法中最先調(diào)用的是優(yōu)先級最低的表達(dá)式的值，
* 但在實(shí)質(zhì)上卻是優(yōu)先級最高的表達(dá)式的私有方法最先被執(zhí)行完。這就保證了表達(dá)式的運(yùn)算是按照優(yōu)先級從高到底的順序執(zhí)行的。
*/
}
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -