java字符串應(yīng)用之表達(dá)式解析器

一、表達(dá)式的組成
    1、數(shù)字
    2、運(yùn)算符：+ - / * ^ % =
    3、圓括號(hào)
    4、變量
二、運(yùn)算符優(yōu)先級(jí)
    由高到低分別為：+-(正負(fù)號(hào))、^、*/%、+-、=
    優(yōu)先級(jí)相等的運(yùn)算符按照從左到右的順序計(jì)算
三、關(guān)鍵技術(shù)點(diǎn)
    1、確定運(yùn)算的優(yōu)先級(jí)，從高到低分別為：原子元素表達(dá)式，包括數(shù)字和變量；括號(hào)表達(dá)式；一元表達(dá)式，取數(shù)的負(fù)數(shù)；指數(shù)表達(dá)式；乘、除、取模表達(dá)式；加、減表達(dá)式；賦值表達(dá)式。
    2、對(duì)于每一級(jí)別的運(yùn)算，都由一個(gè)方法實(shí)現(xiàn)，在方法中先完成比自己高一級(jí)別的運(yùn)算，再處理本級(jí)別的運(yùn)算。因此，在計(jì)算整個(gè)表達(dá)式的主方法中，只需要調(diào)用最低級(jí)別的運(yùn)算的實(shí)現(xiàn)方法即可。
    3、確定表達(dá)式中的分隔符，（+、-、*、/、%、^、=、(、)、）。利用這些分隔符將表達(dá)式分成多段，每一段叫做一個(gè)token，分隔符也算token。
    4、用長(zhǎng)度為26的int數(shù)組vars存儲(chǔ)變量的值。
    5、Character的isWhitespace方法判斷字符是否為空白符，用于去掉表達(dá)式中的空白符。
    6、Character的isLetter方法判斷字符是否為字母，用于提取表達(dá)式中的變量
    7、Character的isDigit方法判斷字符是否為數(shù)字，用于獲取表達(dá)式中的數(shù)字
   
四、演示實(shí)例

/** *//**
 * 文件名ExpressionParser.java
 */
package book.oo.String;

/** *//**
 * 表達(dá)式解析器
 * @author joe
 *
 */
public class ExpressionParser ...{
    //4種標(biāo)記類(lèi)型
    public static final int NONE_TOKEN = 0;    //標(biāo)記為空或者結(jié)束符
    public static final int DELIMITER_TOKEN = 1;    //標(biāo)記為分隔符
    public static final int VARIABLE_TOKEN = 2;    //標(biāo)記為變量
    public static final int NUMBER_TOKEN = 3;    //標(biāo)記為數(shù)字
    
    //4種錯(cuò)誤類(lèi)型
    public static final int SYNTAX_ERROR = 0;    //語(yǔ)法錯(cuò)誤
    public static final int UNBALPARENS_ERROR = 1;    //括號(hào)沒(méi)有結(jié)束錯(cuò)誤
    public static final int NOEXP_ERROR = 2;    //表達(dá)式為空錯(cuò)誤
    public static final int DIVBYZERO_ERROR = 3;    //被0除錯(cuò)誤
    
    //針對(duì)4種錯(cuò)誤類(lèi)型定義的4個(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";
 
 private String exp; //表達(dá)式字符串
 private int expIndex; //解析器當(dāng)前指針在表達(dá)式中的位置
 private String token; //解析器當(dāng)前處理的標(biāo)記
 private int tokenType; //解析器當(dāng)前處理的標(biāo)記類(lèi)型
 private double[] vars = new double[26]; //變量數(shù)組

 /**
  *
  */
 public ExpressionParser() {
 }
 
 /**
  * 解析一個(gè)表達(dá)式，返回表達(dá)式的值
  */
 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)) {
   //沒(méi)有表達(dá)式異常
   this.handleError(NOEXP_ERROR);
  }
  
  result = this.parseAssign(); //處理賦值語(yǔ)句
  //處理完賦值語(yǔ)句，應(yīng)該就是表達(dá)式結(jié)束符，如果不是，則返回異常
  if(!this.token.equals(EOE)) {
   this.handleError(SYNTAX_ERROR);
  }
  return result;
 }
 
 /**
  * 處理賦值語(yǔ)句
  */
 public double parseAssign() throws Exception {
  double result; //結(jié)果
  int varIndex; //變量下標(biāo)
  String oldToken; //舊標(biāo)記
  int oldTokenType; //舊標(biāo)記的類(lèi)型
  
  //如果標(biāo)記類(lèi)型是變量
  if (this.tokenType == VARIABLE_TOKEN) {
   //保存當(dāng)前標(biāo)記
   oldToken = new String(this.token);
   oldTokenType = this.tokenType;
   //取得變量的索引，本解析器只支持一個(gè)字母的變量
   //如果用戶(hù)的變量字母長(zhǎng)度大于1，則取第一個(gè)字母當(dāng)作變量
   varIndex = Character.toUpperCase(this.token.charAt(0)) - 'A';
   
   //獲得下一個(gè)標(biāo)記
   this.getToken();
   //如果當(dāng)前標(biāo)記不是等號(hào)＝
   if(!this.token.equals("=")) {
    this.putBack(); //回滾
    //不是一個(gè)賦值語(yǔ)句，將標(biāo)記恢復(fù)到上一個(gè)標(biāo)記
    this.token = new String(oldToken);
    this.tokenType = oldTokenType;
   } else {
    //如果當(dāng)前標(biāo)記是等號(hào)＝，即給變量賦值，形式如：a = 3 + 5;
    //則計(jì)算等號(hào)后面表達(dá)式的值，然后再將得到的值賦給變量
    this.getToken();
    //因?yàn)榧訙p法的優(yōu)先級(jí)最低，所以計(jì)算加減法表達(dá)式
    result = this.parseAddOrSub();
    //將表達(dá)式的值賦給變量，并存在實(shí)例變量vars中
    this.vars[varIndex] = result;
    return result;
   }
  }
  //如果當(dāng)前標(biāo)記類(lèi)型不是變量，或者不是賦值語(yǔ)句，則用加減法計(jì)算表達(dá)式的值
  return this.parseAddOrSub();
 }
 
 /** 計(jì)算加減法表達(dá)式 */
 private double parseAddOrSub() throws Exception {
  char op; //運(yùn)算符
  double result; //結(jié)果
  double partialResult; //子表達(dá)式的結(jié)果
  
  result = this.pareseMulOrDiv(); //用乘除法計(jì)算當(dāng)前表達(dá)式的值
  //如果當(dāng)前標(biāo)記的第一個(gè)字母是加減號(hào)，則繼續(xù)進(jìn)行加減運(yùn)算
  while ((op = this.token.charAt(0)) == '+' || op == '-') {
   this.getToken(); //取下一個(gè)標(biāo)記
   //用乘除法計(jì)算當(dāng)前子表達(dá)式的值
   partialResult = this.pareseMulOrDiv();
   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 pareseMulOrDiv() throws Exception {
  char op; //運(yùn)算符
  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 == '%') {
   this.getToken(); //取下一標(biāo)記
   //用指數(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除異常
    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
    if(partialResult == 0.0) {
     this.handleError(DIVBYZERO_ERROR);
    }
    result = result % partialResult;
    break;
   }
  }
  return result;
 }
 
 /**
  * 計(jì)算指數(shù)表達(dá)式
  */
 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)記為“^”,則為指數(shù)運(yùn)算
  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ù)的值為個(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; //運(yùn)算符
  op = "";
  //如果當(dāng)前標(biāo)記類(lèi)型為分隔符，而且分隔符的值等于+或者-
  if((this.tokenType == DELIMITER_TOKEN) && this.token.equals("+") || this.token.equals("-")) {
   op = this.token;
   this.getToken();
  }
  //用括號(hào)運(yùn)算計(jì)算當(dāng)前子表達(dá)式的值
  result = this.parseBracket();
  if(op.equals("-")) {
   //如果運(yùn)算符為-，則表示負(fù)數(shù)，將子表達(dá)式的值變?yōu)樨?fù)數(shù)
   result = -result;
  }
  return result;
 }
 
 /**
  * 計(jì)算括號(hào)運(yùn)算
  */
 private double parseBracket() throws Exception {
  double result; //結(jié)果
  //如果當(dāng)前標(biāo)記為左括號(hào)，則表示是一個(gè)括號(hào)運(yùn)算
  if (this.token.equals("(")) {
   this.getToken(); //取下一標(biāo)記
   result = this.parseAddOrSub(); //用加減法運(yùn)算計(jì)算子表達(dá)式的值
   //如果當(dāng)前標(biāo)記不等于右括號(hào)，拋出括號(hào)不匹配異常
   if (!this.token.equals(")")) {
    this.handleError(UNBALPARENS_ERROR);
   }
   this.getToken(); //否則取下一個(gè)標(biāo)記
  } else {
   //如果不是左括號(hào)，表示不是一個(gè)括號(hào)運(yùn)算，則用原子元素運(yùn)算計(jì)算子表達(dá)式值
   result = this.parseAtomElement();
  }
  return result;
 }
 
 /**
  * 計(jì)算原子元素運(yùn)算，包括變量和數(shù)字
  */
 private double parseAtomElement() throws Exception {
  double result = 0.0; //結(jié)果
  
  switch(this.tokenType) {
  case NUMBER_TOKEN:
   //如果當(dāng)前標(biāo)記類(lèi)型為數(shù)字
   try {
    //將數(shù)字的字符串轉(zhuǎn)換成數(shù)字值
    result = Double.parseDouble(this.token);
   } catch (NumberFormatException exc) {
    this.handleError(SYNTAX_ERROR);
   }
   this.getToken(); //取下一個(gè)標(biāo)記
   break;
  case VARIABLE_TOKEN:
   //如果當(dāng)前標(biāo)記類(lèi)型是變量，則取變量的值
   result = this.findVar(token);
   this.getToken();
   break;
  default:
   this.handleError(SYNTAX_ERROR);
   break;
  }
  return result;
 }
 
 /**
  * 根據(jù)變量名獲取變量的值，如果變量名長(zhǎng)度大于1，則只取變量的第一個(gè)字符
  */
 private double findVar(String vname) throws Exception {
  if (!Character.isLetter(vname.charAt(0))) {
   this.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--;
  }
 }
 
 /**
  * 處理異常情況
  */
 private void handleError(int errorType) throws Exception {
  //遇到異常情況時(shí)，根據(jù)錯(cuò)誤類(lèi)型，取得異常提示信息，將提示信息封裝在異常中拋出
  throw new Exception(ERROR_MESSAGES[errorType]);
 }
 
 /**
  * 獲取下一個(gè)標(biāo)記
  */
 private void getToken() {
  //設(shè)置初始值
  this.token = "";
  this.tokenType = NONE_TOKEN;
  
  //檢查表達(dá)式是否結(jié)束，如果解析器當(dāng)前指針已經(jīng)到達(dá)了字符串長(zhǎng)度，
  //則表明表達(dá)式已經(jīng)結(jié)束，置當(dāng)前標(biāo)記的值為EOE
  if(this.expIndex == this.exp.length()) {
   this.token = EOE;
   return;
  }
  
  //跳過(guò)表達(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)記類(lèi)型賦值，并將指針后移
  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);
    }
   }
   this.tokenType = VARIABLE_TOKEN; //設(shè)置標(biāo)記類(lèi)型為變量
  } else if (Character.isDigit(currentChar)) {
   //如果當(dāng)前字符是一個(gè)數(shù)字，則認(rèn)為當(dāng)前標(biāo)記的類(lèi)型為數(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);
    }
   }
   this.tokenType = NUMBER_TOKEN; //設(shè)置標(biāo)記類(lèi)型為數(shù)字
  } else {
   //無(wú)法識(shí)別的字符，則認(rèn)為表達(dá)式結(jié)束
   this.token = EOE;
   return;
  }
 }
 
 /**
  * 判斷一個(gè)字符是否為分隔符
  * 表達(dá)式中的字符包括：
  * 加“＋”、減“－”、乘“*”、除“/”、取模“%”、指數(shù)“^”、賦值“＝”、左括號(hào)“（”、右括號(hào)“）”
  */
 private boolean isDelim(char c) {
  if (("+-*/%^=()".indexOf(c) != -1))
   return true;
  return false;
 }
 /**
  * @param args
  */
 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));

 }

}

輸出結(jié)果：

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

五、實(shí)例分析
    表達(dá)式的解析，實(shí)際就是一個(gè)表達(dá)式的分解過(guò)程。根據(jù)分隔符將表達(dá)式分成若干段。然后計(jì)算每一段的值，最后都會(huì)歸結(jié)到一個(gè)原子表達(dá)式。

posted on 2008-12-29 18:14 .VwV. 閱讀(1158) 評(píng)論(2)  編輯  收藏 所屬分類(lèi): java