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 .
Example 1:
Input: "1 + 1" Output: 2
Example 2:
Input: " 2-1 + 2 " Output: 3
Example 3:
Input: "(1+(4+5+2)-3)+(6+8)" Output: 23
Note:
- You may assume that the given expression is always valid.
- Do not use the
evalbuilt-in library function.
Solution: Recursion
Make a recursive call when there is an open parenthesis and return if there is close parenthesis.
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 29 30 31 32 |
// Author: Huahua class Solution { public: int calculate(string s) { function<int(int&)> eval = [&](int& pos) { int ret = 0; int sign = 1; int val = 0; while (pos < s.size()) { const char ch = s[pos]; if (isdigit(ch)) { val = val * 10 + (s[pos++] - '0'); } else if (ch == '+' || ch == '-') { ret += sign * val; val = 0; sign = ch == '+' ? 1 : -1; ++pos; } else if (ch == '(') { val = eval(++pos); } else if (ch == ')') { ++pos; break; } else { ++pos; } } return ret += sign * val; }; int pos = 0; return eval(pos); } }; |
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 26 27 28 29 30 |
# Author: Huahua class Solution: def calculate(self, s: str) -> int: self.pos = 0 def eval(): val = 0 sign = 1 ret = 0 while self.pos < len(s): ch = s[self.pos] if ch == ' ': self.pos += 1 elif ch == '(': self.pos += 1 val = eval() elif ch == ')': self.pos += 1 ret += sign * val return ret elif ch == '+' or ch == '-': ret += sign * val val = 0 sign = 1 if ch == '+' else -1 self.pos += 1 else: val = val * 10 + (ord(ch) - ord('0')) self.pos += 1 ret += val * sign return ret return eval() |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
[…] https://zxi.mytechroad.com/blog/recursion/leetcode-224-basic-calculator/ […]