|
| 1 | +<h2><a href="https://leetcode.com/problems/evaluate-reverse-polish-notation">150. Evaluate Reverse Polish Notation</a></h2><h3>Medium</h3><hr><p>You are given an array of strings <code>tokens</code> that represents an arithmetic expression in a <a href="http://en.wikipedia.org/wiki/Reverse_Polish_notation" target="_blank">Reverse Polish Notation</a>.</p> |
| 2 | + |
| 3 | +<p>Evaluate the expression. Return <em>an integer that represents the value of the expression</em>.</p> |
| 4 | + |
| 5 | +<p><strong>Note</strong> that:</p> |
| 6 | + |
| 7 | +<ul> |
| 8 | + <li>The valid operators are <code>'+'</code>, <code>'-'</code>, <code>'*'</code>, and <code>'/'</code>.</li> |
| 9 | + <li>Each operand may be an integer or another expression.</li> |
| 10 | + <li>The division between two integers always <strong>truncates toward zero</strong>.</li> |
| 11 | + <li>There will not be any division by zero.</li> |
| 12 | + <li>The input represents a valid arithmetic expression in a reverse polish notation.</li> |
| 13 | + <li>The answer and all the intermediate calculations can be represented in a <strong>32-bit</strong> integer.</li> |
| 14 | +</ul> |
| 15 | + |
| 16 | +<p> </p> |
| 17 | +<p><strong class="example">Example 1:</strong></p> |
| 18 | + |
| 19 | +<pre> |
| 20 | +<strong>Input:</strong> tokens = ["2","1","+","3","*"] |
| 21 | +<strong>Output:</strong> 9 |
| 22 | +<strong>Explanation:</strong> ((2 + 1) * 3) = 9 |
| 23 | +</pre> |
| 24 | + |
| 25 | +<p><strong class="example">Example 2:</strong></p> |
| 26 | + |
| 27 | +<pre> |
| 28 | +<strong>Input:</strong> tokens = ["4","13","5","/","+"] |
| 29 | +<strong>Output:</strong> 6 |
| 30 | +<strong>Explanation:</strong> (4 + (13 / 5)) = 6 |
| 31 | +</pre> |
| 32 | + |
| 33 | +<p><strong class="example">Example 3:</strong></p> |
| 34 | + |
| 35 | +<pre> |
| 36 | +<strong>Input:</strong> tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] |
| 37 | +<strong>Output:</strong> 22 |
| 38 | +<strong>Explanation:</strong> ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 |
| 39 | += ((10 * (6 / (12 * -11))) + 17) + 5 |
| 40 | += ((10 * (6 / -132)) + 17) + 5 |
| 41 | += ((10 * 0) + 17) + 5 |
| 42 | += (0 + 17) + 5 |
| 43 | += 17 + 5 |
| 44 | += 22 |
| 45 | +</pre> |
| 46 | + |
| 47 | +<p> </p> |
| 48 | +<p><strong>Constraints:</strong></p> |
| 49 | + |
| 50 | +<ul> |
| 51 | + <li><code>1 <= tokens.length <= 10<sup>4</sup></code></li> |
| 52 | + <li><code>tokens[i]</code> is either an operator: <code>"+"</code>, <code>"-"</code>, <code>"*"</code>, or <code>"/"</code>, or an integer in the range <code>[-200, 200]</code>.</li> |
| 53 | +</ul> |
0 commit comments