{"id":6438,"date":"2020-03-09T13:33:55","date_gmt":"2020-03-09T20:33:55","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6438"},"modified":"2020-03-09T17:46:54","modified_gmt":"2020-03-10T00:46:54","slug":"leetcode-224-basic-calculator","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/recursion\/leetcode-224-basic-calculator\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 224. Basic Calculator"},"content":{"rendered":"\n<p>Implement a basic calculator to evaluate a simple expression string.<\/p>\n\n\n\n<p>The expression string may contain open&nbsp;<code>(<\/code>&nbsp;and closing parentheses&nbsp;<code>)<\/code>, the plus&nbsp;<code>+<\/code>&nbsp;or minus sign&nbsp;<code>-<\/code>,&nbsp;<strong>non-negative<\/strong>&nbsp;integers and empty spaces&nbsp;.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> \"1 + 1\"\n<strong>Output:<\/strong> 2\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> \" 2-1 + 2 \"\n<strong>Output:<\/strong> 3<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> \"(1+(4+5+2)-3)+(6+8)\"\n<strong>Output:<\/strong> 23<\/pre>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>You may assume that the given expression is always valid.<\/li><li><strong>Do not<\/strong>&nbsp;use the&nbsp;<code>eval<\/code>&nbsp;built-in library function.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Recursion<\/strong><\/h2>\n\n\n\n<p>Make a recursive call when there is an open parenthesis and return if there is close parenthesis.<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int calculate(string s) {    \n    function<int(int&#038;)> eval = [&](int& pos) {\n      int ret = 0;\n      int sign = 1;\n      int val = 0;\n      while (pos < s.size()) {\n        const char ch = s[pos];\n        if (isdigit(ch)) {\n          val = val * 10 + (s[pos++] - '0');\n        } else if (ch == '+' || ch == '-') {\n          ret += sign * val;\n          val = 0;\n          sign = ch == '+' ? 1 : -1;\n          ++pos;\n        } else if (ch == '(') {\n          val = eval(++pos);\n        } else if (ch == ')') {          \n          ++pos;\n          break;\n        } else {\n          ++pos;\n        }\n      }\n      return ret += sign * val;\n    };\n    int pos = 0;\n    return eval(pos);\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua\nclass Solution:\n  def calculate(self, s: str) -> int:\n    self.pos = 0    \n    def eval():\n      val = 0\n      sign = 1\n      ret = 0\n      while self.pos < len(s):\n        ch = s[self.pos]\n        if ch == ' ':\n          self.pos += 1\n        elif ch == '(':\n          self.pos += 1\n          val = eval()\n        elif ch == ')':\n          self.pos += 1\n          ret += sign * val\n          return ret\n        elif ch == '+' or ch == '-':\n          ret += sign * val\n          val = 0\n          sign = 1 if ch == '+' else -1\n          self.pos += 1\n        else:\n          val = val * 10 + (ord(ch) - ord('0'))\n          self.pos += 1\n      ret += val * sign\n      return ret\n    return eval()\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Implement a basic calculator to evaluate a simple expression string. The expression string may contain open&nbsp;(&nbsp;and closing parentheses&nbsp;), the plus&nbsp;+&nbsp;or minus sign&nbsp;-,&nbsp;non-negative&nbsp;integers and empty spaces&nbsp;.&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[153],"tags":[568,217,17],"class_list":["post-6438","post","type-post","status-publish","format-standard","hentry","category-recursion","tag-calculator","tag-hard","tag-recursion","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6438","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6438"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6438\/revisions"}],"predecessor-version":[{"id":6440,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6438\/revisions\/6440"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6438"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6438"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6438"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}