Convert Expression to Reverse Po

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

Example
For the expression [3 - 4 + 5] (which denote by ["3", "-", "4", "+", "5"]), return [3 4 - 5 +] (which denote by ["3", "4", "-", "5", "+"])

答案

public class Solution {
    /**
     * @param expression: A string array
     * @return: The Reverse Polish notation of this expression
     */
    public List<String> convertToRPN(String[] expression) {
        List<String> list = new ArrayList<>();
        Stack<Integer> numstk = new Stack<>();
        Stack<String> opstk = new Stack<>();

        for(int i = 0; i < expression.length; i++) {
            String curr = expression[i];
            // Number
            if(Character.isDigit(curr.charAt(0))) {
                list.add(curr);
            }
            else if(curr.equals("(")) {
                opstk.push("(");
            }
            else if(curr.equals(")")) {
                while(!opstk.isEmpty() && !opstk.peek().equals("(")) {
                    list.add(opstk.pop());
                }
                // Pop left paren
                opstk.pop();
            }
            else {
                // + - * /
                while(!opstk.isEmpty() && !opstk.peek().equals("(") && !isHigherPriority(curr, opstk.peek())) {
                    String last_op = opstk.pop();
                    list.add(last_op);
                }

                opstk.push(curr);
            }
        }

        while(!opstk.isEmpty()) list.add(opstk.pop());

        return list;
    }

    public boolean isHigherPriority(String op1, String op2) {
        if((op1.equals("*") || op1.equals("/")) && (op2.equals("+") || op2.equals("-"))) return true;
        return false;
    }
}