6
\$\begingroup\$

This is my homework. Kindly help me check it?

The instructions are:

Implement an infix expression to postfix expression converter. You are to implement the infix to postfix algorithm presented in the lecture. You are to use only the stack that was provided in the lab lecture. The use of the stack of JDK or any other stack is not allowed. The supported operators are +, -, *, / and ^. Grouping operator are ( and ).

Input: Infix expresseion where each token (operand and operator) are space-separated (console-based). Explore the StringTokenizer class for tokenizing (separating the infix expression into tokesn) the input. The book of Deitel and Deitel has examples on how to use StringTokenizer.

Output: Postfix expression (console-based). The tokens (operand and operator) are also space-separated in the output. "

The code I wrote is:

import java.util.*;

public class PostfixConverter {
private String infixExpression;

public PostfixConverter(String infixExpression) {
this.infixExpression = infixExpression;
}

private String convertInfixExpression() {
StringTokenizer tokens = new StringTokenizer(infixExpression);
Stack operatorStack = new ArrayStack();
String converted = "";

while(tokens.hasMoreTokens()) {
    String token = tokens.nextToken();
    if(token.equals("(")) {
        operatorStack.push(new String(token));
    }
    else if(token.equals(")")) {
        while(operatorStack.top().equals("(") != true) {
                converted = converted + " " + operatorStack.pop();
            }
        if(operatorStack.top().equals("(")) {
            operatorStack.pop();
        }
    }
    else if (isOperator(token)){
        if(operatorStack.isEmpty() == true) {
            operatorStack.push(new String(token));
        }
        else {
            if(ICP(token) < ISP((String) operatorStack.top())) {
                converted = converted + " " + operatorStack.pop();
                operatorStack.push(token);
            }
            else {
                operatorStack.push(new String(token));
            }
        }
    }
    else {
        converted = converted + " " + new String(token);
    }
}
while(operatorStack.isEmpty() != true) {
    converted = converted + " " + operatorStack.pop();
    }

return converted;
}

public int ISP(String token) {
int precedence = 0;
if(token.equals("+")|| token.equals("-")) {
    precedence = 2;
}
else if(token.equals("*") || token.equals("/")) {
    precedence = 4;
}
else if(token.equals("^")) {
    precedence = 5;
}
else if(token.equals("(")) {
    precedence = 0;
}
return precedence;
}

public int ICP(String token) {
int precedence = 0;
if(token.equals("+")|| token.equals("-")) {
    precedence = 1;
}
else if(token.equals("*") || token.equals("/")) {
    precedence = 3;
}
else if(token.equals("^")) {
    precedence = 6;
}
return precedence;
}

private boolean isOperator(String token) {
return (token.equals("+") || 
        token.equals("-") || 
        token.equals("*") || 
        token.equals("/") ||
        token.equals("^") );            
}

public static void main(String[] args) {
System.out.println("Input the infix expression " 
        + "(operands, operators are separated by spaces):");
Scanner input = new Scanner(System.in);
String infixExpression = input.nextLine();
PostfixConverter converter = new PostfixConverter(infixExpression);
System.out.println("The converted expression is " + 
        converter.convertInfixExpression());
}


}
\$\endgroup\$
  • 1
    \$\begingroup\$ What is ArrayStack? \$\endgroup\$ – 200_success Aug 9 '14 at 10:18
  • \$\begingroup\$ @SimonGo : Indentation looks weird did it occur when you copy paste it here ? or was it like that from the beginning ? \$\endgroup\$ – 422_unprocessable_entity Aug 9 '14 at 11:47
7
\$\begingroup\$

I like this opportunity for a code review because I hopefully can share some good programming techniques that I didn't have a chance to learn until I actually got out of school and into the industry. I can edit to explain anything further.

  • Your variable infixExpression can be defined as final:

    private final String infixExpression;
    

    This isn't necessary but is good practice as it's a good idea to maximize the immutability of your classes. Anything variable which is only modified when declared, or in a constructor, may be final.

  • The convertInfixExpression method should also be public. I know this is for an assignment, but that should not stop you from thinking about using it outside the main method. Alternatively, you could do away with the constructor altogether, and just make this method static. That way, you would use it by calling

    PostfixConverter.convertInfixExpression("my infix expression");
    

    This is possible by changing your current convertInfixExpression method signature to

    public static String convertInfixExpression(String infixExpression)
    
  • I don't know what library ArrayStack came from, but I can assume how it works. That being said, you don't parametize it which is a big no no, and causes yourself some extra work later. This should be

    Stack<String> operatorStack = new ArrayStack<String>();
    
  • In Java, appending to a String is typically a bad idea. If you have an object you know you'll be appending too, use a StringBuilder:

    StringBuilder converted = new StringBuilder();
    
  • Concerning the first while loop in the method, I don't like the looks of it from a glance. There's way too many nested while, if, and else statements. We'll see if we can simplify some of that. To start, let's look at the highest level of what's going on:

    If token is a '(' push to stack
    If token is a ')' do complicated stuff
    If token is an Operator do complicated stuff
    Otherwise append the token to the result
    

    So the hint here is that you want to move all that complicated stuff to separate methods. Your code benefits from this by being much easier to read and reason about.

  • There's almost never a reason to use the new keyword next to String in Java.

    operatorStack.push(token);
    

    not

    operatorStack.push(new String(token));
    
  • The first complicated block (fixed formatting):

    while(operatorStack.top().equals("(") != true) {
        converted = converted + " " + operatorStack.pop();
    }
    if(operatorStack.top().equals("(")) {
        operatorStack.pop();
    }
    

    I guess this isn't too complicated, but I don't like seeing nested while statements... This is how I would write it:

    while(!operatorStack.top().equals("(")) {
        converted.append(" ").append(operatorStack.pop());
    }
    operatorStack.pop();
    

    I'll highlight the differences:

    • There's no reason to ever compare anything to true or false in an if statement.
    • Used append from the StringBuilder. Check out the Oracle tutorial on this class to find out why.
    • There's no reason for the if statement. We already know the a ( is on the top of the stack, otherwise the previous loop wouldn't have ended.
  • Regarding the second complicated bit, I would write it like so:

    else if (isOperator(token)){
        if(operatorStack.isEmpty()) {
            operatorStack.push(token);
        }
        else {
            if(ICP(token) < ISP(operatorStack.top())) {
                converted.append(" ").append(operatorStack.pop());
                operatorStack.push(token);
            }
            else {
                operatorStack.push(token);
            }
        }
    }
    

    Pretty much the same comments as above, but notice you don't need to cast to a String because you've now parametized your stack. Too be honest, though I'm still not entirely sure of the purpose of the logic here, but mainly because I have no idea what ICP and ISP mean!

  • Use descriptive and conventional method names. If ICP and ISP return a value, they should start with get. I know they're return the precedence of operators, but the S and C is still unclear to me. That being said, you can simplify all of this by using some Map constants. For example,

    private static final Map<String, Integer> S_PRECEDENCE;
    static {
        Map<String, Integer> map = new HashMap<String, Integer>();
        map.put("+", 2);
        map.put("-", 2);
        map.put("*", 4);
        ....
        S_PRECEDENCE = Collections.unmodifiableMap(map);
    }
    

    And then you can change the ISP method to something like

    public int ISP(String token) {
        return S_PRECEDENCE.contains(token) ? S_PRECEDENCE.get(token) : 0;
    }
    

    I'll note that S_PRECEDENCE is a bad name and should be expanded with whatever S means.

  • Along the same lines, you can make a Set of your operators, and simply check if that collection contains the token.

\$\endgroup\$
3
\$\begingroup\$

Building upon @lealand's well-written suggestions, I can offer five more:

  1. Moving away from StringTokenizer

    According to various answers such as this, StringTokenizer is a legacy class that is discouraged for use over the String.split() or Pattern.split() methods. A small benefit of using the split() methods is that you save a line by converting the while-loop into a for-loop:

    while (tokenizer.hasMoreTokens()) {
        String token = tokenizer.nextToken();
        ...
    }
    

    vs.

    for (String token : tokens) {
        ...
    }
    
  2. Using a standardized way of building the output

    If you have decided to apply @lealand's suggestion to use a StringBuilder, remember that it accepts char values too, which in your case works well for the whitespace character ' '. Hence, instead of repeating builder.append(' ').append(<some String value>), you can make the call slightly shorter by:

    private static append(final StringBuilder builder, final String value) {
        builder.append(' ').append(value);
    }
    
  3. Simplifying the 'first complicated loop' (re: @lealand's answer)

    @lealand suggested this (copying in verbatim):

    while(!operatorStack.top().equals("(")) {
        converted.append(" ").append(operatorStack.pop());
    }
    operatorStack.pop();
    

    On second look, the final operatorStack.pop() is simply to remove the false condition of the while loop, i.e. when operatorStack.top() is "(". Knowing this, you can just pop() every element and add to the output except for the value "(":

    String operator;
    while (!"(".equals(operator = operatorStack.pop())) {
        append(result, operator);
    }
    
  4. Simplifying the 'second complicated loop' (re: @lealand's answer)

    @lealand suggested this (copying in verbatim):

    else if (isOperator(token)){
        if(operatorStack.isEmpty()) {
            operatorStack.push(token);
        }
        else {
            if(ICP(token) < ISP(operatorStack.top())) {
                converted.append(" ").append(operatorStack.pop());
                operatorStack.push(token);
            }
            else {
                operatorStack.push(token);
            }
        }
    }
    

    On second look, operatorStack.push(token) is actually done for every condition, so we can simplify it as such:

    else if (Operator.isOperator(token)) {
        if (!operatorStack.isEmpty() && Operator.isPrecedent(token, operatorStack.top())) {
            append(result, operatorStack.pop());
        }
        operatorStack.push(token);
    } 
    

    The append() is only done when operatorStack.isEmpty() and the comparison done are both false. What is Operator.isPrecedent()? That brings us to the final suggestion...

  5. Using enum to hide magic numbers and logic

    To be frank, I have no idea what ICP() and ISP() stands for, besides the fact that they are not well-named method names. Furthermore, the use of magic numbers should be 'hidden' away, and I have opted for the enum approach. In this approach, I create enum values for the operators with their respective icp and isp values. I can then rely on a statc Map to map the String representation of the operators to the respective enums for usage in isOperator(). The operator precedence comparison can also be done as a static method of the enum. You can see below for the entirety of this enum.

Putting it altogether

public class PostfixConverter {
    public static String convertInfixExpression(final String infixExpression) {
        final String[] tokens = Pattern.compile("\\s+").split(infixExpression);
        final Stack operatorStack = new ArrayStack();
        final StringBuilder result = new StringBuilder();
        for (final String token : tokens) {
            if (token.equals("(")) {
                operatorStack.push(token);
            } else if (token.equals(")")) {
                String operator;
                while (!"(".equals(operator = operatorStack.pop())) {
                    append(result, operator);
                }
            } else if (Operator.isOperator(token)) {
                if (!operatorStack.isEmpty() && Operator.isPrecedent(token, operatorStack.top())) {
                    append(result, operatorStack.pop());
                }
                operatorStack.push(token);
            } else {
                append(result, token);
            }
        }
        while (!operatorStack.isEmpty()) {
            append(result, operatorStack.pop());
        }
        return result.toString();
    }

    private static void append(final StringBuilder builder, String value) {
        builder.append(' ').append(value);
    }

    enum Operator {
        PLUS('+', 1, 2), MINUS('-', 1, 2), MULTIPLY('*', 3, 4), DIVIDE('/', 3, 4), EXPONENT('^', 6, 5);

        private final char value;
        private final int icpValue;
        private final int ispValue;

        Operator(char value, int icpValue, int ispValue) {
            this.value = value;
            this.icpValue = icpValue;
            this.ispValue = ispValue;
        }

        private final static Map<String, Operator> operatorMap = new HashMap<>();

        static {
            for (Operator operator : Operator.values()) {
                operatorMap.put(String.valueOf(operator.value), operator);
            }
        }

        private static Operator getOperator(final String operator) {
            return operatorMap.get(operator);
        }

        static boolean isOperator(final String operator) {
            return getOperator(operator) != null;
        }

        private static int getIcpValue(final String value) {
            final Operator operator = getOperator(value);
            return operator == null ? 0 : operator.icpValue;
        }

        private static int getIspValue(final String value) {
            final Operator operator = getOperator(value);
            return operator == null ? 0 : operator.ispValue;
        }

        static boolean isPrecedent(final String firstToken, final String secondToken) {
            return getIcpValue(firstToken) < getIspValue(secondToken);
        }
    }

    public static void main(String[] args) {
        System.out.println("Input the infix expression (operands, operators are separated by spaces):");
        try (Scanner input = new Scanner(System.in)) {
            String line;
            while (!"q".equals(line = input.nextLine())) {
                System.out.println("Converted expression: " + PostfixConverter.convertInfixExpression(line));
            }
        }
    }
}

Final notes:

  • I am assuming Stack and ArrayStack are handling Strings only, otherwise you'll need @lealand's type suggestion.
  • Not sure if you're on JDK7 or not, but I am using try-with-resources to prevent resource leakage on Scanner. I have also showed how to handle repetitive inputs until the user exits with a single q input.
\$\endgroup\$
  • \$\begingroup\$ I love the use of the enum in (5). I suggest changing the while to a for loop in (3) just to simplify things and make them more explicit. Then you also don't have to have the operator variable declaration sitting on its own lonesome line. \$\endgroup\$ – lealand Aug 10 '14 at 10:12
  • \$\begingroup\$ You mean like for (String operator = operatorStack.pop(); !"(".equals(operator); operator = operatorStack.pop())? \$\endgroup\$ – h.j.k. Aug 10 '14 at 10:29
  • 1
    \$\begingroup\$ Yeah, just a thought. They're equivalent and I have somewhat of an aversion to causing side effects in a while loop. \$\endgroup\$ – lealand Aug 10 '14 at 18:14

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.