150.Evaluate Reverse Polish Notation
===

###### tags: `Medium`,`Array`,`Math`,`Stack`

[150. Evaluate Reverse Polish Notation](https://leetcode.com/problems/evaluate-reverse-polish-notation/)

### 題目描述

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are `+`, `-`, `*`, and `/`. Each operand may be an integer or another expression.

**Note** that division between two integers should truncate toward zero.

It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

### 範例

**Example 1:**

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

**Example 2:**

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

**Example 3:**

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

**Constraints**:

* 1 <= `tokens.length` <= 10^4^
* `tokens[i]` is either an operator: `"+"`, `"-"`, `"*"`, or `"/"`, or an integer in the range `[-200, 200]`.

### 解答

#### C#

public class Solution {
    public int EvalRPN(string[] tokens) {
        Stack<int> operands = new();
        var operators = new string[] { "+", "-", "*", "/" };

        foreach (string token in tokens)
        {
            if (operators.Contains(token))
            {
                int operand2 = operands.Pop();
                int operand1 = operands.Pop();
                operands.Push(Calc(operand1, operand2, token));
            }
            else
            {
                operands.Push(int.Parse(token));
            }
        }

        return operands.Pop();

        static int Calc(int operand1, int operand2, string oper) => oper switch
        {
            "+" => operand1 + operand2,
            "-" => operand1 - operand2,
            "*" => operand1 * operand2,
            "/" => operand1 / operand2,
            _ => throw new ArgumentException(null, nameof(oper)),
        };
    }
}

>[name=Jim][time= Dec 17, 2022]

#### Python

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stk = []

        for token in tokens:
            if token in "+-*/":
                num2 = stk.pop()
                num1 = stk.pop()

                if token == '+':
                    stk.append(num1 + num2)
                elif token == '-':
                    stk.append(num1 - num2)
                elif token == '*':
                    stk.append(num1 * num2)
                elif token == '/':
                    stk.append(int(num1 / num2))
            else:
                stk.append(int(token))
                
        return stk.pop()

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)