227. Basic Calculator II

  • 28.5%

https://leetcode.com/problems/basic-calculator-ii/#/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.

You may assume that the given expression is always valid.

1
2
3
4
Some examples:
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

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


方法一:

学习一个str的方法,find_first_not_of

find_first_not_of()

isdigit函数,判断是否为数字

https://discuss.leetcode.com/topic/17323/my-16-ms-no-stack-one-pass-short-c-solution

My 16 ms No stack One pass short C++ solution

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
class Solution {
public:
int calculate(string s) {
int result = 0, cur_res = 0;
char op = '+';
for(int pos = s.find_first_not_of(' '); pos < s.size(); pos = s.find_first_not_of(' ', pos)) {
if(isdigit(s[pos])) {
int tmp = s[pos] - '0';
while(++pos < s.size() && isdigit(s[pos]))
tmp = tmp*10 + (s[pos] - '0');
switch(op) {
case '+' : cur_res += tmp; break;
case '-' : cur_res -= tmp; break;
case '*' : cur_res *= tmp; break;
case '/' : cur_res /= tmp; break;
}
}
else {
if(s[pos] == '+' || s[pos] == '-') {
result += cur_res;
cur_res = 0;
}
op = s[pos++];
}
}
return result + cur_res;
}
};

https://discuss.leetcode.com/topic/30568/c-stack-solution

C++ stack solution.

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
int calculate(string s) {
stack<int> myStack;
char sign = '+';
int res = 0, tmp = 0;
for (unsigned int i = 0; i < s.size(); i++) {
if (isdigit(s[i]))
tmp = 10*tmp + s[i]-'0';
if (!isdigit(s[i]) && !isspace(s[i]) || i == s.size()-1) {
if (sign == '-')
myStack.push(-tmp);
else if (sign == '+')
myStack.push(tmp);
else {
int num;
if (sign == '*' )
num = myStack.top()*tmp;
else
num = myStack.top()/tmp;
myStack.pop();
myStack.push(num);
}
sign = s[i];
tmp = 0;
}
}
while (!myStack.empty()) {
res += myStack.top();
myStack.pop();
}
return res;
}

https://discuss.leetcode.com/topic/16807/17-lines-c-easy-20-ms

17 lines C++, easy, 20 ms

If you don’t like the 44 - op ASCII trick, you can use op == ‘+’ ? 1 : -1 instead. And wow, I didn’t know C++ has or. I’m a Python guy and wrote that out of habit and only realized it after getting this accepted :-)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int calculate(string s) {
istringstream in('+' + s + '+');
long long total = 0, term = 0, n;
char op;
while (in >> op) {
if (op == '+' or op == '-') {
total += term;
in >> term;
term *= 44 - op;
} else {
in >> n;
if (op == '*')
term *= n;
else
term /= n;
}
}
return total;
}


https://discuss.leetcode.com/topic/17213/my-28ms-c-code-with-two-stacks-one-for-op-one-for-oprand-extension-to-cover-also-given

My 28ms C++ code with two stacks (one for op, one for oprand), extension to cover ‘(‘ & ‘)’ also given

Use two stacks : one to save operators, one to save oprands. Every time, if we get a digit, then update curNum, if we get an operator, then it means we get a complete oprand, which is saved in curNum; if the last operator is * or /, then calculate it, otherwise, just save curNum and s[i] (new operator) in the stacks. At last, the opS stack has only “+” & “-“, which are the sign of the corresponding operands saved in numS. Then we do sum to get the result.

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
class Solution {
public:
int calculate(string s) {
stack<char> opS;
stack<int> numS;
s.push_back(')'); // to make sure the last operand will be saved in the stack e.g. 1+2*3), 2*3 will be calculated and push in the stack
opS.push('+'); // sign for the first operand

int i, curNum, len = s.size(), res =0;
for(i=0,curNum=0; i<len; ++i)
{
if(isdigit(s[i])) curNum = curNum*10 + s[i] -'0'; // digit, recover the oprand
else if(isspace(s[i])) continue; // skip the space
else
{
switch(opS.top())
{
case '*': // if the last operator is * / , do calculation
case '/':
curNum = opS.top()=='/'?numS.top()/curNum : numS.top()*curNum;
opS.pop();
numS.pop();
}
numS.push(curNum); /
curNum = 0;
opS.push(s[i]);
}
}
opS.pop(); // skip the ")"
while(!opS.empty()) {res += (opS.top()=='-')? -numS.top(): numS.top(); opS.pop(); numS.pop();}
return res;
}
};

The below version covers both +-*/ and ()

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
class Solution {
public:
int calculate(string s) {
stack<char> opS;
stack<int> numS;
s = '(' + s + ')';

int i, curNum = 0, len = s.size();
for(i=0; i<len; ++i)
{
if(isdigit(s[i])) curNum = curNum*10 + s[i] -'0';
else if(isspace(s[i])) continue;
else if(s[i] == '(')
{
opS.push('(');
opS.push('+');
}
else
{
switch(opS.top())
{
case '*':
case '/':
curNum = opS.top()=='/'?numS.top()/curNum : numS.top()*curNum;
opS.pop();
numS.pop();
}
switch(s[i])
{
case ')':
if('-'== opS.top()) curNum = -curNum;
opS.pop();

while(opS.top()!='(')
{
curNum += (opS.top()=='-')? -numS.top(): numS.top();
opS.pop();
numS.pop();
}
opS.pop(); // skip '('
break;
default: //+,-,*,/
opS.push(s[i]);
numS.push(curNum);
curNum = 0;
}
}
}
return curNum;
}
};

https://discuss.leetcode.com/topic/22170/python-short-solution-with-stack

Python short solution with stack.

212ms, 79.87%, September 22, 2016

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def calculate(self, s):
if not s:
return "0"
stack, num, sign = [], 0, "+"
for i in xrange(len(s)):
if s[i].isdigit():
num = num*10+ord(s[i])-ord("0")
if (not s[i].isdigit() and not s[i].isspace()) or i == len(s)-1:
if sign == "-":
stack.append(-num)
elif sign == "+":
stack.append(num)
elif sign == "*":
stack.append(stack.pop()*num)
else:
tmp = stack.pop()
if tmp//num < 0 and tmp%num != 0:
stack.append(tmp//num+1)
else:
stack.append(tmp//num)
sign = s[i]
num = 0
return sum(stack)

https://discuss.leetcode.com/topic/16803/easy-7-12-lines-three-solutions

Easy 7-12 lines, Three solutions

Three quite different Python solutions.

Solution 1: Split the splits (10 lines, 520 ms)

Split the expression into terms on + and -. Split each term into numbers on * and /.

1
2
3
4
5
6
7
8
9
10
11
def calculate(self, s):
total = 0
outer = iter(['+'] + re.split('([+-])', s))
for addsub in outer:
inner = iter(['*'] + re.split('([*/])', next(outer)))
term = 1
for muldiv in inner:
n = int(next(inner))
term = term*n if muldiv == '*' else term/n
total += term if addsub == '+' else -term
return total

Solution 2: Process tokens from left to right (12 lines, 224 ms):

Iterate over the tokens (numbers and operators), keeping track of the current total, the current term sign (+1 or -1), and the current term value.

1
2
3
4
5
6
7
8
9
10
11
12
13
def calculate(self, s):
tokens = iter(re.findall('\d+|\S', s))
total, sign = 0, 1
for token in tokens:
if token in '+-':
total += sign * term
sign = ' +'.find(token)
elif token in '*/':
n = int(next(tokens))
term = term*n if token == '*' else term/n
else:
term = int(token)
return total + sign * term

I could make that one more space-efficient with

1
tokens = (m.group() for m in re.finditer('\d+|\S', s))

but that’s less pretty and it actually increased the runtime by about 100 ms.

Also, I could add + to the input (i.e., findall(…, s + ‘+’)), then I could just return total and wouldn’t have to add the final term there. Pretty much doesn’t change the runtime.

Solution 3: First or second operation, repeat… (7 lines, 244 ms)

As long as there is any operation left to do, do either the first or the second operation, depending on what they are. Implemented by putting the tokens in a list in reverse order, because making a change at the end of the list is O(1) and making a change at the start would be O(n).

1
2
3
4
5
6
7
8
def calculate(self, s):
t = re.findall('\d+|\S', s + '+0')[::-1]
t[::2] = map(int, t[::2])
while len(t) > 3:
i = len(t) - 5 + 2 * (t[-2] in '*/' or t[-4] not in '*/')
b, op, a = t[i:i+3]
t[i:i+3] = a+b if op=='+' else a-b if op=='-' else a*b if op=='*' else a/b,
return t[2]
谢谢你,可爱的朋友。