strexpression.java

表达式解析程序

package expression;

import java.util.*;
import expression.DataInvalidException;
import expression.SOperator;
import expression.DOperator;

/**
 * <p>计算字符串表达式的值</p>
 * Vesion 1.0功能：
 * <p>Description:这个程序演示了如何计算字符串表达式的值，为了将问题简化，在这我
 * 只是计算符号格式要求的字符串表达式的值，也就是说不做数据合法性检测。你在测试
 * 的时候务必保证表达式正确.看上去应该是这个样子3+2*4+1-5.
 * 字符串中的数据必须是个合法的表达式，而且表达式中的运算符号只能是+ - * / ,
 * 数字只能是0123456789 ,容许有点”.”号 ,允许操作符和运算数之间有空格
 * </p>
 *
 * Vesion 2.0 功能
 * 引入了括号运算符
 *
 * Vesion 3.0 功能
 * 支持JAVA中所有算术运算，而且允许用户自定义运算符号.
 * <p>Copyright: Copyright (c) 2002</p>
 * <p>Company: 广州同望科技软件公司 </p>
 * @author 黄云辉
 * @version 2.0
 * @history:
 * 2002 -8 -11 上午 ： 完成了字符串表达式的计算。不支持括号运算符
 * 2002 -8 -11 晚上 ： 支持括号运算符.现在表达式可以是这个样子(3+4)*2+2*(3+3)
 * 2002 -8 -13 上午 ： 支持JAVA中所有算术运算，而且允许用户自定义运算符号.
 *
 *为了便于问题的阐述，在此我引入３个概念
 *基本运算因子
 *    不包括括号的合法字符串表达式（不管它多么复杂）就叫做基本运算因子。比如：
 *    30*20,20,30*3+20,log10+2^3,9*3*3/3+3+34*300/3  都是一个基本运算因子.
 *基本运算因子具有这样一条性质1：
 *    基本运算因子做任何运算后所得结果还是一个基本运算因子.
 *基本运算因子规约
 *    将多个基本运算因子化成一个基本运算因子的过程叫基本运算因子规约。
 *字符串表达式
 *    字符串表达式是“左括号（”，基本运算因子的，算术运算符和“右括号）”的集合体.
 * 字符串表达式的性质2：
 *　　１：合法字符串表达式中的“（”，“）”总是成队出现的(要么一个都没有，要么双双“飞“，呵呵)
 *　　２：最右的左括号相匹配的右括号离它最近.（近水楼台先得月）
 *
 *下面我们来看看一个合法字符串的基本形态:
 *  ( (基本运算因子１)* 基本运算因子２)＋基本运算因子３
 *  由性质１和性质２我们可以知道：
 *  我们可以采用一个递归函数将字符串表达式中的括号由里往外一层层“剥”掉，每剥
 *  掉一层都要进行一次基本因子规约。所有括号都“剥”光的时候也就是字符串表达式计
 *  算的最后一步——计算基本运算因子的结果.
 *  所以我们所要做的最重要的事就是计算基本运算因子的结果.
 *
 *  基本因子如何计算，请看下文。
 */

//---------------------------------------------------------------------
//说明： 用可以通过定义SOperatro/DOperator的实现类，并调用StringExpression
//中的操作符注册方法： registryOp进行注册，可以在字符串表达式中出现自定义
//操作符号. 自定义操作符号必须满足以下条件：
//   1： 必须是合法的标识符号
//   2： 不能包括这些符号 0,1,2,3,4,5,6,7,8,9,.,E,PI
//------------------------------------------------------------------------

/**
 *@decription:计算字符串表达式的值，容许带括号.
 *
 * 现在我门来看看如何实现括号运算符号
 * 先让我们看个带括号的字符串表达式:   ( ( ( 3+4 ) * 3 + 2 ) *4+3 ) *2
 * 兄台，有没有发现：
 *               1：“（”和“）”是成队出现的，都是n个（在这n=3）
 *               2:  可以看出：他们伴总是离自己最近的（近水楼台先得月，呵呵）
 *知道这些就好办了，我门可以用递归函数将括号一层层剥掉
 *下面我给你介绍3个将会用到的字符串函数，有请：
 *int	lastIndexOf(int ch, int fromIndex)
 *Returns the index within this string of the last occurrence of the specified
 * character, searching backward starting at the specified index.
 *
 *String	substring(int beginIndex, int endIndex)
 *Returns a new string that is a substring of this string.
 *int	indexOf(String str, int fromIndex)
 *Returns the index within this string of the first occurrence of the specified
 * substring, starting at the specified index.
 *哈哈，是不是爽歪了，有了这3个函数我们要做的只是写个很简单的递归函数就可以搞定了.
 *具体实施请参看源代码.
 */
public final class StrExpression {
  private  double result=0;
  private  Stack SourceStack = new Stack();//字符串表达式计算堆栈
  private  Stack TempStack = new Stack();


  //为了便于操作，用2个hash表来记录操作符信息（这个程序运行效率不是问题）
  private static Hashtable op_level = new Hashtable();//操作符信息(操作符号，操作符级别)
  private static Hashtable op_class = new Hashtable();//操作符信息(操作符号，计算类)

  public StrExpression () {
      //注册标准标准操作符号
      //第一级别运算符号注册
      this.registryOp("n!",1,"expression.SN");    //注册阶乘运算
      this.registryOp("dao",1,"expression.SDao"); //注册倒数运算
      this.registryOp("sin",1,"expression.SSin"); //注册正玄运算
      this.registryOp("cos",1,"expression.SCos"); //注册余玄运算
      this.registryOp("tan",1,"expression.STan"); //注册正切运算
      this.registryOp("sqrt",1,"expression.SSqrt"); //注册开方运算
      this.registryOp("log",1,"expression.SLog"); //注册对数运算
      this.registryOp("ln",1,"expression.SLn"); //注册e为底的对数运算
      this.registryOp("exp",1,"expression.SExp"); //注册指数运算
      this.registryOp("pin",1,"expression.SX2"); //注册平方运算
      this.registryOp("li",1,"expression.SX3"); //注册立方运算

      //第二级别运算符号注册
      this.registryOp("^",2,"expression.DPow"); //注册立方运算
      this.registryOp("*",2,"expression.DMul");//注册乘法运算
      this.registryOp("/",2,"expression.DDiv");//注册除法运算
      this.registryOp("%",2,"expression.DMod");//注册求余数运算
      //第三级别运算符号注册
      this.registryOp("+",3,"expression.DAdd");//注册加法运算
      this.registryOp("-",3,"expression.DDec");//注册减法运算
  }

  /**
   * @description: 注册操作符号信息
   * @param value String strOp 操作符
   * @param value int strLevel 操作符号级别(操作符号共分了3个级别1.2.3)
   * @param value String strClass 操作符号对应的操作类(带上包名)
   * @return void
   * 说明： 所以有的运算符都必须注册.
   */
    public static void registryOp(String strOp,int level,String strClass) {
     op_level.put(strOp,new Integer(level));
     op_class.put(strOp,strClass);
   }
   /**
    * 获取某操作符的运算级别
    * @param value String strOp(操作符)
    * @return 操作符级别
    */
   private int getLevel( String strOp ) {
      String strLevel = op_level.get(strOp).toString();
      if ( strLevel == null )
        return 0;
      else
        return Integer.parseInt(strLevel);
   }
   /**
    *判断给定字符串是否是已注册的操作符号
    * @param value strOp 待判断操作符号
    * @return 如果是已经注册的操作符号，者返回true,否则返回false。
    */
   private boolean isOp(String strOp) {
     return op_level.containsKey(strOp);
   }
  /**
   * 获取某操作符的运算类
   * @param value String strOp(操作符)
   * @return 操作符的运算类
   */
   private  String getClass( String strOp ) {
     return (String)op_class.get(strOp);
   }
  /**
   *将字符串表达式分解成运算符号和运算数，并将分解后的字符串保存到堆栈中
   * @param value String Expression: 字符串表达式
   * @return 运算数和运算符的集合。
   * 我采用这样一种方式来分解字符串运算符号：
   * 先在各运算符前后都插入‘#’号，然后用StringTokenzier对字符串进行分解.
   * 在这我采用了一种比较偷懒的方法插入”#“号(因为这个程序都运算效率没什么
   * 要求),具体如何插入，请看源代码.
   * 这个方法比较难看懂.我是通过搜索strExpression来定temp的插入位置，所以有个位置
   * 差的问题.如果您有什么不明白的地方随时可以和我联系.
   */
  private  Stack  splitStr(String strExpression) throws DataInvalidException {
     //----------------------------------------------
     HashSet hs = new HashSet();
     hs.addAll(op_level.keySet());
     hs.add("(");
     hs.add(")");
     //运算符号集合.
     //------------------------------------------------
     Iterator i = hs.iterator();//用来遍历运算符
     String strOp;
     StringBuffer temp = new StringBuffer(strExpression);//为了提高运算效率，引入该变量

     //----------------------------------------------------------------------------------
     //表答式最前面容许出现‘-’号（负号）,可以出现多个负，但没什么意义，所以目前程序
     //只许出现一个负号..
     String strHead = new String();//用来保存”-”号
     while(true) {//
        if ( temp.charAt(0)== '-'){
          temp.deleteCharAt(0);
          strHead +="-";
        } else break;
     }
    //----------------------------------------------------------------------------------
     if  ( temp.toString().trim().length() == 0)//只有负号的表达式
       throw new DataInvalidException("您输入的字符串表达式，不符合格式要求，"+
                                      "导致无法计算，请检测您的输入表达式");

     while ( i.hasNext() ) {
       int intInsertPos=0;//'#'的插入点.
       int intIndex=0;//搜索位置
       int intLen=0;//操作符的长度
       int intDiff=0;//记录位置差
       strOp = i.next().toString();//取出一个运算符
       intLen = strOp.length();
       strExpression = temp.toString();//temp的值会发生变化，每次插入符号前
       //要保证strExpression与temp值相同
       while(true) {
         intIndex =strExpression.indexOf(strOp,intIndex);
         if ( intIndex == -1 ) // 没有找到.
           break;
         intInsertPos = intIndex + intDiff;//设置插入位置
         if (intIndex ==0){
           temp.insert(intInsertPos+intLen,'#');//运算符号后面插入“#”
           intDiff ++;
         }else{
           temp.insert(intInsertPos,'#');//运算符号前插入“#”
           temp.insert(intInsertPos+intLen+1,'#');//运算符号后面插入“#”
           intDiff += 2;
         }
         intIndex +=  intLen;//调整搜索位置.

         }//end while(true);
     }// end while(i .hasNext());
      strExpression = strHead +temp.toString();
    // 创建个StringTokenizer对象用来提取表达式中的运算符号.
     Stack result = new Stack();
     StringTokenizer tool = new StringTokenizer(strExpression,"# ");
     while(tool.hasMoreElements())
            result.push(tool.nextElement());
     return result;
  }

  /**
   *@decription: 获取表达式的值.
   *@param value : 待计算的字符串表达式
   *@return : 字符串表达式的值.
   */
  public  double getValue(String value) throws DataInvalidException{
    int intIndexLeft;//最后一个“（”在字符串value 中的位置
    int intIndexRight;//第一个")"在字符串value中的位置.

    intIndexLeft = value.lastIndexOf("(");//取得左括号的索引
    if ( intIndexLeft == -1 ) {//value中不存在括号.
    try {
            result = parseValue(value);//如果当value不是个表达式时，会触发异常
        } catch (DataInvalidException die) {
           throw die;
      }//end try -catch
    }// end if
    else {
      intIndexRight = value.indexOf(")",intIndexLeft);//获取与左括号相匹配的右括号。
      //将表达式分成 左 中 右三串
      String strLeft = value.substring(0,intIndexLeft);//取左串
      String strTemp = value.substring(intIndexLeft+1,intIndexRight);//取中串
      double dblTemp;
      try {
         dblTemp = parseValue(strTemp);//计算中串的值.
      }catch(DataInvalidException die){
        throw die;
      }
      String strMid = new Double(dblTemp).toString();//得到新的中串
      String strRight= value.substring(intIndexRight+1);//获取右串
      value = strLeft + strMid + strRight;//重新组合字符串表达式 .
      getValue(value);//递归计算.
    } //end else
    return result;
  }//end getValue

    /**
     *@description:计算运算因子的值
     *@param value : 运算因子
     *@return: 运算因子的值
     */
    private  double parseValue( String value )throws DataInvalidException{

       this.SourceStack.clear();
       this.TempStack.clear();
      /*1:数据合法性检测
       *如果数据是非法的，则抛出DataInvalidException异常，为了
       *简化问题，在这不做数据合法性检测.如果您是做正式产品，这步不能省.
       */

      /*2：数据分解
       *将字符串的表达式分解成运算符号，和运算数的集合体,并将这些数据压入SourceStack堆栈中.
       *如果输入串是"32+33*14-1”那么分解后将会是"32","+","33"*","14","-","1"这个样子。
       *
       *分解方法：
       *为了便于说明问题，假设输入字符串是-32+2*4+3-1
       *我门的任务就是将“-32+2*4+3-1“分解成多个字符串: “-32”,”+”,”2”,”*”,”4”,”+”,+”3”,”-“,”1”.
       *兄弟门有没有发现：没个运算都是夹在2个数的中间，要是我们在运算符的前面和后面都插入字符“，”，就可以将数字
       *和运算符号分开.我门来看看插入符号’,’后字符串的形态： -32，+，2，*，4，*，3,-,1.
       *分解这类字符串是StringTokenizer的拿手把戏了，只要将分解标志设为”,”就可以搞定了.
       */
       try{
            SourceStack.addAll(this.splitStr(value));
       }catch (DataInvalidException die) {
         throw die;
       }
       //消除第1级别的运算符
        delLevel1();
       //将TempStack中的数据挪到SourceStack中，并清除TempStack中内容。这样做没什么特别
       //的原因，只是为了沿用上版的某些功能.
       SourceStack.addAll((Collection)TempStack.clone());
       TempStack.clear();

       //如果堆栈中只有一个数据则认为是一个合法数据，否则触发异常.
       if (SourceStack.size() == 1) {
         try {
            return Double.parseDouble(SourceStack.pop().toString());
         }catch (Exception e) {
           throw new DataInvalidException("您输入的字符串表达式，不符合格式要求，"+
                                          "导致无法计算，请检测您的输入表达式");
         }
       }
        //第2层处理，消除第2级别的运算符号
        delLevel2();
       //第三层处理，消除第三级别的运算符号
        Collections.reverse(TempStack);
        return delLevel3();//返回基本运算因子的运算结果 .

    }// end StringToValue

    //第1层处理，消除第1级别的运算符号
    private  void delLevel1() {
      //第1层处理，消除第1级别的运算符号
       String strTemp;//用来保存从SourceStack中弹出来的字符串.

       int intSize = SourceStack.size() ;
       for( int i=0 ;i< intSize;i++) {
          strTemp = (String)SourceStack.pop();
          if ( isOp(strTemp) ) {//如果是运算符号
          int intLevel = this.getLevel(strTemp);//获取运算级别
          if ( intLevel==1) {//
              Object objX = TempStack.pop();//取出运算数
              String strClass = getClass(strTemp);// 获取类包路径
              try {
                 Class clsCalculate = Class.forName(strClass);
                 SOperator cal = (SOperator)clsCalculate.newInstance();
                 TempStack.push(cal.calculate(objX));
              }catch(Exception e) {
                e.printStackTrace();
              }//end try-catch
            }//if (intLevel==1)
            if ( intLevel==3 ||
                 intLevel==2 ) {//将2,3级别运算符号进行压栈处理