|
|
 |
|
 |
本文由中国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
{
public sealed class SimpleRPN
{
private SimpleRPN( )
{
}
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=' ';
for( int i=0;
i<sb.Length;
i++ )
{
c=sb[i];
if( char.IsDigit( c ) ) re.Append( c );
char.IsLetter( c ) ) 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( );
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( ) );
}
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( );
}
private static
int Power( char opr )
{
switch( opr )
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '%':
case '^':
case '!':
return 3;
default:
return 0;
}
}
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( );
}
}
/*这里给出的测试用例虽然不多.但如都能成功计算也不容易.( 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 ) */
}
本文由中国C#技术学习中心整理 如果你对本文有不明之处请到技术论坛讨论!
|
|
