Expression Evaluation

1. Question

Given an expression string array, return the final result of this expression

Notice

The expression contains onlyinteger,+,-,*,/,(,).
Example
For the expression2*6-(23+7)/(1+2), input is
1
[
2
"2", "*", "6", "-", "(",
3
"23", "+", "7", ")", "/",
4
"(", "1", "+", "2", ")"
5
],
Copied!
return2

2. Implementation

1
public class Solution {
2
/**
3
* @param expression: an array of strings;
4
* @return: an integer
5
*/
6
public int evaluateExpression(String[] expression) {
7
// write your code here
8
Stack<Integer> nums = new Stack<>();
9
Stack<String> operators = new Stack<>();
10
11
for (int i = 0; i < expression.length; i++) {
12
String c = expression[i];
13
14
if (isOperator(c)) {
15
if (c.equals("(")) {
16
operators.push(c);
17
}
18
else if (c.equals(")")) {
19
while (!operators.isEmpty() && !operators.peek().equals("(")) {
20
nums.push(calculate(nums.pop(), nums.pop(), operators.pop()));
21
}
22
operators.pop(); // remove "("
23
}
24
else {
25
while (!operators.isEmpty() && hasPrecedence(c, operators.peek())) {
26
nums.push(calculate(nums.pop(), nums.pop(), operators.pop()));
27
}
28
operators.push(c);
29
}
30
}
31
else {
32
nums.push(Integer.valueOf(c));
33
}
34
}
35
36
while (!operators.isEmpty()) {
37
nums.push(calculate(nums.pop(), nums.pop(), operators.pop()));
38
}
39
return nums.isEmpty() ? 0 : nums.pop();
40
}
41
42
public boolean isOperator(String c) {
43
return c.equals("*") || c.equals("/") || c.equals("+") || c.equals("-")
44
|| c.equals("(") || c.equals(")");
45
}
46
47
public int calculate(int num1, int num2, String op) {
48
int value = 0;
49
switch(op) {
50
case "+":
51
value = num1 + num2;
52
break;
53
case "-":
54
value = num2 - num1;
55
break;
56
case "*":
57
value = num1 * num2;
58
break;
59
case "/":
60
value = num2 / num1;
61
break;
62
}
63
return value;
64
}
65
66
// Check if op2 has a higher precedence
67
public boolean hasPrecedence(String op1, String op2) {
68
if (op2.equals("*") || op2.equals("/")) {
69
return true;
70
}
71
else if (op2.equals("+") || op2.equals("-")) {
72
if (op1.equals("*") || op1.equals("/")) {
73
return false;
74
}
75
else {
76
return true;
77
}
78
}
79
else {
80
return false;
81
}
82
}
83
};
Copied!

3. Time & Space Complexity

时间复杂度: O(n), 空间复杂度: O(n)
Last modified 2yr ago