Convert Expression to Reverse Polish Notation

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", "+"])

Solution:

Simply reverse the output of infix to postfix conversion in (Expression Evaluation).

Code:

public class Solution {
    /**
     * @param expression: A string array
     * @return: The Reverse Polish notation of this expression
     */
    public ArrayList<String> convertToRPN(String[] expression) {
        ArrayList<String> res = infixToPostfix(expression);
        Collections.reverse(res);
        return res;
    }

    private ArrayList<String> infixToPostfix(String[] strs) {
        Stack<String> postfix = new Stack<>();
        Stack<String> opstack = new Stack<>();
        for (String s : strs) {
            if (isNum(s)) {
                postfix.push(s);
            } else {
                if (!opstack.empty()) {
                    if (s.equals("(")) {
                        opstack.push(s);
                    } else if (s.equals(")")) {
                        while (!opstack.empty() && !opstack.peek().equals("(")) {
                            postfix.push(opstack.pop());
                        }
                        if (opstack.peek().equals("(")) {
                            opstack.pop();
                        }
                    } else {
                        while (!opstack.empty() && order(opstack.peek()) >= order(s)) {
                            postfix.push(opstack.pop());
                        }
                        opstack.push(s);
                    }
                } else {
                    opstack.push(s);
                }
            }
        }
        while (!opstack.empty()) {
            postfix.push(opstack.pop());
        }
        ArrayList<String> res = new ArrayList<>();
        while (!postfix.empty()) {
            res.add(postfix.pop());
        }
        return res;
    }

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

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

results matching ""

    No results matching ""