Convert Expression to Reverse Polish Notation
25%
Accepted
Given an expression string array, return the Reverse Polish notation of this expression. (remove the parentheses)
Have you met this question in a real interview?
Yes
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 ArrayList<String> convertToRPN(String[] expression) {
// write your code here
Stack<String> stack = new Stack<String>();
ArrayList<String> res = new ArrayList<String>();
String operator = "-+/*";
for(String cur : expression){
if(operator.contains(cur)){
while(!stack.isEmpty() && precedence(stack.peek()) >= precedence(cur)){
res.add(stack.pop());
}
stack.push(cur);
} else if(cur.equals("(")){
stack.push(cur);
} else if(cur.equals(")")){
while(!stack.isEmpty() && !"(".equals(stack.peek())){
res.add(stack.pop());
}
stack.pop();
} else {
res.add(cur);
}
}
while(!stack.isEmpty()) {
res.add(stack.pop());
}
return res;
}
private int precedence(String op){
if(op.equals("-") || op.equals("+"))
return 1;
if(op.equals("/") || op.equals("*"))
return 2;
return 0;
}
}
No comments:
Post a Comment