“This is the second day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

Evaluate the inverse Polish expression

Evaluate the expression according to the inverse Polish notation.

Valid operators include +, -, *, and /. Each operand can be an integer or another inverse Polish expression.

Note: Integer division retains only integer parts. Given the inverse Polish expression is always valid. In other words, the expression always yields a valid value and never has a divisor of 0.

Inverse Polish expression:

An inverse Polish expression is an expression with a suffix, which means the operator is written after it.

The usual formula is an infix expression, such as (1 + 2) * (3 + 4). The inverse Polish expression of the formula is (1 2 +) (3 4 +) *). The inverse Polish expression has two main advantages:

After removing the parentheses, the expression has no ambiguity. Even if the above formula is written as 1, 2 + 3, 4 + *, the correct result can be calculated according to the order. Suitable for stack operation: the number is pushed into the stack; When encountering an operator, the top two numbers on the stack are calculated and the result is pushed onto the stack.

Source: LeetCode link: leetcode-cn.com/problems/ev… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

solution

Inverse Polish expressions are classic stack problems. First we need to consider both numerical and operator cases. If it is a number, the normal pressure on the stack, if it is an operator, the top two elements of the stack pop up, and then according to the operator to the corresponding rules for operation, and then the operation result is pushed onto the stack, has repeated the above operation, until the expression is all processed, pop up the operation result. In this process, we can use the Map operator to store the corresponding operation, or we can use the if comparison operator directly to use the corresponding operation, and finally note that the division operation only preserves the integer part

var evalRPN = function(tokens) {
    const stack = [];
    const s = new Map([["+".(a,b) = > a * 1 + b * 1],
        ["-".(a,b) = > b - a],
        ["*".(a,b) = > a * b],
        ["/".(a, b) = > (b / a) | 0]]);for(const x of tokens) {
        if(! s.has(x)) { stack.push(x);continue;
        }
        stack.push(s.get(x)(stack.pop(),stack.pop()))
    }
    return stack.pop();
};
Copy the code