Simulation volume leetcode [general] 150. evaluation of inverse Polish expression

Summary ： Simulation volume Leetcode Summary of questions

150. Evaluate the inverse Polish expression

according to Reverse Polish notation , Find the value of the expression .

Valid operators include  +、-、*、/ . Each operand can be an integer , It can also be another inverse Polish expression .

Be careful   The division between two integers retains only the integer part .

It can be guaranteed that the given inverse Polish expression is always valid . let me put it another way , The expression always yields a valid number and does not have a divisor of 0 The situation of .

Example  1：

Input ：tokens = [“2”,“1”,“+”,“3”,“*”]
Output ：9
explain ： This formula is transformed into a common infix arithmetic expression as ：((2 + 1) * 3) = 9
Example  2：

Input ：tokens = [“4”,“13”,“5”,“/”,“+”]
Output ：6
explain ： This formula is transformed into a common infix arithmetic expression as ：(4 + (13 / 5)) = 6
Example  3：

Input ：tokens = [“10”,“6”,“9”,“3”,“+”,“-11”,““,”/“,””,“17”,“+”,“5”,“+”]
Output ：22
explain ： This formula is transformed into a common infix arithmetic expression as ：
((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

Tips ：

1 <= tokens.length <= 104
tokens[i]  It's an operator （“+”、“-”、“*” or “/”）, Or in the range [-200, 200] An integer in

Reverse Polish notation ：

The inverse Polish expression is a suffix expression , The so-called suffix means that the operator is written after .

The usual formula is a infix expression , Such as ( 1 + 2 ) * ( 3 + 4 ) .
The inverse Polish expression of the formula is written as ( ( 1 2 + ) ( 3 4 + ) * ) .
The inverse Polish expression has two main advantages ：

There is no ambiguity in the expression after removing the brackets , Even if the above formula is written as 1 2 + 3 4 + * You can also calculate the correct result according to the order .
It is suitable for stack operation ： When it comes to numbers, it's on the stack ; When you encounter an operator, you take out two numbers at the top of the stack to calculate , And push the results into the stack

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Code ：

from leetcode_python.utils import *


class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for x in tokens:
            if x in '+-*/':
                b = stack.pop(-1)
                a = stack.pop(-1)
                stack.append(int(eval(f"{
      a}{
      x}{
      b}")))
            else:
                stack.append(x)
        return int(stack[0])


def test(data_test):
    s = Solution()
    data = data_test  # normal
    # data = [List2Node(data_test[0])] # list turn node
    return s.evalRPN(*data)


def test_obj(data_test):
    result = [None]
    obj = Solution(*data_test[1][0])
    for fun, data in zip(data_test[0][1::], data_test[1][1::]):
        if data:
            res = obj.__getattribute__(fun)(*data)
        else:
            res = obj.__getattribute__(fun)()
        result.append(res)
    return result


if __name__ == '__main__':
    datas = [
        [["10","6","9","3","+","-11","*","/","*","17","+","5","+"]],
    ]
    for data_test in datas:
        t0 = time.time()
        print('-' * 50)
        print('input:', data_test)
        print('output:', test(data_test))
        print(f'use time:{
      time.time() - t0}s')

remarks ：
GitHub：https://github.com/monijuan/leetcode_python

CSDN Summary ： Simulation volume Leetcode Summary of questions

You can add QQ Group communication ：1092754609

leetcode_python.utils See the description on the summary page for details
First brush questions , Then generated by script blog, If there is any mistake, please leave a message , I see it will be revised ！ thank you ！