算術表達式求值是一個經典的問題,很多學習編程的人都對此不陌生.本來我並不想寫一個算術表達式求值的算法.在網上我看到了一篇文章,名叫<快速精確的對數學表達式求值>( 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 ) */
}
