package freegraph;

/***
 * ExpressionStack, by Martin Lovell 1999
 * Freeware
 */

import java.util.*;

/**
 * ExpressionStack converts a free-form Infix expression into Postfix, or
 * Reverse Polish Notation (RPN).  The expression is parsed into tokens, and
 * converted to RPN using a standard stack technique. After converted to RPN,
 * the expression is on a stack which can be easily evaluated using
 * ExpressionEvaluator.
 * <P>
 * The stack technique involves using 3 stacks, an infix stack, a hold stack,
 * and an RPN stack.  Following a algorithm, items on the infix stack are
 * tested, and based on what is on the top of the HOLD stack, one of 5 "ACTION"
 * constants are followed.  The ExpressionItem.getAction() method is called
 * on the ExpressionItem on the top of the infix stack to determine which
 * action to take.
 * <P>
 * When the InfixExpression property is set, the expression is parsed, and the
 * RPN stack is immediately available.
 * <P>
 * The algorithm used is from: Tanenbaum, Andrew S. 1990.
 * <I>Structured Computer Organization, 3rd ed.</I>,
 * New Jersey: Prentice Hall. (pp. 268-272)
 * @see ExpressionEvaluator
 */
public class ExpressionStack extends Stack
{

    /**
     * Action indicating that the top of the infix stack should be put on the
     * top of the RPN stack
     */
    final public static int ACTION_INFIX_TO_RPN_STACK = 0;

    /**
     * Action indicating that the top of the infix stack should be put on the
     * top of the hold stack
     */
    final public static int ACTION_INFIX_TO_HOLD_STACK = 1;

    /**
     * Action indicating that the top of the hold stack should be put on the
     * top of the RPN stack
     */
    final public static int ACTION_HOLD_TO_RPN_STACK = 2;

    /**
     * Action indicating that the top of the hold stack should be deleted
     */
    final public static int ACTION_DELETE_HOLD = 3;

    /**
     * Action indicating that conversion is complete
     */
    final public static int ACTION_COMPLETE = 4;

    /**
     * Action indicating that an error has occured because an unexpected
     * token was encountered
     */
    final public static int ACTION_ERROR = 5;

    /***
     * the string holding the current infixExpression which is being
     * represented by the stack.
     */
    private String infixExpression = "";

    /**
     * Constructs a new ExpressionStack for the infixExpression.
     * @param infixExpression   a free-form infix expression
     */
    public ExpressionStack(String infixExpression) throws ExpressionException
    {
        setInfixExpression(infixExpression);
    }

    /**
     * Constructs a new ExpressionStack which initially has no
     * infixExpression
     */
    public ExpressionStack()
    {
    }

    /**
     * internal method because StringBuffer.delete is not available in
     * Java 1.1
     */
    private static void strBuffSub(StringBuffer b, int startIndex)
    {
        String s = b.toString().substring(startIndex);
        b.setLength(s.length());
        for (int i = 0; i < s.length(); i++)
        {
            b.setCharAt(i, s.charAt(i));
        }
    }

    /**
     * Internally used method to convert the infixExpression to an RPN stack.
     * This method uses the ExpressionParse private class to perform the actual
     * parsing.
     */
    private void convertToPostfix() throws ExpressionException
    {
        if (infixExpression == null || infixExpression.length() < 1)
        {
            return;
        }
        ExpressionParser exprParse = new ExpressionParser(infixExpression);
        Stack reversePostfix = new Stack();
        Stack holdStack = new Stack();
        Stack infixStack = exprParse.getExpressionItemStack();
        ExpressionItem exprItem = (ExpressionItem) infixStack.pop();
        int action = 5;
        ExpressionItem topOfHold;
        whileLoop:while (exprItem != null)
        {
            if (holdStack.size() > 0)
            {
                topOfHold = (ExpressionItem) holdStack.peek();
            }
            else
            {
                topOfHold = null;
            }
            action = exprItem.getAction(topOfHold);
            switch (action)
            {
                case ACTION_INFIX_TO_RPN_STACK:
                    reversePostfix.push(exprItem);
                    break;
                case ACTION_INFIX_TO_HOLD_STACK:
                    holdStack.push(exprItem);
                    break;
                case ACTION_HOLD_TO_RPN_STACK:
                    reversePostfix.push(holdStack.pop());
                    continue; //don't read another item
                case ACTION_DELETE_HOLD:
                    holdStack.pop();
                    break;
                case ACTION_COMPLETE:
                    break whileLoop;
                case ACTION_ERROR:
                    throw new ExpressionException(
                        "Error Converting to Postfix");
            }
            try
            {
                exprItem = (ExpressionItem) infixStack.pop();
            }
            catch (Exception e)
            {
                exprItem = null;
            }
        }
        if (holdStack.size() > 0)
        {
            topOfHold = (ExpressionItem) holdStack.peek();
        }
        else
        {
            topOfHold = null;
        }
        while (topOfHold != null &&
               (topOfHold instanceof ExpressionItem.BiOperator ||
                topOfHold instanceof ExpressionItem.UnOperator))
        {
            reversePostfix.push(holdStack.pop());
            if (holdStack.size() > 0)
            {
                topOfHold = (ExpressionItem) holdStack.peek();
            }
            else
            {
                topOfHold = null;
            }
        }
        if (holdStack.size() > 0)
        {
            throw new ExpressionException("Error Converting to Postfix");
        }
        //this.clear(); clear not available in 1.1
        while (this.size() > 0)
        {
            this.removeElementAt(0);
        }
        while (reversePostfix.size() > 0)
        {
            this.push(reversePostfix.pop());
        }
    }

    /**
     * sets the infix expression for the stack.  The expression is converted
     * to postfix and is available through the stack.
     */
    public void setInfixExpression(String infixExpression) throws
        ExpressionException
    {
        this.infixExpression = infixExpression;
        convertToPostfix();
    }

    public String getInfixExpression()
    {
        return infixExpression;
    }

    /***
     * ExpressionParser used by ExpressionStack to parse the infix string into
     * expression items
     */
    private static class ExpressionParser
    {
        String expression;
        StringBuffer expr;

        /**
         * Creates a new ExpressionParser to parse the expression
         * @param expression    the expression this instance will parse
         */
        public ExpressionParser(String expression)
        {
            this.expression = expression;
        }

        /**
         * reads the next ExpressionItem from the ExpressionStack. This
         * method is used internally
         */
        private ExpressionItem readExpressionItem(StringBuffer str)
        {
            if (str.length() <= 0)
            {
                return null;
            }

            /* --- START: New code ---
               Thanks to Aaron Patzer
               ELE, Princeton University
             */
            //check for whitespace
            while (Character.isWhitespace(str.charAt(0)))
            {
                strBuffSub(str, 1);
            }
            /* --- END: New code --- */

            char c = Character.toUpperCase(str.charAt(0));

            //check for number
            if ( (c >= '0' && c <= '9') || c == '.')
            {
                StringBuffer resultStr = new StringBuffer();
                do
                {
                    resultStr.append(str.charAt(0));
                    strBuffSub(str, 1);
                    if (str.length() > 0)
                    {
                        c = str.charAt(0);
                    }
                }
                while (str.length() > 0 && ( (c >= '0' && c <= '9') || c == '.'));
                return new ExpressionItem.Number(
                    Double.valueOf(resultStr.toString()).doubleValue());
            }

            //check for Parenthesis
            if (c == '(' || c == ')')
            {
                strBuffSub(str, 1);
                return new ExpressionItem.Parenthesis(
                    c == '(' ? ExpressionItem.Parenthesis.LEFT :
                    ExpressionItem.Parenthesis.RIGHT);
            }

            int newKind = -1;

            //check for bi operator
            String strString = str.toString().toUpperCase();
            for (int i = 0; i < ExpressionItem.BiOperator.OPERATORS.length; i++)
            {
                if (strString.startsWith(ExpressionItem.BiOperator.OPERATORS[i]))
                {
                    newKind = i;
                    strBuffSub(str,
                               ExpressionItem.BiOperator.OPERATORS[i].length());
                    break;
                }
            }
            if (newKind != -1)
            {
                return new ExpressionItem.BiOperator(newKind);
            }

            //check for unary operator
            for (int i = 0; i < ExpressionItem.UnOperator.OPERATORS.length; i++)
            {
                if (strString.startsWith(ExpressionItem.UnOperator.OPERATORS[i]))
                {
                    newKind = i;
                    strBuffSub(str,
                               ExpressionItem.UnOperator.OPERATORS[i].length());
                    break;
                }
            }
            if (newKind != -1)
            {
                return new ExpressionItem.UnOperator(newKind);
            }

            //check for a Variable
            if (c >= 'A' && c <= 'Z')
            {
                strBuffSub(str, 1);
                return new ExpressionItem.Variable(c);
            }

            return null;
        }

        /***
             * internally used method to fix an infix stack by converting subtraction
             * operators to negative operators where appropiate, removing all positive
         * operators and inserts implicit multiplication.
         * <P>It does the following to fix the expression:<BR>
         *
         *   1) If the first position is +, it is removed, if it
         *   is -, it is converted from subtraction to negative operator.<BR>
         *   2) If + or - are after ( or after an operator, then
         *   remove the + and convert - to negative operator.<BR>
         *   3) Add implicit multiplication with ) followed by
         *   an operator, variable, number or (.<BR>
         *   4) Add implicit multiplication with ( preceded by
         *   an operator, variable, number or ).<BR>
         *
         * (ExpressionParser does some down casting on the ExpressionItems when
         * fixing expressions.  Perhaps there is a design which would avoid
         * this; however, it works fine in this case.)
         *
         */
        private void fixInfixStack(Stack infixStack)
        {
            if (infixStack.size() < 2)
            {
                return;
            }
            int i = 0;
            ExpressionItem e1, e2;

            //fix negative or positive in first position
            //  If the first position is +, it is removed, if it
            //  is -, it is converted from subtraction to negative operator.
            //
            e1 = (ExpressionItem) infixStack.elementAt(0);
            if (e1 instanceof ExpressionItem.BiOperator)
            {
                if ( ( (ExpressionItem.BiOperator) e1).getKind() ==
                    ExpressionItem.BiOperator.SUBTR)
                {
                    infixStack.setElementAt(
                        new ExpressionItem.UnOperator(ExpressionItem.UnOperator.
                        NEG),
                        0);
                }
                else
                if ( ( (ExpressionItem.BiOperator) e1).getKind() ==
                    ExpressionItem.BiOperator.ADD)
                {
                    infixStack.removeElementAt(0);
                }
            }

            // fix other negative and positives and implicit multiplication
            while (i < infixStack.size() - 1)
            {
                e1 = (ExpressionItem) infixStack.elementAt(i);
                e2 = (ExpressionItem) infixStack.elementAt(i + 1);

                // if + or - are after ( or after a operator, then
                //  remove the + and convert - to negative operator
                if (e1 instanceof ExpressionItem.UnOperator ||
                    e1 instanceof ExpressionItem.BiOperator ||
                    (e1 instanceof ExpressionItem.Parenthesis &&
                     ( (ExpressionItem.Parenthesis) e1).getKind() ==
                     ExpressionItem.Parenthesis.LEFT))
                {
                    if (e2 instanceof ExpressionItem.BiOperator &&
                        ( (ExpressionItem.BiOperator) e2).getKind() ==
                        ExpressionItem.BiOperator.SUBTR)
                    {
                        infixStack.setElementAt(
                            new ExpressionItem.UnOperator(
                            ExpressionItem.UnOperator.NEG), i + 1);
                    }
                    else
                    if (e2 instanceof ExpressionItem.BiOperator &&
                        ( (ExpressionItem.BiOperator) e2).getKind() ==
                        ExpressionItem.BiOperator.ADD)
                    {
                        infixStack.removeElementAt(i + 1);
                    }
                }

                //Add implicit multiplication with ) followed by
                //an operator, variable, number or (
                if (e1 instanceof ExpressionItem.Parenthesis &&
                    ( (ExpressionItem.Parenthesis) e1).getKind() ==
                    ExpressionItem.Parenthesis.RIGHT &&
                    (e2 instanceof ExpressionItem.UnOperator ||
                     e2 instanceof ExpressionItem.Variable ||
                     e2 instanceof ExpressionItem.Number ||
                     (e2 instanceof ExpressionItem.Parenthesis &&
                      ( (ExpressionItem.Parenthesis) e2).getKind() ==
                      ExpressionItem.Parenthesis.LEFT)
                     ))
                {
                    infixStack.insertElementAt(
                        new ExpressionItem.BiOperator(ExpressionItem.BiOperator.
                        MULT),
                        i + 1);
                }

                //Add implicit multiplication with ( preceded by
                //an operator, variable, number or )
                if ( (e1 instanceof ExpressionItem.Variable ||
                      e1 instanceof ExpressionItem.Number) &&
                    (e2 instanceof ExpressionItem.Variable ||
                     e2 instanceof ExpressionItem.Number ||
                     e2 instanceof ExpressionItem.UnOperator ||
                     (e2 instanceof ExpressionItem.Parenthesis &&
                      ( (ExpressionItem.Parenthesis) e2).getKind() ==
                      ExpressionItem.Parenthesis.LEFT)))
                {
                    infixStack.insertElementAt(
                        new ExpressionItem.BiOperator(ExpressionItem.BiOperator.
                        MULT),
                        i + 1);
                }
                i++;
            }
        }

        /**
         * Parses and fixes the expression and returns the stack of expression
         * items.
         */
        public Stack getExpressionItemStack()
        {
            expr = new StringBuffer(expression);
            ExpressionItem exprItem = readExpressionItem(expr);
            Stack infixStack = new Stack();
            while (exprItem != null)
            {
                infixStack.push(exprItem);
                exprItem = readExpressionItem(expr);
            }
            fixInfixStack(infixStack);
            Stack resultStack = new Stack();
            while (infixStack.size() > 0)
            {
                resultStack.push(infixStack.pop());
            }
            return resultStack;
        }
    }
}