224. Basic Calculator

  • 26.0%

https://leetcode.com/problems/basic-calculator/?tab=Description

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

1
2
3
4
Some examples:
"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.


需要继续学习

方法一:

https://discuss.leetcode.com/topic/22359/16-ms-solution-in-c-with-stacks

16 ms solution in C++ with stacks

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
class Solution {
public:
int calculate(string s) {
stack <int> nums, ops;
int num = 0;
int rst = 0;
int sign = 1;
for (char c : s) {
if (isdigit(c)) {
num = num * 10 + c - '0';
}
else {
rst += sign * num;
num = 0;
if (c == '+') sign = 1;
if (c == '-') sign = -1;
if (c == '(') {
nums.push(rst);
ops.push(sign);
rst = 0;
sign = 1;
}
if (c == ')' && ops.size()) {
rst = ops.top() * rst + nums.top();
ops.pop(); nums.pop();
}
}
}
rst += sign * num;
return rst;
}
};

方法二:

26ms, September 13, 2016

https://discuss.leetcode.com/topic/15806/easy-18-lines-c-16-lines-python

Easy 18 lines C++, 16 lines Python

Keep a global running total and a stack of signs (+1 or -1), one for each open scope. The “global” outermost sign is +1.

  • Each number consumes a sign.
  • Each + and - causes a new sign.
  • Each ( duplicates the current sign so it can be used for the first term inside the new scope. That’s also why I start with [1, 1] - the global sign 1 and a duplicate to be used for the first term, since expressions start like 3… or (…, not like +3… or +(….
  • Each ) closes the current scope and thus drops the current sign.

Also see the example trace below my programs.

C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int calculate(string s) {
int total = 0;
vector<int> signs(2, 1);
for (int i=0; i<s.size(); i++) {
char c = s[i];
if (c >= '0') {
int number = 0;
while (i < s.size() && s[i] >= '0')
number = 10 * number + s[i++] - '0';
total += signs.back() * number;
signs.pop_back();
i--;
}
else if (c == ')')
signs.pop_back();
else if (c != ' ')
signs.push_back(signs.back() * (c == '-' ? -1 : 1));
}
return total;
}

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def calculate(self, s):
total = 0
i, signs = 0, [1, 1]
while i < len(s):
c = s[i]
if c.isdigit():
start = i
while i < len(s) and s[i].isdigit():
i += 1
total += signs.pop() * int(s[start:i])
continue
if c in '+-(':
signs += signs[-1] * (1, -1)[c == '-'],
elif c == ')':
signs.pop()
i += 1
return total

Example trace:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Here's an example trace for input 3-(2+(9-4)).

remaining sign stack total
3-(2+(9-4)) [1, 1] 0
-(2+(9-4)) [1] 3
(2+(9-4)) [1, -1] 3
2+(9-4)) [1, -1, -1] 3
+(9-4)) [1, -1] 1
(9-4)) [1, -1, -1] 1
9-4)) [1, -1, -1, -1] 1
-4)) [1, -1, -1] -8
4)) [1, -1, -1, 1] -8
)) [1, -1, -1] -4
) [1, -1] -4
[1] -4

If you want to see traces for other examples, you can add this at the start inside the loop and after the loop (that’s for the Python solution, where it’s all easier):

1
print '%11s   %-16s %2d' % (s[i:], signs, total)

https://discuss.leetcode.com/topic/15775/simple-c-in-24-ms

Simple c++ in 24 ms

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
class Solution {
public:
int calculate(string s) {
// the given expression is always valid!!!
// only + and - !!!
// every + and - can be flipped base on it's depth in ().
stack<int> signs;
int sign = 1;
int num = 0;
int ans = 0;

// always transform s into ( s )
signs.push(1);

for (auto c : s) {
if (c >= '0' && c <= '9') {
num = 10 * num + c - '0';
} else if (c == '+' || c == '-') {
ans = ans + signs.top() * sign * num;
num = 0;
sign = (c == '+' ? 1 : -1);
} else if (c == '(') {
signs.push(sign * signs.top());
sign = 1;
} else if (c == ')') {
ans = ans + signs.top() * sign * num;
num = 0;
signs.pop();
sign = 1;
}
}

if (num) {
ans = ans + signs.top() * sign * num;
}

return ans;
}
};

python


https://discuss.leetcode.com/topic/25775/python-concise-solution-with-stack

Python concise solution with stack.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def calculate(self, s):
res, num, sign, stack = 0, 0, 1, []
for ss in s:
if ss.isdigit():
num = 10*num + int(ss)
elif ss in ["-", "+"]:
res += sign*num
num = 0
sign = [-1, 1][ss=="+"]
elif ss == "(":
stack.append(res)
stack.append(sign)
sign, res = 1, 0
elif ss == ")":
res += sign*num
res *= stack.pop()
res += stack.pop()
num = 0
return res + num*sign

https://discuss.leetcode.com/topic/37951/python-with-stack

Python with stack

This solution uses stack to store previous result and sign when encounter a “(“

For this problem storing sign is enough, and will be faster.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def calculate(self, s):
res, num, sign, stack = 0, 0, 1, [1]
for i in s+"+":
if i.isdigit():
num = 10*num + int(i)
elif i in "+-":
res += num * sign * stack[-1]
sign = 1 if i=="+" else -1
num = 0
elif i == "(":
stack.append(sign * stack[-1])
sign = 1
elif i == ")":
res += num * sign * stack[-1]
num = 0
stack.pop()
return res

https://discuss.leetcode.com/topic/15932/ac-python-solution

AC Python Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def calculate(self, s):
s = '+(+' + s + ')'
s = s.replace('+-', '-').replace('++', '+') # for the corner case '-5', '+5'
stack = []
for i in s:
if i == ')':
total = 0
while stack[-1] != '(':
total += int(stack.pop())
stack.pop()
sign = 1 if stack.pop() == '+' else -1
stack.append(sign * total)
elif i.isdigit() and stack[-1][-1] in '+-0123456789':
stack[-1] += i
elif i != ' ':
stack.append(i)
return stack[0]

java


https://discuss.leetcode.com/topic/15816/iterative-java-solution-with-stack

Iterative Java solution with stack

Simple iterative solution by identifying characters one by one. One important thing is that the input is valid, which means the parentheses are always paired and in order.

Only 5 possible input we need to pay attention:

  1. digit: it should be one digit from the current number
  2. ‘+’: number is over, we can add the previous number and start a new number
  3. ‘-‘: same as above
  4. ‘(‘: push the previous result and the sign into the stack, set result to 0, just calculate the new result within the parenthesis.
  5. ‘)’: pop out the top two numbers from stack, first one is the sign before this pair of parenthesis, second is the temporary result before this pair of parenthesis. We add them together.

Finally if there is only one number, from the above solution, we haven’t add the number to the result, so we do a check see if the number is zero.

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
public int calculate(String s) {
Stack<Integer> stack = new Stack<Integer>();
int result = 0;
int number = 0;
int sign = 1;
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if(Character.isDigit(c)){
number = 10 * number + (int)(c - '0');
}else if(c == '+'){
result += sign * number;
number = 0;
sign = 1;
}else if(c == '-'){
result += sign * number;
number = 0;
sign = -1;
}else if(c == '('){
//we push the result first, then sign;
stack.push(result);
stack.push(sign);
//reset the sign and result for the value in the parenthesis
sign = 1;
result = 0;
}else if(c == ')'){
result += sign * number;
number = 0;
result *= stack.pop(); //stack.pop() is the sign before the parenthesis
result += stack.pop(); //stack.pop() now is the result calculated before the parenthesis

}
}
if(number != 0) result += sign * number;
return result;
}

https://discuss.leetcode.com/topic/15816/iterative-java-solution-with-stack/2

+1 for your concise and clean code. My solution seems to be really different from others.
First I reformed the input expression by rules of:

  1. remove all ‘(‘, ‘)’, ‘ ‘;
  2. reverse the express string;
  3. add ‘+’ or ‘-‘ to the end of the express.
    By this approach, the reformed expression will be easy to handled.
1
2
3
4
"1 + 1"                             =>   "1+1+"
" 2-1 + 2 " => "2+1-2+"
"(1+(4+5+2)-3)+(6+8)" => "8+6+3-2+5+4+1+"
"2-(5-6)" => "6+5-2+"

Java code:

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
public int calculate(String s) {
if(s == null)
return 0;
s = reform(s);
int result = 0, num = 0, base = 1;
for(char c: s.toCharArray())
switch(c){
case '+': result += num; num = 0; base = 1; break;
case '-': result -= num; num = 0; base = 1; break;
default: num += (c - '0') * base; base *= 10;
}
return result;
}

private String reform(String s) {
StringBuilder sb = new StringBuilder();
Stack<Boolean> stack = new Stack<>();
stack.push(true);
boolean add = true;
for(char c: s.toCharArray())
switch(c){
case ' ': break;
case '(': stack.push(add); break;
case ')': stack.pop(); break;
case '+':
add = stack.peek();
sb.append(stack.peek() ? '+' : '-');
break;
case '-':
add = !stack.peek();
sb.append(stack.peek() ? '-' : '+');
break;
default: sb.append(c);
}
if(sb.charAt(0) != '+' || sb.charAt(0) != '-')
sb.insert(0, '+');
return sb.reverse().toString();
}

https://discuss.leetcode.com/topic/33044/java-easy-version-to-understand

JAVA———–Easy Version To Understand!!!!!

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
public static int calculate(String s) {
int len = s.length(), sign = 1, result = 0;
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < len; i++) {
if (Character.isDigit(s.charAt(i))) {
int sum = s.charAt(i) - '0';
while (i + 1 < len && Character.isDigit(s.charAt(i + 1))) {
sum = sum * 10 + s.charAt(i + 1) - '0';
i++;
}
result += sum * sign;
} else if (s.charAt(i) == '+')
sign = 1;
else if (s.charAt(i) == '-')
sign = -1;
else if (s.charAt(i) == '(') {
stack.push(result);
stack.push(sign);
result = 0;
sign = 1;
} else if (s.charAt(i) == ')') {
result = result * stack.pop() + stack.pop();
}

}
return result;
}

java

28ms, September 13, 2016

https://discuss.leetcode.com/topic/33044/java-easy-version-to-understand

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
public class Solution {
public int calculate(String s) {
int len = s.length(), sign = 1, result = 0;
Stack<Integer> stack = new Stack<Integer>();
for(int i = 0; i < len; i++){
if(Character.isDigit(s.charAt(i))){
int sum = s.charAt(i) - '0';
while(i + 1 < len && Character.isDigit(s.charAt(i+1))){
sum = sum * 10 + s.charAt(i+1) - '0';
i++;
}
result += sum * sign;
}else if(s.charAt(i) == '+')
sign = 1;
else if(s.charAt(i) == '-')
sign = -1;
if(s.charAt(i)== '('){
stack.push(result);
stack.push(sign);
result = 0;
sign = 1;
}else if(s.charAt(i) == ')')
result = result * stack.pop() + stack.pop();
}
return result;
}
}
谢谢你,可爱的朋友。