LeetCode - Basic Calculator II
Problem description
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
Example 1:
1
2
Input: "3+2*2"
Output: 7
Example 2:
1
2
Input: " 3/2 "
Output: 1
Example 3:
1
2
Input: " 3+5 / 2 "
Output: 5
Note:
- You may assume that the given expression is always valid.
- Do not use the eval built-in library function.
Analysis
The basic idea is to use stack.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public int calculate(String s) {
Deque<Character> symbols = new ArrayDeque<>();
Deque<Integer> vals = new ArrayDeque<>();
int n = 0;
int cur = 0;
for (char c:s.toCharArray()){
if (Character.isDigit(c)){
cur = cur * 10 + c-'0';
}
else if (c != ' '){
if (!symbols.isEmpty() && symbols.peekLast() == '*'){
int first = vals.pollLast();
cur = first * cur;
symbols.pollLast();
}
if (!symbols.isEmpty() && symbols.peekLast() == '/'){
int first = vals.pollLast();
cur = first / cur;
symbols.pollLast();
}
vals.offer(cur);
cur = 0;
symbols.offer(c);
}
}
if (!symbols.isEmpty() && symbols.peekLast() == '*'){
int first = vals.pollLast();
cur = first * cur;
symbols.pollLast();
}
if (!symbols.isEmpty() && symbols.peekLast() == '/'){
int first = vals.pollLast();
cur = first / cur;
symbols.pollLast();
}
vals.offer(cur);
int first = vals.pollFirst();
while (!vals.isEmpty()){
int second = vals.pollFirst();
char c = symbols.pollFirst();
if (c == '+'){
first = first + second;
}
else if (c == '-'){
first = first - second;
}
}
return first;
}
}