A
A
Algorithm Practice
Search…
A
A
Algorithm Practice
Introduction
Lintcode
Expression Evaluation
Leetcode
Google
Powered By GitBook
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)
Previous
Lintcode
Next
Leetcode
Last modified 2yr ago
Copy link
Contents
Expression Evaluation
1. Question
Notice
2. Implementation
3. Time & Space Complexity