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:
Input: "3+2*2" Output: 7
Example 2:
Input: " 3/2 " Output: 1
Example 3:
Input: " 3+5 / 2 " Output: 5
Note:
- You may assume that the given expression is always valid.
- Do not use the
evalbuilt-in library function.
Solution: Stack
if operator is ‘+’ or ‘-’, push the current num * sign onto stack.
if operator ‘*’ or ‘/’, pop the last num from stack and * or / by the current num and push it back to stack.
The answer is the sum of numbers on stack.
3+2*2 => {3}, {3,2}, {3, 2*2} = {3, 4} => ans = 7
3 +5/2 => {3}, {3,5}, {3, 5/2} = {3, 2} => ans = 5
1 + 2*3 – 5 => {1}, {1,2}, {1,2*3} = {1,6}, {1, 6, -5} => ans = 2
Time complexity: O(n)
Space complexity: O(n)
C++
|
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 |
// Author: Huahua class Solution { public: int calculate(string s) { vector<int> nums; char op = '+'; int cur = 0; int pos = 0; while (pos < s.size()) { if (s[pos] == ' ') { ++pos; continue; } while (isdigit(s[pos]) && pos < s.size()) cur = cur * 10 + (s[pos++] - '0'); if (op == '+' || op == '-') { nums.push_back(cur * (op == '+' ? 1 : -1)); } else if (op == '*') { nums.back() *= cur; } else if (op == '/') { nums.back() /= cur; } cur = 0; op = s[pos++]; } return accumulate(begin(nums), end(nums), 0); } }; |
python3
|
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 |
# Author: Huahua class Solution: def calculate(self, s: str) -> int: nums = [] op = '+' cur = 0 i = 0 while i < len(s): if s[i] == ' ': i += 1 continue while i < len(s) and s[i].isdigit(): cur = cur * 10 + ord(s[i]) - ord('0') i += 1 if op in '+-': nums.append(cur * (1 if op == '+' else -1)) elif op == '*': nums[-1] *= cur elif op == '/': sign = -1 if nums[-1] < 0 or cur < 0 else 1 nums[-1] = abs(nums[-1]) // abs(cur) * sign cur = 0 if (i < len(s)): op = s[i] i += 1 return sum(nums) |