{"id":5331,"date":"2019-07-22T20:56:28","date_gmt":"2019-07-23T03:56:28","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5331"},"modified":"2020-05-21T18:54:54","modified_gmt":"2020-05-22T01:54:54","slug":"leetcode-150-evaluate-reverse-polish-notation","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/stack\/leetcode-150-evaluate-reverse-polish-notation\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 150. Evaluate Reverse Polish Notation"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 150. Evaluate Reverse Polish Notation - \u5237\u9898\u627e\u5de5\u4f5c EP328\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/hFYs9LNKc5w?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>Evaluate the value of an arithmetic expression in&nbsp;<a href=\"http:\/\/en.wikipedia.org\/wiki\/Reverse_Polish_notation\" target=\"_blank\" rel=\"noreferrer noopener\">Reverse Polish Notation<\/a>.<\/p>\n\n\n\n<p>Valid operators are&nbsp;<code>+<\/code>,&nbsp;<code>-<\/code>,&nbsp;<code>*<\/code>,&nbsp;<code>\/<\/code>. Each operand may be an integer or another expression.<\/p>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Division between two integers should truncate toward zero.<\/li><li>The given RPN expression is always valid. That means the expression would always evaluate to a result and there won&#8217;t&nbsp;be any&nbsp;divide&nbsp;by zero operation.<\/li><\/ul>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> [\"2\", \"1\", \"+\", \"3\", \"*\"]\n<strong>Output:<\/strong> 9\n<strong>Explanation:<\/strong> ((2 + 1) * 3) = 9\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> [\"4\", \"13\", \"5\", \"\/\", \"+\"]\n<strong>Output:<\/strong> 6\n<strong>Explanation:<\/strong> (4 + (13 \/ 5)) = 6\n<\/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> [\"10\", \"6\", \"9\", \"3\", \"+\", \"-11\", \"*\", \"\/\", \"*\", \"17\", \"+\", \"5\", \"+\"]\n<strong>Output:<\/strong> 22\n<strong>Explanation:<\/strong> \n  ((10 * (6 \/ ((9 + 3) * -11))) + 17) + 5\n= ((10 * (6 \/ (12 * -11))) + 17) + 5\n= ((10 * (6 \/ -132)) + 17) + 5\n= ((10 * 0) + 17) + 5\n= (0 + 17) + 5\n= 17 + 5\n= 22<\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Stack<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/150-ep328.png\" alt=\"\" class=\"wp-image-6807\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/150-ep328.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/150-ep328-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/150-ep328-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>Use a stack to store the operands, pop two whenever there is an operator, compute the result and push back to the stack.<\/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++\">\nclass Solution {\npublic:\n  int evalRPN(vector<string>& tokens) {\n    stack<int> s;\n    for (const string& token : tokens) {\n      if (isdigit(token.back())) {\n        s.push(stoi(token));\n      } else {\n        int n2 = s.top(); s.pop();\n        int n1 = s.top(); s.pop();        \n        int n = 0;\n        switch (token[0]) {\n          case '+': n = n1 + n2; break;\n          case '-': n = n1 - n2; break;\n          case '*': n = n1 * n2; break;\n          case '\/': n = n1 \/ n2; break;\n        }\n        s.push(n);\n      }\n    }\n    return s.top();\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\"># Author: Huahua\nclass Solution:\n  def evalRPN(self, tokens: List[str]) -&gt; int:\n    s = []\n    for token in tokens:\n      if token[-1] not in '+-*\/':\n        s.append(int(token))\n      else:\n        n2 = s.pop()\n        n1 = s.pop()\n        if token == '+': n = n1 + n2\n        elif token == '-': n = n1 - n2\n        elif token == '*': n = n1 * n2\n        elif token == '\/': n = int(n1 \/ n2)\n        s.append(n)\n    return s[-1]\n<\/pre>\n<\/div><\/div>\n\n\n\n<p>Just for fun, f-string with eval<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\"># Author: Huahua\nclass Solution:\n  def evalRPN(self, tokens: List[str]) -&gt; int:\n    s = []\n    for token in tokens:\n      if token[-1] not in '+-*\/':\n        s.append(int(token))\n      else:\n        n2 = s.pop()\n        n1 = s.pop()\n        s.append(int(eval(f'{n1}{token}{n2}')))\n    return s[-1]\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Evaluate the value of an arithmetic expression in&nbsp;Reverse Polish Notation. Valid operators are&nbsp;+,&nbsp;-,&nbsp;*,&nbsp;\/. Each operand may be an integer or another expression. Note: Division between&#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":[177,180],"class_list":["post-5331","post","type-post","status-publish","format-standard","hentry","category-stack","tag-medium","tag-stack","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5331","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=5331"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5331\/revisions"}],"predecessor-version":[{"id":6808,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5331\/revisions\/6808"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5331"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5331"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5331"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}