- 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 | Some examples: |

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 | class Solution { |

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

C++ stack solution.

1 | int calculate(string s) { |

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 | int calculate(string s) { |

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 | class Solution { |

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

1 | class Solution { |

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

Python short solution with stack.

212ms, 79.87%, September 22, 2016

1 | def calculate(self, s): |

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 | def calculate(self, s): |

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 | def calculate(self, s): |

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 | def calculate(self, s): |