{"id":6442,"date":"2020-03-09T18:24:59","date_gmt":"2020-03-10T01:24:59","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6442"},"modified":"2020-03-09T18:40:23","modified_gmt":"2020-03-10T01:40:23","slug":"leetcode-227-basic-calculator-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/stack\/leetcode-227-basic-calculator-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 227. Basic Calculator II"},"content":{"rendered":"\n<p>Implement a basic calculator to evaluate a simple expression string.<\/p>\n\n\n\n<p>The expression string contains only&nbsp;<strong>non-negative<\/strong>&nbsp;integers,&nbsp;<code>+<\/code>,&nbsp;<code>-<\/code>,&nbsp;<code>*<\/code>,&nbsp;<code>\/<\/code>&nbsp;operators and empty spaces&nbsp;. The integer division should truncate toward zero.<\/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>\"3+2*2\"\n<strong>Output:<\/strong> 7\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> \" 3\/2 \"\n<strong>Output:<\/strong> 1<\/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> \" 3+5 \/ 2 \"\n<strong>Output:<\/strong> 5\n<\/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: Stack<\/strong><\/h2>\n\n\n\n<p>if operator is \u2018+\u2019 or \u2018-\u2019, push the current num * sign onto stack.<br>if operator &#8216;*&#8217; or &#8216;\/&#8217;, pop the last num from stack and * or \/ by the current num and push it back to stack.<\/p>\n\n\n\n<p>The answer is the sum of numbers on stack.<\/p>\n\n\n\n<p>3+2*2 =&gt; {3}, {3,2}, {3, 2*2} = {3, 4} =&gt; ans = 7<br>3 +5\/2 =&gt; {3}, {3,5}, {3, 5\/2} = {3, 2} =&gt; ans = 5<br>1 + 2*3 &#8211; 5 =&gt; {1}, {1,2}, {1,2*3} = {1,6}, {1, 6, -5} =&gt; ans = 2<\/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    vector<int> nums;    \n    char op = '+';\n    int cur = 0;\n    int pos = 0;\n    while (pos < s.size()) {\n      if (s[pos] == ' ') {\n        ++pos;\n        continue;\n      }\n      while (isdigit(s[pos]) &#038;&#038; pos < s.size())\n        cur = cur * 10 + (s[pos++] - '0');      \n      if (op == '+' || op == '-') {\n        nums.push_back(cur * (op == '+' ? 1 : -1));\n      } else if (op == '*') {\n        nums.back() *= cur;\n      } else if (op == '\/') {\n        nums.back() \/= cur;\n      }\n      cur = 0;      \n      op = s[pos++];\n    }\n    return accumulate(begin(nums), end(nums), 0);\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    nums = []\n    op = '+'\n    cur = 0\n    i = 0\n    while i < len(s):\n      if s[i] == ' ': \n        i += 1\n        continue\n      while i < len(s) and s[i].isdigit():\n        cur = cur * 10 + ord(s[i]) - ord('0')\n        i += 1      \n      if op in '+-':\n        nums.append(cur * (1 if op == '+' else -1))\n      elif op == '*':\n        nums[-1] *= cur\n      elif op == '\/':\n        sign = -1 if nums[-1] < 0 or cur < 0 else 1\n        nums[-1] = abs(nums[-1]) \/\/ abs(cur) * sign\n      cur = 0\n      if (i < len(s)): op = s[i]\n      i += 1    \n    return sum(nums)\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Related Problems<\/strong><\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/recursion\/leetcode-224-basic-calculator\/\">https:\/\/zxi.mytechroad.com\/blog\/recursion\/leetcode-224-basic-calculator\/<\/a><\/li><li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/recursion\/leetcode-736-parse-lisp-expression\/\">https:\/\/zxi.mytechroad.com\/blog\/recursion\/leetcode-736-parse-lisp-expression\/<\/a><\/li><li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-282-expression-add-operators\/\">https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-282-expression-add-operators\/<\/a><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Implement a basic calculator to evaluate a simple expression string. The expression string contains only&nbsp;non-negative&nbsp;integers,&nbsp;+,&nbsp;-,&nbsp;*,&nbsp;\/&nbsp;operators and empty spaces&nbsp;. The integer division should truncate toward zero.&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[407],"tags":[568,177,180],"class_list":["post-6442","post","type-post","status-publish","format-standard","hentry","category-stack","tag-calculator","tag-medium","tag-stack","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6442","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=6442"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6442\/revisions"}],"predecessor-version":[{"id":6446,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6442\/revisions\/6446"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6442"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6442"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6442"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}