用递归下降方法实现算术表达式解析器

　　对于形如2*2+2/1+3的算术表达式,如果不将优先级顺序考虑进去的话,那么解析如上的表达式十分容易,

a = get first operand
while(operand present){
op = get operator
b = get second operand
a = a op b
}

　　如果将优先级考虑进去的话,而且还使用上述算法,那么复杂度可想而知.在此,我用递归下降的方式实现解析有优先级的算术表达式.

　　在此解析的算术表达式,由如下元素组成:

• 　　 数字
• 运算符+ - * / %

　　运算符的优先级如下

　　% / * > + -

　　优先级相等的运算符从左向右顺序计算

　　在使用递归向下解析器时,表达式被视为递归的数据结构,那么所有的表达式可以由如下的规则生成

　　表达式 ->项 [+项][-项]

　　项 -> 因数 [*因数][/因数][%因数]

　　因数 -> 数字 或表达式

　　注意,上面的生成规则是以表达式中只包含+-*/%运算符且无变量为前提的,而且生成规则也包含了运算优先级,下面举例说明表达式的解析过程

　　2*3+2

　　有两个项,分别为2*3和2,前者包含两个因素2,3

　　下面以一个例子跟踪递归向下解析过程

　　2*3+3*4

1. 　　获得第一项2*3
2. 计算得到6
3. 获得第二项3*4
4. 计算得到12
5. 从第二项递归计算过程返回
6. 6+12计算得到18

　　为计算表达式的值,需要对表达式进行分解,例如2*3-4可以分解成2,*,3,-,4四个元素,这些元素在解析器术语中称为标识符,是一个不能再分的独立单元.为了将表达式分解一独立的元素单元,需要设计一个过程,该过程能从头至尾扫描整个表达式,顺序地返回每个元素,并且能够识别每个元素的,在本解析器,实现该功能的函数称为getToken.

　　本文的解析器封装在一个Parser的类中,为对getToken功能有个更好的理解,现说明它的第一部分

 
      1 
     // 
     解析器 
     
 
      2 
       
     class 
      Parser{
 
      3 
       
     //标识符 
     的类型种类 
     
 
      4 
       
     final 
       
     int 
      NONE  
     = 
       
     0 
     ;
 
      5 
       
     final 
       
     int 
      NUMBER 
     = 
       
     1 
     ;
 
      6 
       
     final 
       
     int 
      DELIMITER  
     = 
       
     2 
     ;
 
      7 
     
 
      8 
       
     // 
     异常的类型 
     
 
      9 
       
     final 
       
     int 
      NOEXP  
     = 
       
     0 
     ;
 
     10 
       
     final 
       
     int 
      SYNTAX  
     = 
       
     1 
     ;
 
     11 
       
     final 
       
     int 
      DIVBYZERO  
     = 
       
     2 
     ;
 
     12 
     
 
     13 
       
     final 
      String EOE  
     = 
       
     " 
      
     " 
     ; 
     // 
     标明表达式结尾 
     
 
     14 
       
     private 
       
     int 
      tokType; 
     // 
     用于存放标识符类型 
     
 
     15 
       
     private 
      String token; 
     // 
     用于存放标识符 
     
 
     16 
       
     private 
      String exp; 
     // 
     用于存放表达式 
     
 
     17 
       
     private 
       
     int 
      expIdx; 
     // 
     在表达式中的当前位置 
    

　　解析器解析表达式时,每个标识符必须有与之关联的标识符,本解析器只用到2种类型,分别为NUMBER,DELIMITER.此外NONE类型只是当标识符未定义时的一个占位符.

　　此外,Parser类还定义几个异常,其中NOEXP是当解析器解析时没有表达式,SYNTAX代表表达式不符合规则的错误,DIVBYZERO代表除数为0时的错误.

　　final变量EOE表示解析器己达到表达式的结尾.

　　被解析的表达式己字符串形式保存,exp保存该字符串的一个引用,exIdx保存下一个标识符在exp中的索引,初始值为0.当前标识符保存在token中,其类型则保存在tokType.这些变量都是private型,只允许解析器自己访问而不能被外部代码修改.

　　下面列出getToken函数的完整代码,每调用一次getToken(),将得到表达式的下一个标识,也就是exp[expIdx]后的一个标识.getToken()将标识符保存在token中,标识符类型则保存在tokType之中.

//获得下一个标识符

 
     private 
       
     void 
      getToken(){
token  
     = 
       
     "" 
     ;
tokType  
     = 
      NONE;

 
    

 
     //检查表达式是否到达末尾
 
     if 
     (expIdx  
     == 
      exp.length()){
token  
     = 
      EOE;
 
     return 
     ;
}

 
    

 
     //去掉空格
 
     while 
     (expIdx  
     < 
      exp.length()  
     && 
      Character.isWhitespace(exp.charAt(expIdx))) expIdx 
     ++ 
     ;

 
    

 
     //当表达式以空格结束
 
     if 
     (expIdx  
     >= 
      exp.length())
{
token  
     = 
      EOE;
 
     return 
     ;
}

 
     if 
     (isDelim(exp.charAt(expIdx))){//是运算符
token  
     += 
      exp.charAt(expIdx));
tokType  
     = 
      DELIMITER;
expIdx  
     ++ 
     ;
}  
     else 
       
     if 
     (Character.isDigit(exp.charAt(expIdx))){//是数字 
 
     while 
     ( 
     ! 
     isDelim(exp.charAt(expIdx))){
token  
     += 
      exp.charAt(expIdx); 
    

 
     expIdx ++;
 
     if 
     (expIdx  
     >= 
      exp.length())
 
     break 
     ;
} 
tokType  
     = 
      NUMBER;
}  
     else 
      {//不知名的字符结束字符串
token  
     = 
      EOE;
 
     return 
     ;
}
}

 
     private 
       
     boolean 
      isDelim( 
     char 
      c){//判断字符是否是运算符
 
     if 
     (( 
     " 
      +-*/% 
     " 
     ).indexOf(c)  
     != 
       
     - 
     1 
     )
 
     return 
       
     true 
     ;
 
     return 
       
     false 
     ;
}

} 
    

　　下面简单分析下getToken().getToken()首先做初始化工作,然后查看expIdx是否等于表达式的.由于expIdx保存的是解析器解析表达当前的进度,如果expIdx和exp.length(),那么表明解析器完成了表达式的解析.

　　如果解析器还能找到未处理的标识符,则解析过程继续进行.首先跳过下一个标识符之前所有的空格,如果表达式以空格结尾,则返回EOE结尾.根据exp[expIdx]后的一个字符的类型不同,getToken()对当前标识符的处理过程不同.如果一个字符为运算符,那么getToken()将当前标识符保存在token中,并将tokType设置为DELIMITER.若下一个字符为数字,token保存当前标识符,并将tokType设为NUMBER.如果下一个字符不为以上两种之一,则token保存EOE返回.

　　下面为解析器的代码,这个解析器只能解析由数字和运算符组成的表达式,其中运行符只包含+-*/%.

class ParserException extends Exception{
private String error;
public ParserException(String error){
this.error = error;
}
public String toString(){
return error;
}
}
class Parser {

final int NONE = 0;
final int NUMBER = 1;
final int DELIMITER = 2;

final int NOEXP = 0;
final int SYNTAX = 1;
final int DIVBYZERO = 2;


final String EOE = "";
private String exp;
private String token;
private int expIdx;
private int tokType;

//解析入口
public double evaluate(String expStr) throws ParserException{
this.exp = expStr;
this.expIdx = 0;
double result;

getToken();
if(token.equals(EOE)){
handleErr(NOEXP);
}

result = evalExp1();

if(!token.equals(EOE))
{
handleErr(SYNTAX);
}
return result;
}

//加或减
private double evalExp1() throws ParserException{
double result;
double partialResult;
char op;

result = evalExp2();

while((op = token.charAt(0)) == '+' || op == '-'){
getToken();
partialResult = evalExp2();
switch(op){
case '+':result += partialResult;break;
case '-':result -=partialResult;break;
}
}
return result;
}

//乘或除或取余
private double evalExp2() throws ParserException{
double result;
double partialResult;
char op;

result = atom();

while((op = token.charAt(0)) == '*' || op == '/' || op == '%'){
getToken();
partialResult = atom();
switch(op){
case '*':result *= partialResult;break;
case '/':if(partialResult == 0.0) handleErr(DIVBYZERO);result /=partialResult;break;
case '%':result %= partialResult;break;
}
}
return result;
}

//获得数的值
private double atom() throws ParserException{
double result = 0.0;

switch(tokType){
case NUMBER:try{
result = Double.parseDouble(token);
getToken();
}catch(NumberFormatException exc){
handleErr(SYNTAX);
}
break;
default:handleErr(SYNTAX);
}
return result;
}

//错误处理
private void handleErr(int error) throws ParserException{
String[] errs = {
"表达式不存在",
"表达式不符合规则",
"除数为0"};
throw new ParserException(errs[error]);
}
//获得下一个标识符
private void getToken(){
token = "";
tokType = NONE;

//检查表达式是否到达末尾
if(expIdx == exp.length()){
token = EOE;
return;
}

//去掉空格
while(expIdx < exp.length() && Character.isWhitespace(exp.charAt(expIdx))) expIdx++;

//当表达式以空格结束
if(expIdx >= exp.length())
{
token = EOE;
return;
}

if(isDelim(exp.charAt(expIdx))){//是运算符
token += exp.charAt(expIdx);
tokType = DELIMITER;
expIdx ++;
} else if(Character.isDigit(exp.charAt(expIdx))){//是数字 
while(!isDelim(exp.charAt(expIdx))){
token += exp.charAt(expIdx);
expIdx ++;
if(expIdx >= exp.length())
break;
} 
tokType = NUMBER;
} else {//不知名的字符结束字符串
token = EOE;
return;
}
}

private boolean isDelim(char c){//判断字符是否是运算符
if((" +-*/%").indexOf(c) != -1)
return true;
return false;
}
}

　在代码最开始部分声明了一个ParserException类,这是一个异常类,当解析器解析表达式时就会根据异常类抛出特定的,该异常的处理需要使用该解析器的主程序处理.使用该解析器的方法是先实例化一个Parser,然后将一个表达式字符串传入该实例的evaluate方法,该方法返回最终的结果.下面的代码 说明解析器的使用方法.

import java.io.*;
public class PDemo{
public static void main(String[] args){
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(expr.equals("")) break;
   			try{
   				System.out.println("Result :" +p.evaluate(expr));
   				System.out.println();
   			}catch(ParserException exc){
   				System.out.println(exc);
   			}
   			}
}
}

转载请指明出处 http://cnblogs.com/notifyer