postfixconversion.java

Calculator algorithm with postfix notation. Example of usage.

import java.util.Stack;

public class PostfixConversion
{
    /**
     * The precedence method determines the precedence between two operators.
     * If the first operator is of higher or equal precedence than the second operator,
     * it returns the value true; otherwise, it returns the value false.
     * This method will be called from the convertToPostfix method described below
     *
     * @param first  - first operator
     * @param second - second operator
     * @return true if the first operator is of higher or equal precedence than the second operator,
     *         otherwise, it returns the value false.
     */
    public static boolean precedence(char first, char second)
    {
        //First precedence weight
        int firstPrec = 0;
        //Second precedence weight
        int secondPrec = 0;

        //Set weights based on operator
        if (first == '+')
            firstPrec = 1;
        if (first == '-')
            firstPrec = 1;
        if (first == '*')
            firstPrec = 2;
        if (first == '/')
            firstPrec = 2;

        if (second == '+')
            secondPrec = 1;
        if (second == '-')
            secondPrec = 1;
        if (second == '*')
            secondPrec = 2;
        if (second == '/')
            secondPrec = 2;

        //Get result
        return firstPrec >= secondPrec;
    }

    /**
     * The convertToPostfix method converts the infix expression
     * (the parameter string for this method) into a postfix expression.
     *
     * @param str - infix expression
     * @return postfix expression.
     */
    public static String convertToPostfix(String str)
    {
        //Skip empty string
        if (str == null || str.length() == 0)
            return str;

        //Number of left and right parenthesises
        int lp = 0, rp = 0;
        for (int i = 0; i < str.length(); i++)
        {
            //count parenthesises
            if (str.charAt(i) == '(')
                lp++;
            if (str.charAt(i) == ')')
                rp++;

            //If first in expression is right parenthesis - error
            if (rp == 1 && lp == 0)
                return "There is no matching left parenthesis.";
        }

        //if count of left and right parenthesises isn't equal - errors
        if (lp > rp)
            return "There is no matching right parenthesis.";

        if (lp < rp)
            return "There is no matching left parenthesis.";

        //Final expression string
        String postfix = "";
        //Stack for operators
        Stack stack = new Stack();

        //Scan each character of a given infix expression (a string) from left to right
        for (int i = 0; i < str.length(); i++)
        {
            char ch = str.charAt(i);

            //If the next scanned symbol (character) is an operand
            // (here only alphabet letters - both upper cases and lower cases are used.),
            // append it to the postfix expression.
            if (Character.isLetter(ch))
                postfix += ch;

            //If the next scanned symbol (character) is a left parenthesis '(', then put it onto the stack
            if (ch == '(')
                stack.push(new Character(ch));

            //If the next scanned symbol (character) is a right parenthesis ')', then pop and append all
            // the symbols from the stack until the most recent matching left parenthesis. i.e.,
            // pop and append all the symbols above the left parenthesis that is located in the highest
            // position in the stack. Then pop and discard that left parenthesis at the highest position in the stack.
            if (ch == ')')
            {
                char c = '\0';
                while (c != '(' && stack.size() > 0)
                {
                    c = ((Character) stack.pop()).charValue();

                    if (c != '(')
                        postfix += c;
                }
            }

            //If the next scanned symbol (character) is an operator (here, they are either '+', '-', '*', or '/')
            if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
            {
                char c = '\0';
                boolean prec = true;
                //Pop and append to the postfix expression every operator from the stack
                // that is above the most recently scanned left parenthesis, and that has
                // precedence greater than or equals to the new operator
                while (c != '(' && stack.size() > 0 && prec)
                {
                    c = ((Character) stack.peek()).charValue();
                    prec = precedence(c, ch);
                    if (c != '(' && prec)
                    {
                        postfix += c;
                        stack.pop();
                    }
                }
                //Push the new operator onto the stack
                stack.push(new Character(ch));
            }
        }

        //After the infix string is completely processed,
        // pop and append to the postfix string everything from the stack
        char c = '\0';
        while (stack.size() > 0)
        {
            c = ((Character) stack.pop()).charValue();
            if (c != '(')
                postfix += c;
        }

        //Return result
        return "The Postfix Expression is: " + postfix;
    }
}