程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> C#算術表達式求值

C#算術表達式求值

編輯:關於C語言

算術表達式求值是一個經典的問題,很多學習編程的人都對此不陌生.本來我並不想寫一個算術表達式求值的算法.在網上我看到了一篇文章,名叫<快速精確的對數學表達式求值>( http://www-128.ibm.com/developerworks/cn/Java/j-w3eva/ ).才有興趣著一個玩玩.寫來寫去,覺得真得很經典.所以把我寫的代碼拿出來讓大家看看吧.因為時間較緊.所以變量名沒有做得很規范.

w3eavl是用Java寫得,我用C#把它重寫了一下.基本上能用,只是三角函數/反三角函數/雙曲線函數計算不太正常.誰對算術表達式求值感興趣可以和我聯系.原程序截圖:

我用C#重寫的( 實其是用他的代碼改為C#語法. )

誰想要W3Eval的Java代碼.和我改寫的C#代碼.可以和我聯系.下面要講的這個逆波蘭式求值算法的代碼也可以向我索取.請不要在商業中使用我的代碼.如果需要使用.請通知我.

我是的算法核心是逆波蘭式.還有就是w3eval這個算術表達式求值算法很不錯.但有一種表達式它會報錯.我想這是一個BUG:w3eavl不能計算"-( 3+5 )"的值.或者類似的計算式.

在生成逆波蘭式時,負號前綴是一個很大的麻煩.因為它和減號共用一個符號.我的做法是將負號前綴做一個預處理.負號在我這裡做為單目運算符求反.並將其替換還為"!".

為了可以擴充新的各種級別的運算符我為運算符的優先級做了一個Power( )函數.如果出現了新的優先級級別.只要在這裡調整就可以了.

後綴式求值本沒有什麼好說的.只是.單目運算和雙目運算還行三目運算對於它來說就不太好玩了.幸虧三目運算不多.不然,那都是事兒.

using System;
namespace XIYV.Compute
{
  /// <summary>
  /// SimpleRPN 的摘要說明.
  /// </summary>
  public sealed class SimpleRPN
  {
    private SimpleRPN( )
    {
    }

    /// <summary>
    /// Reverse Polish Notation 
    /// 算術逆波蘭表達式.生成. 
    /// </summary>
    /// <param name="s"></param>
    /// <returns></returns>
    private static
    string BuildingRPN( string s )
    {
      System.Text.StringBuilder sb=new System.Text.StringBuilder( s );
      System.Collections.Stack sk=new System.Collections.Stack( );
      System.Text.StringBuilder re=new System.Text.StringBuilder( );

      char c=' ';
      //sb.Replace( " ","" );
      //一開始,我只去掉了空格.後來我不想不支持函數和常量能濾掉的全OUT掉.
      for( int i=0;
      i<sb.Length;
      i++ )
      {
        c=sb[i];
        if( char.IsDigit( c ) )//數字當然要了.
        re.Append( c );
        //if( char.IsWhiteSpace( c )||
        char.IsLetter( c ) )//如果是空白,那麼不要.現在字母也不要.
        //continue;
        switch( c )//如果是其它字符...列出的要,沒有列出的不要.
        {
          case '+':
          case '-':
          case '*':
          case '/':
          case '%':
          case '^':
          case '!':
          case '( ':
          case ' )':
          case '.':
          re.Append( c );
          break;
          default:
          continue;
        }
      }
      sb=new System.Text.StringBuilder( re.ToString( ) );
      #region 對負號進行預轉義處理.負號變單目運算符求反.
      for( int i=0;i<sb.Length-1;i++ )
      if( sb[i]=='-'&&( i==0||sb[i-1]=='( ' ) )
      sb[i]='!';
      //字符轉義.
      #endregion
      #region 將中綴表達式變為後綴表達式.
      re=new System.Text.StringBuilder( );
      for( int i=0;
      i<sb.Length;
      i++ )
      {
        if( char.IsDigit( sb[i] )||sb[i]=='.' )//如果是數值.
        {
          re.Append( sb[i] );
          //加入後綴式
        }
        else if( sb[i]=='+'
        ||sb[i]=='-'
        ||sb[i]=='*'
        ||sb[i]=='/'
        ||sb[i]=='%'
        ||sb[i]=='^'
        ||sb[i]=='!' )//.
        {
          #region 運算符處理
          while ( sk.Count>0 ) //棧不為空時
          {
            c = ( char )sk.Pop( );
            //將棧中的操作符彈出.
            if ( c == '( ' ) //如果發現左括號.停.
            {
              sk.Push( c );
              //將彈出的左括號壓回.因為還有右括號要和它匹配.
              break;
              //中斷.
            }
            else
            {
              if( Power( c )<Power( sb[i] ) )//如果優先級比上次的高,則壓棧.
              {
                sk.Push( c );
                break;
              }
              else
              {
                re.Append( ' ' );
                re.Append( c );
              }
              //如果不是左括號,那麼將操作符加入後綴式中.
            }
          }
          sk.Push( sb[i] );
          //把新操作符入棧.
          re.Append( ' ' );
          #endregion
        }
        else if( sb[i]=='( ' )//基本優先級提升
        {
          sk.Push( '( ' );
          re.Append( ' ' );
        }
        else if( sb[i]==' )' )//基本優先級下調
        {
          while ( sk.Count>0 ) //棧不為空時
          {
            c = ( char )sk.Pop( );
            //pop Operator
            if ( c != '( ' )
            {
              re.Append( ' ' );
              re.Append( c );
              //加入空格主要是為了防止不相干的數據相臨產生解析錯誤.
              re.Append( ' ' );
            }
            else
            break;
          }
        }
        else
        re.Append( sb[i] );
      }
      while( sk.Count>0 )//這是最後一個彈棧啦.
      {
        re.Append( ' ' );
        re.Append( sk.Pop( ) );
      }
      #endregion
      re.Append( ' ' );
      return FormatSpace( re.ToString( ) );
      //在這裡進行一次表達式格式化.這裡就是後綴式了. 
    }

    /// <summary>
    /// 算術逆波蘭表達式計算. 
    /// </summary>
    /// <param name="s"></param>
    /// <returns></returns>
    public static
    string ComputeRPN( string s )
    {
      string S=BuildingRPN( s );

      string tmp="";
      System.Collections.Stack sk=new System.Collections.Stack( );

      char c=' ';
      System.Text.StringBuilder Operand=new System.Text.StringBuilder( );
      double x,y;
      for( int i=0;
      i<S.Length;
      i++ )
      {
        c=S[i];
        if( char.IsDigit( c )||c=='.' )
        {
          //數據值收集.
          Operand.Append( c );
        }
        else if( c==' '&&Operand.Length>0 )
        {
          #region 運算數轉換
          try
          {
            tmp=Operand.ToString( );
            if( tmp.StartsWith( "-" ) )//負數的轉換一定要小心...它不被直接支持.
            {
              //現在我的算法裡這個分支可能永遠不會被執行.
              sk.Push( -( ( double )Convert.ToDouble( tmp.Sub
              string( 1,tmp.Length-1 ) ) ) );
            }
            else
            {
              sk.Push( Convert.ToDouble( tmp ) );
            }
          }
          catch
          {
            return "發現異常數據值.";
          }
          Operand=new System.Text.StringBuilder( );
          #endregion
        }
        else if( c=='+'//運算符處理.雙目運算處理.
        ||c=='-'
        ||c=='*'
        ||c=='/'
        ||c=='%'
        ||c=='^' )
        {
          #region 雙目運算
          if( sk.Count>0 )/*如果輸入的表達式根本沒有包含運算符.或是根本就是空串.這裡的邏輯就有意義了.*/
          {
            y=( double )sk.Pop( );
          }
          else
          {
            sk.Push( 0 );
            break;
          }
          if( sk.Count>0 )
          x=( double )sk.Pop( );
          else
          {
            sk.Push( y );
            break;
          }
          switch( c )
          {
            case '+':
            sk.Push( x+y );
            break;
            case '-':
            sk.Push( x-y );
            break;
            case '*':
            sk.Push( x*y );
            break;
            case '/':
            sk.Push( x/y );
            break;
            case '%':
            sk.Push( x%y );
            break;
            case '^'://
            if( x>0 )//
            {
              我原本還想,如果被計算的數是負數,又要開真分數次方時如何處理的問題.後來我想還是算了吧.
              sk.Push( System.Math.Pow( x,y ) );
              //
            }
            //
            else//
            {
              //
              double t=y;
              //
              string ts="";
              //
              t=1/( 2*t );
              //
              ts=t.ToString( );
              //
              if( ts.ToUpper( ).LastIndexOf( 'E' )>0 )//
              {
                //
                ;
                //
              }
              //
            }
            break;
          }
          #endregion
        }
        else if( c=='!' )//單目取反. )
        {
          sk.Push( -( ( double )sk.Pop( ) ) );
        }
      }
      if( sk.Count>1 )
      return "運算沒有完成.";
      if( sk.Count==0 )
      return "結果丟失..";
      return sk.Pop( ).ToString( );
    }

    /// <summary>
    /// 優先級別測試函數. 
    /// </summary>
    /// <param name="opr"></param>
    /// <returns></returns>
    private static
    int Power( char opr )
    {
      switch( opr )
      {
        case '+':
        case '-':
        return 1;
        case '*':
        case '/':
        return 2;
        case '%':
        case '^':
        case '!':
        return 3;
        default:
        return 0;
      }
    }

    /// <summary>
    /// 規范化逆波蘭表達式.
    /// </summary>
    /// <param name="s"></param>
    /// <returns></returns>
    private static
    string FormatSpace( string s )
    {
      System.Text.StringBuilder ret=new System.Text.StringBuilder( );
      for( int i=0;
      i<s.Length;
      i++ )
      {
        if( !( s.Length>i+1&&s[i]==' '&&s[i+1]==' ' ) )
        ret.Append( s[i] );
        else
        ret.Append( s[i] );
      }
      return ret.ToString( );
      //.Replace( '!','-' );
    }
  }
  /*這裡給出的測試用例雖然不多.但如都能成功計算也不容易.( 6+9-8+5-8 )*( 2+5+8 )/7+5( 1+2+3+4+5+6+7+8+9 )*( 1+2+3+4+5+6+7+8+9 )/( 9+8+7+6 )*3-2-2+5/7-3( -3+4+9 )*( -3 )*7/( -5*2 )-( 6+9-8+5-8 )*( 2+5+8 )1+2+3+4+5+6+7+8+91*2*3*4*5*6*7*8*91-2-3-4-5-6-7-8-91/2/3/4/5/6/7/8/9( 6+9-8+5-8 )*( 2+5+8 ) */
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved