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"));
}
}