Convert Expression to Polish Notation

Given an expression string array, return the Polish notation of this expression. (remove the parentheses)

Example:

For the expression [(5 − 6) * 7] (which represented by ["(", "5", "−", "6", ")", "*", "7"]), the corresponding polish notation is [* - 5 6 7] (which the return value should be ["*", "−", "5", "6", "7"]).

Solution:

This problem is a variation of Expression Evaluation. Instead of converting infix to postfix, we need to convert infix to prefix this time. There are three things need to do:

• reverse the given infix string

• change all '(' to ')' and ')' to '('

• when a operator in stack has the same procedure with the incoming one, we should keep that operator in stack. (In postfix, we pop this operator out).

Code:

public class Solution {
    /**
     * @param expression: A string array
     * @return: The Polish notation of this expression
     */
    public ArrayList<String> convertToPN(String[] expression) {
        reverse(expression, 0, expression.length - 1);
        ArrayList<String> res = infixToPrefix(expression);
        return res;
    }

    private void reverse(String[] strs, int start, int end) {
        while (start < end) {
            String temp = strs[start];
            strs[start] = strs[end];
            strs[end] = temp;
            start++;
            end--;
        }
    }

    private ArrayList<String> infixToPrefix(String[] strs) {
        Stack<String> prefix = new Stack<>();
        Stack<String> ops = new Stack<>();
        for (String s : strs) {
            if (isNum(s)) {
                prefix.push(s);
            } else {
                if (ops.empty()) {
                    ops.push(s);
                } else {
                    if (s.equals(")")) {
                        ops.push(s);
                    } else if (s.equals("(")) {
                        while (!ops.empty() && !ops.peek().equals(")")) {
                            prefix.push(ops.pop());
                        }
                        if (!ops.empty() && ops.peek().equals(")")) {
                            ops.pop();
                        }
                    } else {
                        //!important! same level of operator shouldn't pop out in prefix
                        while (!ops.empty() && order(ops.peek()) > order(s)) {
                            prefix.push(ops.pop());
                        }
                        ops.push(s);
                    }
                }
            }
        }
        while (!ops.empty()) {
            prefix.push(ops.pop());
        }
        ArrayList<String> res = new ArrayList<>();
        while (!prefix.empty()) {
            res.add(prefix.pop());
        }
        return res;
    }

    private boolean isNum(String s) {
        if ('0' <= s.charAt(0) && s.charAt(0) <= '9') {
            return true;
        }
        return false;
    }

    private int order(String s) {
        if (s.equals("*") || s.equals("/")) {
            return 2;
        } else if (s.equals("+") || s.equals("-")) {
            return 1;
        } 
        return 0; //for brackets
    }
}