What is the inverse Polish expression?

The operator follows the operand by 3 * 4 ===> 3, 4 *, so it is also called a postfix expression.

When using inverse Polish expressions, parentheses are not required. In infix expressions, for example :(3-4) * 5, we need to use parentheses to increase the priority of the minus sign, whereas in inverse polish expressions, parentheses are not needed, 3, 4-5 *, followed directly by the 3, 4 operand by a – sign to indicate that 3-4 is evaluated first.

A few more examples:

  • 3 minus 4 times 5= = = >3, 4, 5 times minus
  • 4 plus 13/5.= = = >4, 13, 5 over plus
  • 2 plus 1 times 3 is equal to 9= = = >2, 1 plus 3 times

Manually evaluate the inverse Polish expression

How do we evaluate a complex inverse Polish expression?

For example, 10 6 9 3 + -11 * / * 17 + 5 +

We start by iterating through the inverse Polish expression string from scratch

  1. Meet the first one+ 号 9 plus 3 is 12And now the expression is,10 6 12 -11 * / * 17 + 5 +
  2. Meet the second* 号 Minus 12 times minus 11 is minus 132And now the expression is10 6-132 / * 17 + 5 +
  3. Meet the third/ 号 6 / -132 = -0.04The current expression10 -0.04 * 17 + 5 +
  4. Meet the fourth* 号 10 * -0.04 = -0.4The current expression-0.4 17 + 5 +
  5. Meet the fifth+ 号 -0.4 + 17 = 16.6The current expression16.6 5 +
  6. Meet the sixth+ 号 16.6 + 5 = 21.6

Conversion of infix expressions

How do I convert an infix expression to an inverse Polish expression? We need to use two stacks, one for numbers and one for operators.

Here’s an example :(2 + 1) * 3

// The first step, encountered (do not handle= = = = = = = = = = = = = = | | | | | | | | | | | | | | | | | | | | = = = = = = = = = = = = = = operator// In the second step, 2 is encountered and added to the number stack
=======        =======
｜   ｜         ｜   ｜
｜   ｜         ｜   ｜
｜   ｜         ｜   ｜
｜   ｜         ｜   ｜
｜ 2| | | ======= ======= number operator// The third step encounters +, which is added to the operator stack
=======        =======
｜   ｜         ｜   ｜
｜   ｜         ｜   ｜
｜   ｜         ｜   ｜
｜   ｜         ｜   ｜
｜ 2| | + | ======= ======= numeric operator// Step 4 encounters 1 and adds it to the digital stack
=======        =======
｜   ｜         ｜   ｜
｜   ｜         ｜   ｜
｜   ｜         ｜   ｜
｜ 1| | | |2| | + | ======= ======= numeric operator// Encountered in step 5), pops the top of the operator stack and pushes it onto the digital stack
=======        =======
｜   ｜         ｜   ｜
｜   ｜         ｜   ｜
｜ + ｜         ｜   ｜
｜ 1| | | |2| | | ======= ======= number operator/ / step 6
=======        =======
｜   ｜         ｜   ｜
｜   ｜         ｜   ｜
｜ + ｜         ｜   ｜
｜ 1| | | |2| | * | ======= ======= number operator/ / step 7
=======        =======
｜   ｜         ｜   ｜
｜ 3 ｜         ｜   ｜
｜ + ｜         ｜   ｜
｜ 1| | | |2| | * | ======= ======= number operator// In step 8, pop the operators one by one and add them to the digital stack
=======        =======
｜   ｜         ｜   ｜
｜ 3 ｜         ｜   ｜
｜ + ｜         ｜   ｜
｜ 1| | | |2| | | * = = = = = = = = = = = = = = digital operator = = = = = = = = = = = = = = | | * | | |3 ｜         ｜   ｜
｜ + ｜         ｜   ｜
｜ 1| | | |2| | | ======= ======= the numeric operator results as follows:2 1 + 3 *
Copy the code

↓↓↓↓↓↓

// a js version of the stack
class Stack {
    constructor () {
        this.stack = []
    }
    push (v) {
        this.stack.push(v)
    }
    pop () {
        return this.stack.pop()
    }
    top () {
        return this.stack[this.stack.length - 1]
    }
    size () {
        return this.stack.length
    }
}
Copy the code
// infix expression
const expression = '((10 * (6 / ((9 + 3) * - 11))) + 17) + 5'

const transformRPN = (expression) = > {
    const operator = ['+'.The '-'.The '*'.'/']

    // Stack of operators
    const operatorStack = new Stack()

    // Stack of numbers
    const operandStack = new Stack()

    const tokens = expression.split(' ')

    for (let i = 0; i < tokens.length; i++) {
        const token = tokens[i]
        if (operator.includes(token)) {
            operatorStack.push(token)
        } else {
            if (token === ') ') {
                operandStack.push(operatorStack.pop())
            } else {
                if (
                    typeof Number(token) === 'number'&&!isNaN(Number(token))
                ) {
                    operandStack.push(token)
                }
            }
        }
    }

    while (operatorStack.size()) {
        operandStack.push(operatorStack.pop())
    }
}

transformRPN(expression)

Copy the code

Code to achieve the inverse Polish expression calculation

Leetcode 150 is a similar problem.

For example: 2, 1 + 3 *


/ / the first step
=======        
｜   ｜         
｜   ｜         
｜   ｜      
｜   ｜       
｜ 2| = = = = = = =/ / the second step
=======        
｜   ｜         
｜   ｜         
｜   ｜      
｜ 1| |2| = = = = = = =// 2 + 1 = 3
=======        
｜   ｜         
｜   ｜         
｜   ｜      
｜   ｜       
｜ 3| = = = = = = =/ / step 4
=======        
｜   ｜         
｜   ｜         
｜   ｜      
｜ 3| |3| = = = = = = =3 * 3 = 9
=======        
｜   ｜         
｜   ｜         
｜   ｜      
｜   ｜       
｜ 9| = = = = = = =// get result 9
Copy the code

↓↓↓↓↓↓


const evalRPN = (tokens) = > {
    const operator = ['+'.The '-'.The '*'.'/']

    const stack = new Stack()

    for (let i = 0; i < tokens.length; i++) {
        if (operator.includes(tokens[i])) {
            const a = Number(stack.pop())
            const b = Number(stack.pop())
            let result = null
            switch (tokens[i]) {
                case '+':
                    result = a + b 
                    break
                case The '-':
                    result = b - a
                    break
                case The '*':
                    result = a * b
                    break
                case '/':
                    result = b / a
                    break
            }
            stack.push(result)
        } else {
            stack.push(tokens[i])
        }
    }

    return stack.top()
};
Copy the code

reference

  • Inverse Polish notation