VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > 编程开发 > C#教程 >
  • c#算述表达式求值

制作者:剑锋冷月 单位:无忧统计网,www.51stat.net
 

  算术表达式求值是一个经典的问题,很多学习编程的人都对此不陌生.本来我并不想写一个算术表达式求值的算法.在网上我看到了一篇文章,名叫<快速精确的对数学表达式求值>( 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 ) */
}



相关教程