## Thursday, July 27, 2017

### Expression Evaluation

https://wxx5433.gitbooks.io/interview-preparation/content/part_ii_leetcode_lintcode/stack/expression_evaluation.html
Given an expression string array, return the final result of this expression.
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, +, -, *, /, (, ).

Simulate the process to do computation. If previous operator has higher priority than the new operator, it is safe to do computation using the previous operation.
Corner Case
expression = {"(", "(", ")", ")"};
Complexity
Time: O(N)
Space: O(N)

``````  public int evaluateExpression(String[] expression) {
if (expression == null || expression.length == 0) {
return 0;
}
Stack<Integer> numStack = new Stack<>();
Stack<String> opStack = new Stack<>();
for (String token : expression) {
if (isNumber(token)) {
numStack.push(Integer.valueOf(token));
} else if (token.equals("(")) {
opStack.push(token);
} else if (token.equals(")")) {
while (!opStack.peek().equals("(")) {
numStack.push(compute(numStack.pop(), numStack.pop(), opStack.pop()));
}
opStack.pop();  // pop out "("
} else {
while (!opStack.isEmpty() && getPriority(opStack.peek()) >= getPriority(token)) {
numStack.push(compute(numStack.pop(), numStack.pop(), opStack.pop()));
}
opStack.push(token);
}
}
while (!opStack.isEmpty()) {
numStack.push(compute(numStack.pop(), numStack.pop(), opStack.pop()));
}
return numStack.isEmpty() ? 0 : numStack.pop();
}

private boolean isNumber(String token) {
return Character.isDigit(token.charAt(0));
}

private int getPriority(String op) {
if (op.equals("(")) {
return 0;
} else if (op.equals("+") || op.equals("-")) {
return 1;
} else {
return 2;
}
}

private int compute(int num2, int num1, String token) {
int result;
if (token.equals("+")) {
result = num1 + num2;
} else if (token.equals("-")) {
result = num1 - num2;
} else if (token.equals("*")) {
result = num1 * num2;
} else {
result = num1 / num2;
}
return result;
}``````