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級別運算符號進行壓棧處理