3
\$\begingroup\$

I'm looking for code review, optimizations and best practices.

Also verifying complexity to be O(n), where n is the string length.

public final class InfixToPostfix {

    private static final char PLUS = '+';
    private static final char MINUS = '-';
    private static final char MULTIPLY = '*';
    private static final char DIVIDE = '/';
    private static final char OPENBRACE = '(';
    private static final char CLOSEBRACE = ')';

    private InfixToPostfix() {
    }

    private static boolean isOperator(char c) {
        return c == PLUS || c == MINUS || c == MULTIPLY || c == DIVIDE || c == OPENBRACE || c == CLOSEBRACE;
    }

    /**
     * If op1 has a higher precedence than op2.
     * 
     * @param op1   the first operator
     * @param op2   the second operator
     * @return      true if op1 has a higher precendence.
     */
    private static boolean higherPrecedence(char op1, char op2) {
        switch (op1) {
            case PLUS:
            case MINUS:
                return op2 == OPENBRACE;

            case MULTIPLY:
            case DIVIDE:
                return op2 == PLUS || op2 == MINUS || op2 == OPENBRACE;

            case OPENBRACE:
                return true;

            case CLOSEBRACE:
                return false;

            default: throw new IllegalArgumentException("The operator op1: " + op1 +  " or operator op2: "  + op2 + " is illegal.");
        }
    }

    private static StringBuilder getOperators(Stack<String> operatorStack) {
        final StringBuilder operators = new StringBuilder();
        /* eg: a + (b * c), here a,b and +, (, were in their respective stacks, and current char was ) */
        while (!operatorStack.isEmpty() && operatorStack.peek().charAt(0) != OPENBRACE) {
            operators.append(operatorStack.pop());
        }
        /* pop of the remaining open brace. */
        if (!operatorStack.isEmpty() && operatorStack.peek().charAt(0) == OPENBRACE) {
            operatorStack.pop();
        }
        return operators;
    }

    /**
     * Converts a valid infix to postfix expression
     * It is the clients responsibility to provide with a valid infix expression, failing which yeilds invalid results.
     * 
     * @param infix    the infix expression
     * @return         the postfix expressions
     */
    public static String toPostfix(String infix) {
        final Stack<String> operatorStack = new Stack<String>();
        final Deque<String> operandStack = new ArrayDeque<String>();

        char c;

        for (int i = 0; i < infix.length(); i++) {
            c = infix.charAt(i);

            if (c == ' ')
                continue;

            /* we either have an operator or we have have an operand. */
            if (isOperator(c)) {
                /* we either have a operator with higher or lower precedence.*/

                /* eg: a + b * c, here * has higher precedence over +, where ab and + were in respective stacks &
                  current character was */
                if (operatorStack.isEmpty() || higherPrecedence(c, operatorStack.peek().charAt(0))) {
                    operatorStack.push(c + "");
                } else {
                    /* eg: a * b + c, here * has higher precendence over +, where a,b and * were in respective stacks &
                      current character was +  */

                    String op2 = operandStack.pop();
                    String op1 = operandStack.pop();

                    StringBuilder sb = new StringBuilder();
                    sb.append(op1);
                    sb.append(op2);
                    sb.append(getOperators(operatorStack));

                    operandStack.push(sb.toString());
                    if (c != CLOSEBRACE) {
                        operatorStack.push(c + "");
                    }
                }
            } else {
                /* current char is an operand. */
                operandStack.push(c + "");
            }
        }

        /* Output the remaining operators from the stack. */
        while (!operatorStack.empty()) {
            operandStack.push(operatorStack.pop());
        }

        final StringBuilder sb = new StringBuilder();
        while (!operandStack.isEmpty()) {
            sb.append(operandStack.removeLast());
        }
        return sb.toString();
    }

    public static void main(String[] args) { 
        assertEquals("AB*CD/+", InfixToPostfix.toPostfix("A * B+C / D"));
        assertEquals("ABC+*D/", InfixToPostfix.toPostfix("A* (B+C) / D"));
        assertEquals("ABCD/+*", InfixToPostfix.toPostfix("A * (B + C / D)"));
        assertEquals("AB*C/",   InfixToPostfix.toPostfix("A*B/C"));
        assertEquals("AB+C-",   InfixToPostfix.toPostfix("A+B-C"));
    }
}
\$\endgroup\$
4
\$\begingroup\$

Method comments vs. naming
When the method and parameters are well names, in 9 out of 10 cases, the comment above the method is redundant. For example, higherPrecedence(char op1, char op2) - if you call op1 firstOperator and op2 secondOperator the comment above the method simply says the same thing as the method signature. Twice.

Be consistent and precise
higherPrecedence("+", "-") == false, but higherPrecendence("-", "+") == false as well... this is a very surprising result, and might result in inconsistent results.
When you get to the default case you throw an Exception which states that either op1 or op2 are illegal, although you know that op1 is the illegal one, since you don't even check if op2 is an operator.

Magic Constants
I find that "+" is much more descriptive than PLUS. These kind of constants add unnecessary ambiguity to your code, as they force the reader to go and check their actual value.
If you do decide to use a constant, I would suggest a single constant OPERATORS_BY_PRECEDENCE, which will result in these methods:

private static final OPERATORS_BY_PRECEDENCE = "(+-/*)";

private static boolean isOperator(char c) {
    return OPERATORS_BY_PRECEDENCE.indexOf(c) != -1;
}

private static boolean higherPrecendence(char firstOperator, char secondOperator) {
    return OPERATORS_BY_PRECEDENCE.indexOf(firstOperator) < 
        OPERATORS_BY_PRECEDENCE.indexOf(secondOperator);
}
\$\endgroup\$
  • \$\begingroup\$ Although I agree naming has room for improvement, there is a issue with solution you proposed. This problem says 'if precedence is the same, then go from left to right' which means - a+b-c is should be ab+c- and not abc-+ although the would compute to be the same \$\endgroup\$ – JavaDeveloper Apr 7 '14 at 3:13
  • \$\begingroup\$ In that case I would propose that the method will return three states - higher priority, lower priority, or same priority \$\endgroup\$ – Uri Agassi Apr 7 '14 at 3:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.