国产精品毛片一区二区在线看,日本天堂影院在线视频,欧美一区二区高清在线观看

java實(shí)現(xiàn)遞歸下降的表達(dá)式解析器

本算法用java代碼實(shí)現(xiàn)數(shù)值表達(dá)式的解析。

1、數(shù)值表達(dá)式的組成：

數(shù)字
運(yùn)算符+、-、*、/、^、%、=
圓括號(hào)(、)
變量

其中^運(yùn)算符表示求冪運(yùn)算符（如10^2=100），=是賦值運(yùn)算符。

2、本解析器必須滿足的約束條件：

1)、所有變量都是單個(gè)字母（從A到Z的26個(gè)字母），字母不區(qū)分大小；

2)、假定所有的數(shù)字都是double類型，可以方便地修改解析器從而處理其他類型的值。

3、該算法將表達(dá)式被視為遞歸的數(shù)據(jù)結(jié)構(gòu)，表達(dá)式定義的規(guī)則：

表達(dá)式-->項(xiàng) [+項(xiàng)] [-項(xiàng)]

項(xiàng)-->因數(shù) [*因數(shù)] [/因數(shù)]

因數(shù)-->變量、數(shù)字或者表達(dá)式

4、表達(dá)式的分解

例如表達(dá)式：A * B - (C + 10)

包括如下這些獨(dú)立的元素：A、*、B、-、(、C、+、10、)，這些元素叫做標(biāo)識(shí)符（token），表示表達(dá)式中一個(gè)不可再分的獨(dú)立單元。

5、代碼

[java] view plain copy

package com.mmq.expression;
/**
* @use 表達(dá)式解析器，支持變量
* @ProjectName stuff
* @Author <a href="mailto:mhmyqn@126.com">mumaoqiang</a>
* @Date 2011-11-22 下午12:03:57
* @FullName com.mmq.expression.Parser.java
* @JDK 1.6.0
* @Version 1.0
*/
public class Parser {
//These are the token types 標(biāo)識(shí)符類型常量
/**未定義的標(biāo)識(shí)符*/
final int NONE = 0;
/**分隔符(包括運(yùn)算符和括號(hào))*/
final int DELIMITER = 1;
/**變量*/
final int VARIABLE = 2;
/**數(shù)值*/
final int NUMBER = 3;
//These are the types of the syntax errors 語法錯(cuò)誤類型常量
/**所有導(dǎo)致非正則表達(dá)式的錯(cuò)誤*/
final int SYNTAX = 0;
/**括號(hào)不對稱錯(cuò)誤*/
final int UNBALPARENS = 1;
/**沒有表達(dá)式*/
final int NOEXP = 2;
/**除數(shù)為0*/
final int DIVBYZERO = 3;
/**
* This token indicates end-of-expression 表達(dá)式結(jié)束標(biāo)識(shí)符
* 標(biāo)志解析器已達(dá)到表達(dá)式結(jié)尾
*/
final String EOE = "\0";
/**refers to expression string 表達(dá)式字符串*/
private String exp;
/**current index into the expression 表達(dá)式中當(dāng)前標(biāo)識(shí)符的索引*/
private int expIdx;
/**holds current token 當(dāng)前標(biāo)識(shí)符*/
private String token;
/**holds token's type 標(biāo)識(shí)符類型*/
private int tokType;
/**Array for variables 變量數(shù)組*/
private double vars[] = new double[26];
/**
* Parser entry point 解析器入口
* @param expstr 表達(dá)式字符串
* @return 表達(dá)式的值
* @throws ParserException
*/
public double evaluate(String expstr) throws ParserException {
double result;
exp = expstr;
expIdx = 0;
getToken();
if(token.equals(EOE)){
handleErr(NOEXP);//no expression present
}
//Parse and evaluate the expression
result = assignment();
if(!token.equals(EOE)){//last token must be EOE
handleErr(SYNTAX);
}
return result;
}
/**
* Process an assignment 處理賦值語句
* @return
* @throws ParserException
*/
private double assignment() throws ParserException {
double result;
int varIdx;
int ttokType;
String temptoken;
if(tokType == VARIABLE){
//save old token
temptoken = new String(token);
ttokType = tokType;
//Compute the index of a variable.
varIdx = Character.toUpperCase(token.charAt(0)) - 'A';
getToken();
if(!token.equals("=")){
putBack();//return current token
//restore old token -- not an assignment
token = new String(temptoken);
tokType = ttokType;
} else {
getToken();//
result = addOrSubtract();
vars[varIdx] = result;
return result;
}
}
return addOrSubtract();
}
/**
* Add or subtract two terms. 兩個(gè)數(shù)值加或減
* @return
* @throws ParserException
*/
private double addOrSubtract() throws ParserException {
char op;
double result;
double partialResult;
result = multiplyOrDivide();
while((op = token.charAt(0)) == '+' || op == '-'){
getToken();
partialResult = multiplyOrDivide();
switch(op){
case '-' :
result = result - partialResult;
break;
case '+' :
result = result + partialResult;
break;
}
}
return result;
}
/**
* Multiply or divide two factors. 兩個(gè)數(shù)值乘、除或取模
* @return
* @throws ParserException
*/
private double multiplyOrDivide() throws ParserException {
char op;
double result;
double partialResult;
result = exponent();
while((op = token.charAt(0)) == '*' || op == '/' || op == '%'){
getToken();
partialResult = exponent();
switch(op){
case '*' :
result = result * partialResult;
break;
case '/' :
if(partialResult == 0.0){
handleErr(DIVBYZERO);
}
result = result / partialResult;
break;
case '%' :
if(partialResult == 0.0){
handleErr(DIVBYZERO);
}
result = result % partialResult;
break;
}
}
return result;
}
/**
* Process an exponent. 指數(shù)運(yùn)算
* @return
* @throws ParserException
*/
private double exponent() throws ParserException {
double result;
double partialResult;
double ex;
int t;
result = unary();
if(token.equals("^")){
getToken();
partialResult = exponent();
ex = result;
if(partialResult == 0.0){
result = 1.0;
} else {
for(t = (int)partialResult - 1; t > 0; t-- ){
result = result * ex;
}
}
}
return result;
}
/**
* Evaluate a unary + or -. 一元取正或一元取負(fù)運(yùn)算
* @return
* @throws ParserException
*/
private double unary() throws ParserException {
double result;
String op = "";
//檢查標(biāo)識(shí)符是否為一元取正或一元取負(fù)運(yùn)算符
if(tokType == DELIMITER && token.equals("+") || token.equals("-")){
op = token;
getToken();
}
result = parenthesize();
if(op.equals("-")){
result = -result;
}
return result;
}
/**
* Process a parenthesized expression. 處理括號(hào)表達(dá)式
* @return
* @throws ParserException
*/
private double parenthesize() throws ParserException {
double result;
//如果讀取的是括號(hào)時(shí)遞歸調(diào)用addOrSubtract()
if(token.equals("(")){
getToken();
result = addOrSubtract();
if(!token.equals(")")){
handleErr(UNBALPARENS);
}
getToken();
} else {
result = atom();
}
return result;
}
/**
* Get the value of a number or variable. 獲取一個(gè)數(shù)值字符串或變量的值
* @return
* @throws ParserException
*/
private double atom() throws ParserException {
double result = 0.0;
switch(tokType){
case NUMBER :
try {
result = Double.parseDouble(token);
} catch (NumberFormatException e) {
handleErr(SYNTAX);
e.printStackTrace();
}
getToken();
break;
case VARIABLE :
result = findVar(token);
getToken();
break;
default :
handleErr(SYNTAX);
break;
}
return result;
}
/**
* Return the value of a variable. 獲取變量的值
* @param vname
* @return
* @throws ParserException
*/
private double findVar(String vname) throws ParserException {
if(!Character.isLetter(vname.charAt(0))){
handleErr(SYNTAX);
return 0.0;
}
return vars[Character.toUpperCase(vname.charAt(0)) - 'A'];
}
/**
* Return a token to the input stream.
* 當(dāng)標(biāo)識(shí)為'='時(shí)，返回到標(biāo)識(shí)符之前的索引位置
*/
private void putBack(){
if(token == EOE){
return;
}
for(int i = 0; i < token.length(); i++){
expIdx--;
}
}
/**
* Handle an error. 錯(cuò)誤處理
* @param error
* @throws ParserException
*/
private void handleErr(int error) throws ParserException {
String[] err = {
"Unbalanced Parentheses",
"No Expression Parent",
"Division by zero"
};
throw new ParserException(err[error]);
}
/**
* 獲得表達(dá)式中的下一個(gè)標(biāo)識(shí)符
*/
private void getToken(){
tokType = NONE;
token = "";
//Check for end of expression
if(expIdx == exp.length()){
token = EOE;
return;
}
//Skip over white space
while(expIdx < exp.length() && Character.isWhitespace(exp.charAt(expIdx))){
++expIdx;
}
//Trailing whitespace ends expression
if(expIdx == exp.length()){
token = EOE;
return;
}
if(isDelim(exp.charAt(expIdx))){//is operator
token += exp.charAt(expIdx);
expIdx++;
tokType = DELIMITER;
} else if(Character.isLetter(exp.charAt(expIdx))){//is variable
while(!isDelim(exp.charAt(expIdx))){
token += exp.charAt(expIdx);
expIdx++;
if(expIdx >= exp.length()){
break;
}
}
tokType = VARIABLE;
} else if(Character.isDigit(exp.charAt(expIdx))){//is number
while(!isDelim(exp.charAt(expIdx))){
token += exp.charAt(expIdx);
expIdx++;
if(expIdx >= exp.length()){
break;
}
}
tokType = NUMBER;
} else {
token = EOE;
return;
}
}
/**
* Return true if c is a delimiter. 判斷是不是一個(gè)分隔符
*/
private boolean isDelim(char c){
if(" +-*/%^=()".indexOf(c) != -1){
return true;
}
return false;
}
}

異常處理類：

[java] view plain copy

package com.mmq.expression;
public class ParserException extends Exception {
private static final long serialVersionUID = 8930730209321088339L;
String errStr;
public ParserException(String str) {
this.errStr = str;
}
public String toString() {
return errStr;
}
}

測試代碼：

[java] view plain copy

package com.mmq.expression;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class ParserDemo {
public static void main(String[] args) throws IOException {
String expr;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Parser p = new Parser();
System.out.println("Enter an empty expression to stop.");
for(;;){
System.out.print("Enter expression: ");
expr = br.readLine();
if("".equals(expr)){
break;
}
try {
System.out.println("Result: " + p.evaluate(expr));
System.out.println();
} catch (ParserException e) {
System.out.println(e);
}
}
}
}

測試輸出如下：

Enter an empty expression to stop.
Enter expression: a=10
Result: 10.0

Enter expression: b=5
Result: 5.0

Enter expression: a+(b-2)/3-5
Result: 6.0

Enter expression:

posted on 2012-10-11 09:13 飛豬一號(hào) 閱讀(715) 評(píng)論(0) 編輯收藏

新用戶注冊刷新評(píng)論列表


只有注冊用戶登錄后才能發(fā)表評(píng)論。




網(wǎng)站導(dǎo)航: 博客園 IT新聞 Chat2DB C++博客博問管理

jialisoftw

java實(shí)現(xiàn)遞歸下降的表達(dá)式解析器

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿

隨筆檔案

友情鏈接

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜