jialisoftw

java实现递归下降的表达式解析器

本算法用java代码实现数值表达式的解析。

1、数值表达式的组成：

 

  • 数字
  • 运算符+、-、*、/、^、%、=
  • 圆括号(、)
  • 变量

 

其中^运算符表示求幂运算符（如10^2=100），=是赋值运算符。

2、本解析器必须满足的约束条件：

1)、所有变量都是单个字母（从A到Z的26个字母），字母不区分大小；

2)、假定所有的数字都是double类型，可以方便地修改解析器从而处理其他类型的值。

3、该算法将表达式被视为递归的数据结构，表达式定义的规则：

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

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

因数-->变量、数字或者表达式

4、表达式的分解

例如表达式：A * B - (C + 10)

包括如下这些独立的元素：A、*、B、-、(、C、+、10、)，这些元素叫做标识符（token），表示表达式中一个不可再分的独立单元。

5、代码

 

  1. <span style="font-size:16px;"><span style="font-family:'Microsoft YaHei';">package com.mmq.expression;  
  2. /** 
  3.  * @use 表达式解析器，支持变量 
  4.  * @ProjectName stuff 
  5.  * @Author <a href="mailto:mhmyqn@126.com">mumaoqiang</a></br> 
  6.  * @Date 2011-11-22 下午12:03:57 </br> 
  7.  * @FullName com.mmq.expression.Parser.java </br> 
  8.  * @JDK 1.6.0 </br> 
  9.  * @Version 1.0 </br> 
  10.  */  
  11. public class Parser {  
  12.     //These are the token types 标识符类型常量  
  13.     /**未定义的标识符*/  
  14.     final int NONE = 0;  
  15.     /**分隔符(包括运算符和括号)*/  
  16.     final int DELIMITER = 1;  
  17.     /**变量*/  
  18.     final int VARIABLE = 2;  
  19.     /**数值*/  
  20.     final int NUMBER = 3;  
  21.       
  22.     //These are the types of the syntax errors 语法错误类型常量  
  23.     /**所有导致非正则表达式的错误*/  
  24.     final int SYNTAX = 0;  
  25.     /**括号不对称错误*/  
  26.     final int UNBALPARENS = 1;  
  27.     /**没有表达式*/  
  28.     final int NOEXP = 2;  
  29.     /**除数为0*/  
  30.     final int DIVBYZERO = 3;  
  31.       
  32.     /** 
  33.      * This token indicates end-of-expression 表达式结束标识符  
  34.      * 标志解析器已达到表达式结尾 
  35.      */  
  36.     final String EOE = "\0";  
  37.       
  38.     /**refers to expression string 表达式字符串*/  
  39.     private String exp;  
  40.     /**current index into the expression 表达式中当前标识符的索引*/  
  41.     private int expIdx;  
  42.     /**holds current token 当前标识符*/  
  43.     private String token;  
  44.     /**holds token's type 标识符类型*/  
  45.     private int tokType;  
  46.       
  47.     /**Array for variables 变量数组*/  
  48.     private double vars[] = new double[26];  
  49.       
  50.     /** 
  51.      * Parser entry point 解析器入口 
  52.      * @param expstr 表达式字符串 
  53.      * @return 表达式的值 
  54.      * @throws ParserException 
  55.      */  
  56.     public double evaluate(String expstr) throws ParserException {  
  57.         double result;  
  58.         exp = expstr;  
  59.         expIdx = 0;  
  60.           
  61.         getToken();  
  62.         if(token.equals(EOE)){  
  63.             handleErr(NOEXP);//no expression present  
  64.         }  
  65.           
  66.         //Parse and evaluate the expression  
  67.         result = assignment();  
  68.           
  69.         if(!token.equals(EOE)){//last token must be EOE  
  70.             handleErr(SYNTAX);  
  71.         }  
  72.           
  73.         return result;  
  74.     }  
  75.     /** 
  76.      * Process an assignment 处理赋值语句 
  77.      * @return 
  78.      * @throws ParserException 
  79.      */  
  80.     private double assignment() throws ParserException {  
  81.         double result;  
  82.         int varIdx;  
  83.         int ttokType;  
  84.         String temptoken;  
  85.           
  86.         if(tokType == VARIABLE){  
  87.             //save old token  
  88.             temptoken = new String(token);  
  89.             ttokType = tokType;  
  90.               
  91.             //Compute the index of a variable.  
  92.             varIdx = Character.toUpperCase(token.charAt(0)) - 'A';  
  93.               
  94.             getToken();  
  95.             if(!token.equals("=")){  
  96.                 putBack();//return current token  
  97.                 //restore old token -- not an assignment  
  98.                 token = new String(temptoken);  
  99.                 tokType = ttokType;  
  100.             } else {  
  101.                 getToken();//  
  102.                 result = addOrSubtract();  
  103.                 vars[varIdx] = result;  
  104.                 return result;  
  105.             }  
  106.         }  
  107.           
  108.         return addOrSubtract();  
  109.     }  
  110.     /** 
  111.      * Add or subtract two terms. 两个数值加或减 
  112.      * @return 
  113.      * @throws ParserException 
  114.      */  
  115.     private double addOrSubtract() throws ParserException {  
  116.         char op;  
  117.         double result;  
  118.         double partialResult;  
  119.           
  120.         result = multiplyOrDivide();  
  121.           
  122.         while((op = token.charAt(0)) == '+' || op == '-'){  
  123.             getToken();  
  124.             partialResult = multiplyOrDivide();  
  125.             switch(op){  
  126.             case '-' :   
  127.                 result = result - partialResult;  
  128.                 break;  
  129.             case '+' :  
  130.                 result = result + partialResult;  
  131.                 break;  
  132.             }  
  133.         }  
  134.           
  135.         return result;  
  136.     }  
  137.       
  138.     /** 
  139.      * Multiply or divide two factors. 两个数值乘、除或取模 
  140.      * @return 
  141.      * @throws ParserException 
  142.      */  
  143.     private double multiplyOrDivide() throws ParserException {  
  144.         char op;  
  145.         double result;  
  146.         double partialResult;  
  147.           
  148.         result = exponent();  
  149.           
  150.         while((op = token.charAt(0)) == '*' || op == '/' || op == '%'){  
  151.             getToken();  
  152.             partialResult = exponent();  
  153.             switch(op){  
  154.             case '*' :   
  155.                 result = result * partialResult;  
  156.                 break;  
  157.             case '/' :  
  158.                 if(partialResult == 0.0){  
  159.                     handleErr(DIVBYZERO);  
  160.                 }  
  161.                 result = result / partialResult;  
  162.                 break;  
  163.             case '%' :  
  164.                 if(partialResult == 0.0){  
  165.                     handleErr(DIVBYZERO);  
  166.                 }  
  167.                 result = result % partialResult;  
  168.                 break;  
  169.             }  
  170.         }  
  171.           
  172.         return result;  
  173.     }  
  174.     /** 
  175.      * Process an exponent. 指数运算 
  176.      * @return 
  177.      * @throws ParserException 
  178.      */  
  179.     private double exponent() throws ParserException {  
  180.         double result;  
  181.         double partialResult;  
  182.         double ex;  
  183.         int t;  
  184.           
  185.         result = unary();  
  186.           
  187.         if(token.equals("^")){  
  188.             getToken();  
  189.             partialResult = exponent();  
  190.             ex = result;  
  191.             if(partialResult == 0.0){  
  192.                 result = 1.0;  
  193.             } else {  
  194.                 for(t = (int)partialResult - 1; t > 0; t-- ){  
  195.                     result = result * ex;  
  196.                 }  
  197.             }  
  198.         }  
  199.           
  200.         return result;  
  201.     }  
  202.     /** 
  203.      * Evaluate a unary + or -. 一元取正或一元取负运算 
  204.      * @return 
  205.      * @throws ParserException 
  206.      */  
  207.     private double unary() throws ParserException {  
  208.         double result;  
  209.         String op = "";  
  210.         //检查标识符是否为一元取正或一元取负运算符  
  211.         if(tokType == DELIMITER && token.equals("+") || token.equals("-")){  
  212.             op = token;  
  213.             getToken();  
  214.         }  
  215.           
  216.         result = parenthesize();  
  217.           
  218.         if(op.equals("-")){  
  219.             result = -result;  
  220.         }  
  221.           
  222.         return result;  
  223.     }  
  224.     /** 
  225.      * Process a parenthesized expression. 处理括号表达式 
  226.      * @return 
  227.      * @throws ParserException 
  228.      */  
  229.     private double parenthesize() throws ParserException {  
  230.         double result;  
  231.         //如果读取的是括号时递归调用addOrSubtract()  
  232.         if(token.equals("(")){  
  233.             getToken();  
  234.             result = addOrSubtract();  
  235.             if(!token.equals(")")){  
  236.                 handleErr(UNBALPARENS);  
  237.             }  
  238.             getToken();  
  239.         } else {  
  240.             result = atom();  
  241.         }  
  242.       
  243.         return result;  
  244.     }  
  245.     /** 
  246.      * Get the value of a number or variable. 获取一个数值字符串或变量的值 
  247.      * @return 
  248.      * @throws ParserException 
  249.      */  
  250.     private double atom() throws ParserException {  
  251.         double result = 0.0;  
  252.           
  253.         switch(tokType){  
  254.         case NUMBER :  
  255.             try {  
  256.                 result = Double.parseDouble(token);  
  257.             } catch (NumberFormatException e) {  
  258.                 handleErr(SYNTAX);  
  259.                 e.printStackTrace();  
  260.             }  
  261.             getToken();  
  262.             break;  
  263.         case VARIABLE :  
  264.             result = findVar(token);  
  265.             getToken();  
  266.             break;  
  267.         default :  
  268.             handleErr(SYNTAX);  
  269.             break;  
  270.         }  
  271.         return result;  
  272.     }  
  273.     /** 
  274.      * Return the value of a variable. 获取变量的值 
  275.      * @param vname 
  276.      * @return 
  277.      * @throws ParserException 
  278.      */  
  279.     private double findVar(String vname) throws ParserException {  
  280.         if(!Character.isLetter(vname.charAt(0))){  
  281.             handleErr(SYNTAX);  
  282.             return 0.0;  
  283.         }  
  284.         return vars[Character.toUpperCase(vname.charAt(0)) - 'A'];  
  285.     }  
  286.     /** 
  287.      * Return a token to the input stream. 
  288.      * 当标识为'='时，返回到标识符之前的索引位置 
  289.      */  
  290.     private void putBack(){  
  291.         if(token == EOE){  
  292.             return;  
  293.         }  
  294.         for(int i = 0; i < token.length(); i++){  
  295.             expIdx--;  
  296.         }  
  297.     }  
  298.     /** 
  299.      * Handle an error. 错误处理 
  300.      * @param error 
  301.      * @throws ParserException 
  302.      */  
  303.     private void handleErr(int error) throws ParserException {  
  304.         String[] err = {  
  305.                 "Unbalanced Parentheses",  
  306.                 "No Expression Parent",  
  307.                 "Division by zero"  
  308.         };  
  309.         throw new ParserException(err[error]);  
  310.     }  
  311.       
  312.     /** 
  313.      * 获得表达式中的下一个标识符 
  314.      */  
  315.     private void getToken(){  
  316.         tokType = NONE;  
  317.         token = "";  
  318.         //Check for end of expression  
  319.         if(expIdx == exp.length()){  
  320.             token = EOE;  
  321.             return;  
  322.         }  
  323.         //Skip over white space  
  324.         while(expIdx < exp.length() && Character.isWhitespace(exp.charAt(expIdx))){  
  325.             ++expIdx;  
  326.         }  
  327.         //Trailing whitespace ends expression  
  328.         if(expIdx == exp.length()){  
  329.             token = EOE;  
  330.             return;  
  331.         }  
  332.           
  333.         if(isDelim(exp.charAt(expIdx))){//is operator  
  334.             token += exp.charAt(expIdx);  
  335.             expIdx++;  
  336.             tokType = DELIMITER;  
  337.         } else if(Character.isLetter(exp.charAt(expIdx))){//is variable  
  338.             while(!isDelim(exp.charAt(expIdx))){  
  339.                 token += exp.charAt(expIdx);  
  340.                 expIdx++;  
  341.                 if(expIdx >= exp.length()){  
  342.                     break;  
  343.                 }  
  344.             }  
  345.             tokType = VARIABLE;  
  346.         } else if(Character.isDigit(exp.charAt(expIdx))){//is number  
  347.             while(!isDelim(exp.charAt(expIdx))){  
  348.                 token += exp.charAt(expIdx);  
  349.                 expIdx++;  
  350.                 if(expIdx >= exp.length()){  
  351.                     break;  
  352.                 }  
  353.             }  
  354.             tokType = NUMBER;  
  355.         } else {  
  356.             token = EOE;  
  357.             return;  
  358.         }  
  359.           
  360.     }  
  361.     /** 
  362.      * Return true if c is a delimiter. 判断是不是一个分隔符 
  363.      */  
  364.     private boolean isDelim(char c){  
  365.         if(" +-*/%^=()".indexOf(c) != -1){  
  366.             return true;  
  367.         }  
  368.         return false;  
  369.     }  
  370.       
  371. }</span></span>  

 

异常处理类：

 

  1. <span style="font-size:16px;"><span style="font-family:'Microsoft YaHei';">package com.mmq.expression;  
  2.   
  3. public class ParserException extends Exception {  
  4.     private static final long serialVersionUID = 8930730209321088339L;  
  5.     String errStr;  
  6.   
  7.     public ParserException(String str) {  
  8.         this.errStr = str;  
  9.     }  
  10.   
  11.     public String toString() {  
  12.         return errStr;  
  13.     }  
  14. }  
  15. </span></span>  

测试代码：

 

 

  1. <span style="font-size:16px;"><span style="font-family:'Microsoft YaHei';">package com.mmq.expression;  
  2.   
  3. import java.io.BufferedReader;  
  4. import java.io.IOException;  
  5. import java.io.InputStreamReader;  
  6.   
  7. public class ParserDemo {  
  8.     public static void main(String[] args) throws IOException {  
  9.         String expr;  
  10.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
  11.         Parser p = new Parser();  
  12.           
  13.         System.out.println("Enter an empty expression to stop.");  
  14.         for(;;){  
  15.             System.out.print("Enter expression: ");  
  16.             expr = br.readLine();  
  17.             if("".equals(expr)){  
  18.                 break;  
  19.             }  
  20.             try {  
  21.                 System.out.println("Result: " + p.evaluate(expr));  
  22.                 System.out.println();  
  23.             } catch (ParserException e) {  
  24.                 System.out.println(e);  
  25.             }  
  26.         }  
  27.     }  
  28. }  
  29. </span></span>  

测试输出如下：
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 飞猪一号 阅读(706) 评论(0)  编辑  收藏


只有注册用户登录后才能发表评论。
网站导航:
 

导航

<2012年10月>
日一二三四五六
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

统计

常用链接

留言簿

随笔档案

友情链接

搜索

最新评论

阅读排行榜

评论排行榜