Expression Evaluation
21%
Accepted
Given an expression string array, return the final result of this expression
Have you met this question in a real interview?
Yes
Example
For the expression
2*6-(23+7)/(1+2), input is[
"2", "*", "6", "-", "(",
"23", "+", "7", ")", "/",
(", "1", "+", "2", ")"
],
return
2
Note
The expression contains only
integer, +, -, *, /, (, ).
public class Solution {
/**
* @param expression: an array of strings;
* @return: an integer
*/
public int evaluateExpression(String[] expression) {
// write your code here
Stack<String> stack = new Stack<String>();
Queue<String> queue = new LinkedList<String>();
String operator = "-+/*";
for(String cur : expression){
if(operator.contains(cur)){
while(!stack.isEmpty() && precedence(stack.peek()) >= precedence(cur)){
queue.offer(stack.pop());
}
stack.push(cur);
} else if(cur.equals("(")){
stack.push(cur);
} else if(cur.equals(")")){
while(!stack.isEmpty() && !"(".equals(stack.peek())){
queue.offer(stack.pop());
}
stack.pop();
} else {
queue.offer(cur);
}
}
while(!stack.isEmpty()) {
queue.offer(stack.pop());
}
return evaluate(queue);
}
private int evaluate(Queue<String> queue){
Stack<Integer> stack = new Stack<Integer>();
while(!queue.isEmpty()){
String cur = queue.poll();
if("*/-+".contains(cur)){
int a = stack.pop();
int b = stack.pop();
int result = 0;
if(cur.equals("+")){
result = a + b;
} else if(cur.equals("-")){
result = b - a;
} else if(cur.equals("/")){
result = b / a;
} else if(cur.equals("*")){
result = a * b;
}
stack.push(result);
} else {
stack.push(Integer.parseInt(cur));
}
}
if(stack.isEmpty()) return 0;
return stack.pop();
}
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