Question

编写一个能够计算中缀表达式的java程序

，其中关于中缀表达式有如下的要求：
1）表达式中可以出现小数
2）表达式中只处理二元运算符
3）表达式中出现的运算符为：+、-、*、/、^(幂运算）、()，其中幂运算符的优先级别比*和/的高，但是其结合性为右结合

Answer 1

 
 
 
基本上就是先做词法分析（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 );
    }
}