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