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