using system;
using system.collections;

namespace xxxxx
{
 public class expression
 {
  private expression() {}

  #region no01.表達式分割為arraylist形式
  /// <summary>
  /// 要求表達式以空格/t作為分隔符
  /// 轉換表達式折分為：
  /// 變量及數值 ,變量不允許為@
  /// 字符串“”
  /// 運算符號{+、-、*、/、++、+=、--、-=、*=、/=、!、!=、>、>=、>>、<、<=、<>、|、|=、||、&、&=、&&}
  /// 括號{包括（、）}
  /// </summary>
  /// <param name="sexpression"></param>
  /// <returns></returns>
  public static arraylist convertexpression(string sexpression)
  {
   arraylist alist = new arraylist();

   string word = null;
   int    i    = 0;
   string   c    = "";
 
   while(i < sexpression.length)
   {
    #region "
    if (word != null && word != "")
    if (word.substring(0,1) == "/"")
    {
     do
     {
      c = sexpression[i++].tostring();
      if (c == "/"") {  alist.add(word + c); word = c =  null; break;}
      else { word += c; c = null; }
     }while(i < sexpression.length);
    }
    if (i > sexpression.length -1)
    { alist.add(word); alist.add(c); word = c= null; break;}
    #endregion

    #region 字符判別
    switch (c = sexpression[i++].tostring())
    {
      #region ( )
     case "/"":
      if (i > sexpression.length -1)
      { alist.add(word); alist.add(c); word = c= null; break;}
      else
      {
       word = c; c= null;
       do
       { c = sexpression[i++].tostring();
        if (c == "/"") {  alist.add(word + c); word = c =  null; break;}
        else { word += c; c = null; }
       }while(i < sexpression.length );
       break;
      }

     case "(": alist.add(word); alist.add(c); word = c= null;  break;
     case ")": alist.add(word); alist.add(c); word = c= null;  break;
     case " ": alist.add(word); word = c= null;  break;
      #endregion

      #region + - * / %
     case "+":
      if (i > sexpression.length -1)
      { alist.add(word); alist.add(c); word = c= null; }
      else
       switch (c = sexpression[i++].tostring())
       {
        case "+": alist.add(word); alist.add("++"); word = c= null;  break;
        case "=": alist.add(word); alist.add("+="); word = c= null;  break;
        default : alist.add(word); alist.add("+");  word = c= null; i--; break;
       }
      break;
     case "-":
      if (i > sexpression.length -1)
      { alist.add(word);  alist.add(c);  word = c= null; }
      else
       switch (c = sexpression[i++].tostring())
       {
        case "-": alist.add(word); alist.add("--"); word = c= null;  break;
        case "=": alist.add(word); alist.add("-="); word = c= null;  break;
        default : alist.add(word); alist.add("-");  word = c= null;i--; break;
       }
      break;
     case "*":
      if (i > sexpression.length -1)
      { alist.add(word);  alist.add(c);  word = c= null; }
      else
       switch (c = sexpression[i++].tostring())
       {
        case "=": alist.add(word); alist.add("*="); word = c= null;  break;
        default : alist.add(word); alist.add("*");  word = c= null; i--; break;
       }
      break;
     case "/":
      if (i > sexpression.length -1)
      { alist.add(word);  alist.add(c); word = c= null; }
      else
       switch (c = sexpression[i++].tostring())
       {
        case "=": alist.add(word); alist.add("/="); word = c= null;  break;
        default : alist.add(word); alist.add("/");  word = c= null;i--; break;
       }
      break;
     case "%":
      if (i > sexpression.length -1)
      { alist.add(word);  alist.add(c);  word = c= null; }
      else
       switch (c = sexpression[i++].tostring())
       {
        case "=": alist.add(word); alist.add("%="); word = c= null;  break;
        default : alist.add(word); alist.add("%");  word = c= null; i--; break;
       }
      break;
      #endregion

      #region > < =
     case ">":
      if (i > sexpression.length -1)
      { alist.add(word); alist.add(c); word = c= null;  }
      else
       switch (c = sexpression[i++].tostring())
       {
        case ">": alist.add(word); alist.add(">>"); word = c= null;  break;
        case "=": alist.add(word); alist.add(">="); word = c= null;  break;
        default : alist.add(word); alist.add(">");  word =c= null;i--; break;
       }
      break;
     case "<":
      if (i > sexpression.length -1)
      { alist.add(word); alist.add(c); word = c= null;  }
      else
       switch (c = sexpression[i++].tostring())
       {
        case "<": alist.add(word); alist.add("<<"); word = c= null;  break;
        case ">": alist.add(word); alist.add("<>"); word = c= null;  break;
        case "=": alist.add(word); alist.add("<="); word = c= null;  break;
        default : alist.add(word); alist.add("<");  word = c =null;i--;  break;
       }
      break;
     case "=":
      if (i > sexpression.length -1)
      { alist.add(word);  alist.add(c);   word = c= null; }
      else
       switch (c = sexpression[i++].tostring())
       {
        case "=": alist.add(word); alist.add("=="); word = c= null;  break;
        default : alist.add(word); alist.add("=");  word = c=null;i--; break;
       }
      break;
      #endregion

      #region ! | &
     case "!":
      if (i > sexpression.length -1)
      { alist.add(word); alist.add(c); word = c= null; }
      else
       switch (c = sexpression[i++].tostring())
       {
        case "=": alist.add(word); alist.add("!="); word = c= null; break;
        default : alist.add(word); alist.add("!");  word = c=null;i--; break;
       }
      break;
     case "|":
      if (i > sexpression.length -1)
      { alist.add(word); alist.add(c); word = c= null; }
      else
       switch (c = sexpression[i++].tostring())
       {
        case "=": alist.add(word); alist.add("|="); word = c= null; break;
        case "|": alist.add(word); alist.add("||"); word = c= null; break;
        default : alist.add(word); alist.add("|");  word =c= null;i--; break;
       }
      break;
     case "&":
      if (i > sexpression.length -1)
      { alist.add(word); alist.add(c); word = c= null; }
      else
       switch (c = sexpression[i++].tostring())
       {
        case "=": alist.add(word); alist.add("&="); word = c= null;  break;
        case "&": alist.add(word); alist.add("&&"); word = c= null;  break;
        default : alist.add(word); alist.add("&");  word =c= null;i--; break;
       }
      break;
      #endregion
     default:
      word += c;
      break;
    }
    if (i == sexpression.length) alist.add(word);
    #endregion
   }

   arraylist alresult = new arraylist();
   foreach (object a in alist)
   {
    if (a == null) continue ;
    if (a.tostring().trim() == "") continue ;
    alresult.add(a);
   }
   return alresult;
  }

  /// <summary>
  /// 對返回的表達式，已經分好放于arraylist中的變量進行替換為實際常量
  /// </summary>
  /// <param name="alexpression"></param>
  /// <param name="mapvar"></param>
  /// <param name="mapvalue"></param>
  /// <returns></returns>
  public static arraylist convertexpression(arraylist alexpression, string mapvar, string mapvalue)
  {
   for (int i = 0; i < alexpression.count; i++)
   {
    if (alexpression[i].tostring() == mapvar ) { alexpression[i] = mapvalue; break; }    
   }
   return alexpression;
  }
  /// <summary>
  /// 對返回的表達式，已經分好放于arraylist中的變量進行替換為實際常量
  /// </summary>
  /// <param name="alexpression"></param>
  /// <param name="name"></param>
  /// <param name="mapvalue"></param>
  /// <returns></returns>
  public static arraylist convertexpression(arraylist alexpression, string[] mapvar, string[] mapvalue)
  {
   for (int i = 0; i < alexpression.count; i++)
   {
    for (int j = 0; j< mapvar.length; j++)
    {
     if (alexpression[i].tostring() == mapvar[j] )
     {
      alexpression[i] = mapvalue[j]; 
      break;
     }
//     system.console.writeline("expression: {0}  >>>  {1}",mapvar[j], mapvalue[j]);
    }    
   }
   return alexpression;
  }

  #endregion

  #region no02.后綴表達式方式 解析表達式
  /// <summary>
  /// 找出第一個閉括號
  /// </summary>
  /// <param name="alexpression"></param>
  /// <returns></returns>
  public static int find_first_rightbracket(arraylist alexpression)
  {
   for (int i = 0; i < alexpression.count; i++)
    {if (operatormap.checkrightbracket(alexpression[i].tostring())) return i; }
   return 0;
  }
  /// <summary>
  /// 找出匹配的開括號
  /// </summary>
  /// <param name="alexpression"></param>
  /// <param name="irightbracket"></param>
  /// <returns></returns>
  public static int find_near_leftbracket(arraylist alexpression, int irightbracket)
  {
   int i = irightbracket - 2;
   while ( i>= 0 )
   {
    if (operatormap.checkleftbracket(alexpression[i].tostring())) return i;
    i--;
   }
   return 0;
  }
  /// <summary>
  /// 中綴表達式轉換為后綴表達式
  /// </summary>
  /// <param name="alexpression"></param>
  /// <returns></returns>
  public static arraylist converttopostfix(arraylist alexpression)
  {
   arraylist aloutput = new arraylist();
   stack soperator = new stack();
   string word = null;
   int count = alexpression.count;
   int i = 0;
   while (i < count)
   {
    word = alexpression[i++].tostring();
    
    //·讀到左括號時總是將它壓入棧中
    if (operatormap.checkleftbracket(word))  
    { soperator.push(word); }
    else
    
     //·讀到右括號時，將*近棧頂的第一個左括號上面的運算符全部依次彈出，送至輸出隊列后，再丟棄左括號。
     if (operatormap.checkrightbracket(word))
    {
     while (true)
     {
      if (soperator.count == 0) break;
      string stop = soperator.peek().tostring();
      if (stop == "(" ) { soperator.pop(); break;}
      else aloutput.add(soperator.pop());
     }
    } 
    else 
     
     //·當讀到數字直接送至輸出隊列中
     if (operatormap.isvar(word))  
    { aloutput.add(word); }
    else

     //·當讀到運算符t時，
     //　　　　　a.將棧中所有優先級高于或等于t的運算符彈出，送到輸出隊列中；
     //　　　　　b.t進棧
     if (operatormap.checkoperator(word))
    { 
     while(soperator.count > 0)
     {
      string spop = soperator.peek().tostring();

      if (spop =="(" )  break;
      
      if (operatormap.getmaxprior(word,spop) >= 0)
      {
       //       spop = soperator.pop().tostring();
       aloutput.add(soperator.pop().tostring());
      }
      else
       break;
      //      system.console.writeline("xh{0}",spop);

     }
     soperator.push(word);
    }

    //    system.console.writeline("{0}",word.tostring());
   }

   //中綴表達式全部讀完后，若棧中仍有運算符，將其送到輸出隊列中
   while (soperator.count > 0)
   {
    string s = soperator.pop().tostring();
    aloutput.add(s);
//    system.console.writeline("{0}:{1}",soperator.count,s.tostring());
   }

   return aloutput;
  }

  /// <summary>
  /// 計算后綴表達式
  /// </summary>
  /// <param name="alexpression"></param>
  /// <returns></returns>
  public static object computepostfix(arraylist alexpression)
  {
   try
   {
    //·建立一個棧s
    stack s = new stack();
    int count = alexpression.count;
    int i = 0;
    while (i < count)
    {
     //·從左到右讀后綴表達式，讀到數字就將它轉換為數值壓入棧s中，
     string word = alexpression[i++].tostring();
     if (operatormap.isvar(word))
     {
      s.push(word); 
//      system.console.writeline("push:{0}",word);
     }
     else//讀到運算符則從棧中依次彈出兩個數分別到y和x，
      if (operatormap.checkoperator(word))
     {
      string y,x,sresult;
      if (!checkoneoperator(word))
      {
       y = s.pop().tostring();
       x = s.pop().tostring();
       //然后以“x 運算符 y”的形式計算機出結果，再壓加棧s中
       sresult = computetwo(x,y,word).tostring();
       s.push(sresult);
      }
      else
      {
       x = s.pop().tostring();
       sresult = computeone(x, word).tostring();
       s.push(sresult);
      }
     }
    }
    string spop = s.pop().tostring();
//    system.console.writeline("result:{0}",spop);
    return spop;
   }
   catch
   {
    system.console.writeline("result:表達式不符合運算規則!sorry!");
    return "sorry!error!";
   }

  }

  public static object computeexpression(string sexpression)
  {
   return expression.computepostfix(expression.converttopostfix(expression.convertexpression(sexpression)));
  }

  public static object computeexpression(string sexpression, string mapvar, string mapvalue)
  {
   return expression.computepostfix(expression.converttopostfix(expression.convertexpression(expression.convertexpression(sexpression),mapvar,mapvalue)));
  }

  public static object computeexpression(string sexpression, string[] mapvar, string[] mapvalue)
  {

   return expression.computepostfix(expression.converttopostfix(expression.convertexpression(expression.convertexpression(sexpression),mapvar,mapvalue)));
  }

  #endregion

  #region no03. 簡單無括號表達式的計算

  #region 檢查字符可以轉換的類型
  public static bool checknumber(string str)
  {
   try { convert.todouble(str); return true; }
   catch{return false;}
  }

  public static bool checkboolean(string str)
  {
   try { convert.toboolean(str); return true; }
   catch{return false;}
  }

  public static bool checkstring(string str)
  {
   try
   {
    str = str.replace("/"","");
    char c = (char)(str[0]);
    if ((c >= 'a') && (c <= 'z') ||  (c >= 'a') && (c <= 'z'))
     return true;
    else
     return false;
   }
   catch{ return false;}
  }
  public static bool checkoneoperator(string soperator)
  {
   if (soperator == "++" || soperator =="--" || soperator == "!")
    return true;
   else
    return false;
  }

  #endregion

  #region 雙目運算
  public static object computetwonumber(double dl, double dr, string so)
  {
   switch (so)
    {
     case "+": return (dl + dr);
     case "-": return (dl - dr);
     case "*": return (dl * dr);
     case "%": return (dl % dr);
     case "/": try{return (dl / dr);} 
        catch
        {
         return false;
         //return "computetwonumber ["+so+"] sorry!";
        }

     case "+=": return (dl += dr);
     case "-=": return (dl -= dr);
     case "*=": return (dl *= dr);
     case "/=": try{return (dl /= dr);}  
        catch
        {
         return false;
         //return "computetwonumber ["+so+"] sorry!";
        }

     case "=": return (dl == dr);
     case "==": return (dl == dr);
     case "!=": return (dl != dr);
     case "<>": return (dl != dr);
     case ">": return (dl.compareto(dr) > 0);
     case ">=": return (dl.compareto(dr) >= 0);
     case "<": return (dl.compareto(dr) < 0);
     case "<=": return (dl.compareto(dr) <= 0);

     case ">>": return (int)dl >> (int)dr;
     case "<<": return (int)dl << (int)dr;
     case "|": return (int)dl | (int)dr;
     case "&": return (int)dl & (int)dr;
     case "|=":
     {
      int il = (int)dl;
      int ir = (int)dr;
      return il |= ir;
     }
     case "&=":
     {
      int il = (int)dl;
      int ir = (int)dr;
      return il &= ir;
     }
     default : 
     return false;
      //return "computetwonumber ["+so+"] sorry!";
    }
  }

  public static object computetwoboolean(bool bl, bool br , string so)
  {
   switch (so)
   {
    case ">": return bl.compareto(br) > 0 ;
    case ">=": return bl.compareto(br) >= 0  ;
    case "<": return bl.compareto(br) < 0 ;
    case "<=": return bl.compareto(br) <= 0 ;
    case "=": return bl == br ;
    case "==": return bl == br ;
    case "!=": return bl != br ;
    case "<>": return bl != br ;

    case "||": return bl || br ;
    case "&&": return bl && br ;
    default : return false; 
     //return "computetwoboolean ["+so+"] sorry!";
   }
  }

  public static object computetwostring(string sl, string sr, string so)
  {
   switch (so)
   {
    case "+": return sl + sr;
    case "=": return (sl == sr);
    case "==": return (sl == sr);
    case "!=": return (sl != sr);
    case "<>": return (sl != sr);
    case ">": return (sl.compareto(sr) > 0);
    case ">=": return (sl.compareto(sr) >= 0);
    case "<": return (sl.compareto(sr) < 0);
    case "<=": return (sl.compareto(sr) <= 0);
    default : return false;
     //return "computetwostring ["+so+"] sorry!";
   }
  }

  public static object computetwo(string sl, string sr, string so)
  { 
   if (checknumber(sl))
   {
    if (checknumber(sr))  
     return computetwonumber(convert.todouble(sl),convert.todouble(sr),so);
    else
     if (checkstring(sr)) return computetwostring(sl,sr,so);
   }
   else if (checkboolean(sl))
   {
    if (checkboolean(sr))
     return computetwoboolean(convert.toboolean(sl),convert.toboolean(sr),so);
    else
     if (checkstring(sr)) return computetwostring(sl,sr,so);
   }
   else if (checkstring(sl))  return computetwostring(sl,sr,so);    

   return "computetwo ["+sl+"]["+so+"]["+sr+"] sorry!";
  }
  
  #endregion

  #region 單目運算
  public static object computeonenumber(double dou, string so)
  {
   switch (so)
   {
    case "++":  return (dou + 1);
    case "--":  return (dou - 1);
    default :  return false;
     //return "computeonenumber ["+so+"] sorry!";
   }
  }

  public static object computeonestring(string str, string so)
  {
   switch (so)
   {
    case "++":  return (str + str);
    default :  return false;
     //return "computeonestring ["+so+"] sorry!";
   }
  }

  public static object computeoneboolean(bool bo, string so)
  {
   switch (so)
   {
    case "!":  return (!bo);
    default :  return false;
     //   return "computeoneboolean ["+so+"] sorry!";
   }
  }

  public static object computeone(string str, string so)
  {
   if (checknumber(str))
    return computeonenumber(convert.todouble(str),so);
   if (checkboolean(str))
    return computeoneboolean(convert.toboolean(str),so);
   if (checkstring(str))
    return computeonestring(str,so);    
   return "computerone ["+str+"]["+so+"] sorry!";
  }

  #endregion

  #endregion

  #region no04. 實用工具類
  /// <summary>
  /// arraylist子集操作
  /// </summary>
  public class arraylistcopy
  {
   private arraylistcopy(){}
   /// <summary>
   /// 返回arraylist子集{l--r}內容
   /// </summary>
   /// <param name="alist"></param>
   /// <param name="ileft"></param>
   /// <param name="iright"></param>
   /// <returns></returns>
   public static arraylist copybewteento(arraylist alist, int ileft, int iright)
   {
    arraylist alresult = new arraylist();
    bool b = false;
    for (int i = ileft; i < iright; i++)
    {
     alresult.add(alist[i]);
     b = true;
    }
    if (b)  return alresult;
    else     return null;
   }

   /// <summary>
   /// 返回arraylist子集{l--r}的補集內容
   /// </summary>
   /// <param name="alist"></param>
   /// <param name="ileft"></param>
   /// <param name="iright"></param>
   /// <returns></returns>
   public static arraylist copynotbetweento(arraylist alist, int ileft, int iright)
   {
    arraylist alresult = new arraylist();
    bool b = false;
    for (int i = 0; i < ileft - 1; i++)
    {
     alresult.add(alist[i]);
     b = true;
    }

    if (b)
    {
     alresult.add("@");

     for (int i = iright + 1; i < alist.count; i++)
     {
      alresult.add(alist[i]);
      b = true;
     }
    }
    if (b)  return alresult;
    else  return null;
   }

   /// <summary>
   /// 統計字符串sin在str中出現的次數
   /// </summary>
   /// <param name="str"></param>
   /// <param name="sin"></param>
   /// <returns></returns>
   public static int  getsubstringcount(string str, string sin)
   {
    int i = 0;
    int ibit = 0;
    while (true)
    {
     ibit = str.indexof(sin, ibit);
     if (ibit > 0 )
     {
      ibit += sin.length;
      i++;
     }
     else
     {
      break;
     }
    }
    return i;
   }
  }

  /// <summary>
  /// 算符的優先級實體
  /// </summary>
  public class operatormap
  {
   public struct map
   {
    public int    priority;
    public string operator;
    public map(int iprior, string  soperator)
    {
     priority = iprior;
     operator = soperator;   
    }
   }
   private operatormap(){ }
   public static map[] map()
   {
    map[] om;
    om = new map[30];

    om[0] = new map(5,"*");
    om[1] = new map(5,"/");
    om[29] = new map(5,"%");

    om[2] = new map(10,"+");
    om[3] = new map(10,"-");
    
    om[4] = new map(20, ">");
    om[5] = new map(20, ">=");
    om[6] = new map(20, "<");
    om[7] = new map(20, "<=");
    om[8] = new map(20, "<>");
    om[9] = new map(20, "!=");
    om[10] = new map(20, "==");
    om[11] = new map(20, "=");

    om[12] = new map(41, "!");
    om[13] = new map(42, "||");
    om[14] = new map(43, "&&");

    om[15] = new map(40, "++");
    om[16] = new map(40, "--");
    om[17] = new map(40, "+=");
    om[18] = new map(40, "-=");
    om[19] = new map(40, "*=");
    om[20] = new map(40, "/=");
    om[21] = new map(40, "&");
    om[22] = new map(40, "|");
    om[23] = new map(40, "&=");
    om[24] = new map(40, "|=");
    om[25] = new map(40, ">>");
    om[26] = new map(40, "<<");

    om[27] = new map(3,"(");
    om[28] = new map(3,")");
    return om;
   }
   public static bool checkleftbracket(string str) { return ( str== "(");}
   public static bool checkrightbracket(string str){ return ( str== ")");}

   public static bool checkbracket(string str) { return ( str== "(" || str == ")"); }
   public static bool checkoperator(string scheck)
   {
    string[]  operator= {"+", "-", "*", "/", "%",
          ">", ">=", "<", "<=", "<>", "!=", "==", "=",
          "!", "||", "&&",
          "++", "--", "+=", "-=", "*=", "/=", 
          "&", "|", "&=", "|=", 
          ">>", "<<",
          ")", "("
         };
    bool bl = false;
    for (int i = 0; i < operator.length - 1; i++ ) { if (operator[i] == scheck){bl = true; break;} }
    return bl;
   }   
  
   public static map getmap(string operator)
   {
    if (checkoperator(operator)) foreach(map tmp in map()){ if (tmp.operator == operator) return tmp; }
    return new map(99,operator);
   }

   public static int getprior(string operator) { return getmap(operator).priority; }

   public static int getmaxprior(string loperator, string roperator)
   {return getmap(loperator).priority - getmap(roperator).priority;}

   public static bool isvar(string svar)
   {
    if ((svar[0] >= '0' && svar[0] <= '9' ) || (svar[0] >= 'a' && svar[0] <= 'z') || (svar[0] >='a' && svar[0] <='z') )
     return true;
    else
     return false;
   }
  }
  #endregion
 }

}