expression.java

FuncPlotter is a combined Java application and applet for displaying two-dimensional plots of explic

    private static Token alphaToToken( String str,
                                       int    pos )
        throws Expression.Exception
    {
        if ( str.equals( VARIABLE_STR ) )
            return new Token( Token.Type.VARIABLE, pos );
        Keyword keyword = Keyword.get( str );
        if ( keyword == null )
            throw new Expression.Exception( ErrorId.UNRECOGNISED_TOKEN, str, pos );
        return new Token( Token.Type.KEYWORD, pos, keyword );
    }

    //------------------------------------------------------------------

    private static Token symbolToToken( String str,
                                        int    pos )
        throws Expression.Exception
    {
        if ( str.length( ) > 1 )
            throw new Expression.Exception( ErrorId.UNRECOGNISED_TOKEN, str, pos );
        return new Token( Token.Type.SYMBOL, pos, Symbol.get( str.charAt( 0 ) ) );
    }

    //------------------------------------------------------------------

    private static List<Token> toTokens( String str )
        throws Expression.Exception
    {
        List<Token> tokens = new ArrayList<Token>( );
        StringBuilder tokenBuf = new StringBuilder( );
        int charIndex = 0;
        int tokenPos = 0;
        NumericState numericState = NumericState.SIGNIFICAND;
        LexState state = LexState.WHITESPACE;
        while ( state != LexState.DONE )
        {
            char ch = (charIndex >= str.length( )) ? 0 : str.charAt( charIndex );
            switch ( state )
            {
                case WHITESPACE:
                {
                    if ( isWhitespace( ch ) )
                    {
                        ++charIndex;
                        break;
                    }
                    state = getLexState( ch );
                    if ( state != LexState.INVALID )
                        tokenPos = charIndex;
                    break;
                }

                case NUMERIC:
                {
                    boolean valid = false;
                    switch ( numericState )
                    {
                        case SIGNIFICAND:
                            if ( isNumeric( ch ) )
                                valid = true;
                            else
                            {
                                if ( (ch == 'E') || (ch == 'e') )
                                {
                                    valid = true;
                                    numericState = NumericState.EXP_INDICATOR;
                                }
                            }
                            break;

                        case EXP_INDICATOR:
                            if ( isNumeric( ch ) || (ch == '+') || (ch == '-') )
                                valid = true;
                            numericState = NumericState.EXPONENT;
                            break;

                        case EXPONENT:
                            if ( isNumeric( ch ) )
                                valid = true;
                            break;
                    }
                    if ( valid )
                    {
                        tokenBuf.append( ch );
                        ++charIndex;
                        break;
                    }
                    numericState = NumericState.SIGNIFICAND;
                    state = getLexState( ch );
                    if ( state != LexState.INVALID )
                    {
                        tokens.add( numberToToken( tokenBuf.toString( ), tokenPos ) );
                        tokenBuf.delete( 0, tokenBuf.length( ) );
                        tokenPos = charIndex;
                    }
                    break;
                }

                case ALPHA:
                {
                    if ( isAlpha( ch ) )
                    {
                        tokenBuf.append( ch );
                        ++charIndex;
                        break;
                    }
                    state = getLexState( ch );
                    if ( state != LexState.INVALID )
                    {
                        tokens.add( alphaToToken( tokenBuf.toString( ), tokenPos ) );
                        tokenBuf.delete( 0, tokenBuf.length( ) );
                        tokenPos = charIndex;
                    }
                    break;
                }

                case SYMBOL:
                {
                    if ( isSymbol( ch ) )
                    {
                        if ( tokenBuf.length( ) > 0 )
                        {
                            tokens.add( symbolToToken( tokenBuf.toString( ), tokenPos ) );
                            tokenBuf.delete( 0, tokenBuf.length( ) );
                            tokenPos = charIndex;
                        }
                        tokenBuf.append( ch );
                        ++charIndex;
                        break;
                    }
                    state = getLexState( ch );
                    if ( state != LexState.INVALID )
                    {
                        tokens.add( symbolToToken( tokenBuf.toString( ), tokenPos ) );
                        tokenBuf.delete( 0, tokenBuf.length( ) );
                        tokenPos = charIndex;
                    }
                    break;
                }

                case EOL:
                    tokens.add( new Token( Token.Type.EOF, tokenPos ) );
                    state = LexState.DONE;
                    break;

                case INVALID:
                    throw new Expression.Exception( ErrorId.CHAR_NOT_ALLOWED, Character.toString( ch ),
                                                    charIndex );
            }
        }

        return tokens;
    }

    //------------------------------------------------------------------

    private static Node parse( List<Token> tokens )
        throws Expression.Exception
    {
        Node tree = new Node( );
        getSubtree( tokens, 0, tree, false );
        tree.lChild.removeNullNodes( );
        return tree;
    }

    //------------------------------------------------------------------

    private static int getSubtree( List<Token> tokens,
                                   int         tokenIndex,
                                   Node        tree,
                                   boolean     subexpression )
        throws Expression.Exception
    {
        Node activeNode = tree;
        ParseState state = ParseState.OPERAND;
        while ( state != ParseState.DONE )
        {
            Token token = tokens.get( tokenIndex++ );
            switch ( state )
            {
                case OPERAND:
                {
                    if ( activeNode.isTerminal( ) )
                        throw new ParserError( 1, token.pos );
                    switch ( token.type )
                    {
                        case NUMBER:
                        {
                            Node node = new Node( activeNode, Node.Type.CONSTANT, token.number );
                            if ( !activeNode.append( node ) )
                                throw new ParserError( 2, token.pos );
                            activeNode = node;
                            state = ParseState.OPERATOR;
                            break;
                        }

                        case VARIABLE:
                        {
                            Node node = new Node( activeNode, Node.Type.VARIABLE );
                            if ( !activeNode.append( node ) )
                                throw new ParserError( 3, token.pos );
                            activeNode = node;
                            state = ParseState.OPERATOR;
                            break;
                        }

                        case KEYWORD:
                        {
                            if ( token.keyword == Keyword.E )
                            {
                                Node node = new Node( activeNode, Node.Type.CONSTANT, Math.E );
                                if ( !activeNode.append( node ) )
                                    throw new ParserError( 4, token.pos );
                                activeNode = node;
                                state = ParseState.OPERATOR;
                                break;
                            }
                            if ( token.keyword == Keyword.PI )
                            {
                                Node node = new Node( activeNode, Node.Type.CONSTANT, Math.PI );
                                if ( !activeNode.append( node ) )
                                    throw new ParserError( 5, token.pos );
                                activeNode = node;
                                state = ParseState.OPERATOR;
                                break;
                            }
                            Node node = new Node( activeNode, token.keyword.getOperator( ) );
                            if ( !activeNode.append( node ) )
                                throw new ParserError( 6, token.pos );
                            activeNode = node;
                            break;
                        }

                        case SYMBOL:
                        {
                            if ( token.symbol == Symbol.OPENING_PARENTHESIS )
                            {
                                Node subtree = new Node( );
                                tokenIndex = getSubtree( tokens, tokenIndex, subtree, true );
                                if ( subtree.isEmpty( ) )
                                    throw new SyntaxError( ErrorId.OPERAND_EXPECTED, token.pos );
                                if ( !activeNode.append( subtree ) )
                                    throw new ParserError( 7, token.pos );
                                subtree.parent = activeNode;
                                activeNode = subtree;
                                state = ParseState.OPERATOR;
                                break;
                            }
                            UnaryOp operator = null;
                            switch ( token.symbol )
                            {
                                case PLUS:
                                    operator = UnaryOp.PLUS;
                                    break;

                                case MINUS:
                                    operator = UnaryOp.MINUS;
                                    break;

                                default:
                                    throw new SyntaxError( ErrorId.OPERAND_EXPECTED, token.pos );
                            }
                            Node node = new Node( activeNode, operator );
                            if ( !activeNode.append( node ) )
                                throw new ParserError( 8, token.pos );
                            activeNode = node;
                            break;
                        }

                        case EOF:
                            throw new SyntaxError( ErrorId.OPERAND_EXPECTED, token.pos );
                    }
                    break;
                }

                case OPERATOR:
                {
                    switch ( token.type )
                    {
                        case NUMBER:
                        case VARIABLE:
                        case KEYWORD:
                            throw new SyntaxError( ErrorId.BINARY_OPERATOR_EXPECTED, token.pos );

                        case SYMBOL:
                        {
                            if ( token.symbol == Symbol.OPENING_PARENTHESIS )
                                throw new SyntaxError( ErrorId.BINARY_OPERATOR_EXPECTED, token.pos );
                            if ( token.symbol == Symbol.CLOSING_PARENTHESIS )
                            {
                                if ( !subexpression )
                                    throw new SyntaxError( ErrorId.UNEXPECTED_CLOSING_PARENTHESIS,
                                                           token.pos );
                                state = ParseState.DONE;
                                break;
                            }
                            if ( activeNode.isOperator( ) )
                                throw new ParserError( 9, token.pos );
                            BinaryOp operator = token.symbol.getOperator( );
                            if ( operator == null )
                                throw new ParserError( 10, token.pos );
                            int opPrecedence = operator.getPrecedence( );
                            while ( activeNode.parent != null )
                            {
                                activeNode = activeNode.parent;
                                if ( (activeNode.type == Node.Type.BINARY_OP) &&
                                     (opPrecedence > activeNode.binaryOp.getPrecedence( )) )
                                    break;
                            }
                            Node node = new Node( activeNode, operator );
                            if ( activeNode.parent == null )
                            {
                                node.lChild = activeNode.lChild;
                                activeNode.lChild = node;
                            }
                            else
                            {
                                node.lChild = activeNode.rChild;
                                activeNode.rChild = node;
                            }
                            node.lChild.parent = node;
                            activeNode = node;
                            state = ParseState.OPERAND;
                            break;
                        }

                        case EOF:
                            if ( subexpression )
                                throw new SyntaxError( ErrorId.CLOSING_PARENTHESIS_EXPECTED, token.pos );
                            state = ParseState.DONE;
                            break;
                    }
                    break;
                }
            }
        }

        return ( tokenIndex );
    }

    //------------------------------------------------------------------

////////////////////////////////////////////////////////////////////////
//  Instance methods : overriding methods
////////////////////////////////////////////////////////////////////////

    public String toString( )
    {
        return str;
    }

    //------------------------------------------------------------------

////////////////////////////////////////////////////////////////////////
//  Instance methods
////////////////////////////////////////////////////////////////////////

    public boolean equals( Expression expression )
    {
        return ( (expression != null) && tree.equals( expression.tree ) );
    }

    //------------------------------------------------------------------

    public double evaluate( double x )
    {
        Node.x = x;
        return tree.lChild.evaluate( );
    }

    //------------------------------------------------------------------

    public String toCanonicalString( )
    {
        if ( tokens == null )
            return null;
        StringBuilder buffer = new StringBuilder( 256 );
        for ( int i = 0; i < tokens.size( ); ++i )
        {
            Token token = tokens.get( i );
            if ( token.type == Token.Type.EOF )
                break;
            if ( i > 0 )
                buffer.append( ' ' );
            buffer.append( token );
        }
        return buffer.toString( );
    }

    //------------------------------------------------------------------

    private void parse( String str )
        throws Expression.Exception
    {
        tokens = toTokens( str );
        tree = parse( tokens );
    }

    //------------------------------------------------------------------

////////////////////////////////////////////////////////////////////////
//  Instance variables
////////////////////////////////////////////////////////////////////////

    private String      str;
    private List<Token> tokens;
    private Node        tree;

}

//----------------------------------------------------------------------