，其中关于中缀表达式有如下的要求：
1）表达式中可以出现小数
2）表达式中只处理二元运算符
3）表达式中出现的运算符为：+、-、*、/、^(幂运算）、()，其中幂运算符的优先级别比*和/的高，但是其结合性为右结合
參考答案:基本上就是先做词法分析（Lexical Analysis），然后再依优先级别把所有操作符和相关的操作数逐一化解成数值，
一直到整个表达式被化解成一个数值（或碰上表达式里的格式或数值范围错误）为止。
代码里，tokenize( ) 负责词法分析，剩下的都交给 evaluate( ) 。
evaluate( ) 能正确地求出空格数量和位置不规则的表达式
（比如 " -8-(+ 6*(1.5+723 )--9)+2^+3 ^- 5.2/16 "）。
注：
我没在 evaluate( ) 里捕捉任何异常，因为从里头冒出的任何异常都表示被传入的参数有错误。
（那意味着 evaluate( ) 的调用应该被放在 try block 里。）
import java.util.*;
class Expression {
public static void main( String[ ] args ) {
String expr = " -8-(+ 6*(1.5+723 )--9)+2^+3 ^- 5.2/16 ";
try {
System.out.println( evaluate( expr ) );
} catch ( Exception e ) {
System.out.println( "Syntax or numeric range error!" );
}
}
public static double evaluate( String expr ) {
List<String> tokens = tokenize( expr );
// Recursively eliminate all operators, in descending order of priority,
// till a numeric value is obtained from expr or till error is detected.
// first of all, get rid of all parentheses
int open = tokens.indexOf( "(" ),
close = tokens.lastIndexOf( ")" );
if ( open != -1 ) // parentheses mismatch will be caught by subList( )
return evaluate( join( tokens.subList( 0, open ) ) +
evaluate( join( tokens.subList( open + 1, close ) ) ) +
join( tokens.subList( close + 1, tokens.size( ) ) ) );
// now, get rid of binaries
String[ ][ ] binaries = { { "+", "-" }, // priority-0 is the lowest
{ "*", "/" },
{ "^" } }; // only one R2L (right-to-left)
List<String> listOfR2L = Arrays.asList( "^" );
for ( int priority = binaries.length - 1; priority >= 0; priority-- ) {
List binariesOfCurrentPriority = Arrays.asList( binaries[ priority ] );
int pos = Algorithms.findFirstOf( binariesOfCurrentPriority, tokens );
if ( listOfR2L.contains( binariesOfCurrentPriority.get( 0 ) ) )
pos = Algorithms.findLastOf( binariesOfCurrentPriority, tokens );
if ( pos != -1 )
return evaluate( join( tokens.subList( 0, pos - 1 ) ) +
operate( tokens.get( pos ),
tokens.get( pos - 1 ),
tokens.get( pos + 1 ) ) +
join( tokens.subList( pos + 2, tokens.size( ) ) ) );
}
// at this point, expr should be a numeric value convertible to double
return Double.parseDouble( tokens.get( 0 ) );
}
public static double operate( String operator, String a, String b ) {
double x = Double.parseDouble( a ), y = Double.parseDouble( b );
if ( operator.equals( "+" ) ) return x + y;
if ( operator.equals( "-" ) ) return x - y;
if ( operator.equals( "*" ) ) return x * y;
if ( operator.equals( "/" ) ) return x / y;
if ( operator.equals( "^" ) ) return Math.pow( x, y );
throw new IllegalArgumentException( "Unknown operator: " + operator );
}
public static boolean isArithmeticOperator( String s ) {
return s.length( ) == 1 && "+-*/^".indexOf( s ) != -1;
}
public static List<String> tokenize( String expr ) {
// split by (while "capturing" all) operators by positive look around
final String pattern = "(?=[-+*/^()])|(?<=[-+*/^()])";
List<String> tokens =
new ArrayList<String>( Arrays.asList( expr.split( pattern ) ) );
// Trim all tokens, discard empty ones, and join sign to number.
for ( int i = 0; i < tokens.size( ); i++ ) {
String current = tokens.get( i ).trim( ),
previous = i > 0 ? tokens.get( i - 1 ) : "+";
if ( current.length( ) == 0 )
tokens.remove( i-- ); // decrement, or miss the next token
else
if ( isArithmeticOperator( current ) &&
isArithmeticOperator( previous ) &&
i + 1 < tokens.size( ) ) {
tokens.set( i + 1, current + tokens.get( i + 1 ).trim( ) );
tokens.remove( i ); // no decrement, to skip the next token
} else
tokens.set( i, current );
}
return tokens;
}
private static String join( List<String> strings ) {
return strings.toString( ).replaceAll( "[,\\[\\]]", "" );
}
}
// see C++'s STL algorithm find_first_of( ) and find_last_of( ) for semantics
class Algorithms {
public static int findFirstOf( List what, List in ) {
List<Integer> locations = new ArrayList<Integer>( );
for ( Object o: what )
if ( in.contains( o ) )
locations.add( in.indexOf( o ) );
return locations.isEmpty( ) ? -1 : Collections.min( locations );
}
public static int findLastOf( List what, List in ) {
List<Integer> locations = new ArrayList<Integer>( );
for ( Object o: what )
if ( in.contains( o ) )
locations.add( in.lastIndexOf( o ) );
return locations.isEmpty( ) ? -1 : Collections.max( locations );
}
}
