Reverse Polish notation (RPN, or Reverse Polish notation), is a form of mathematical expression introduced by the Polish mathematician Jan Wucaszewicz in 1920. In Reverse Polish notation, all operators are placed after the operands, so it is also known as postfix notation. Inverse Polish notation does not require parentheses to identify the precedence of the operator.

The inverse Polish notation can be used to solve the problem of precedence operation of expressions. For example, for the infix expression 12 + (7-3) * 2 + 9/3, the inverse Polish representation should be: 12 7 3-2 * + 9 3 / +. The inverse Polish notation, though strange and unreadable, is good for computers.

The math we learned as children used infix expressions.

Transformation rules

The rule for inverse Polish notation is as follows: Initialize two stacks, S1 for temporary operators and S2 for inverse Polish expressions, and then walk each element of the expression from left to right:

  1. If the character is a number, push it directly into stack S2;
  2. If the extracted character is a (, it is pushed directly into the S1 stack.
  3. If the fetched character is an operator (such as + – * /), compare that operator to the top element of the S1 stack:
    • If the top stack element is “(“, push the operator to S1.
    • If the top element is an operator such as addition, subtraction, multiplication, and division, and the priority of that operator is greater than the priority of the top S1 operator, push that operator into the S1 stack. Otherwise, pop the top S1 operator into the S2 stack until the top S1 operator is below (but not equal to) the priority of the operator. The operator is then sent to the S1 stack.
  4. If the character is “) “, the top elements of S1 are ejected and pushed into S2 until “(” is encountered. Note that” (” is out of the stack but not pushed into S2.
  5. Repeat steps 1 through 4 until the traversal is complete. If there are operators in S1 stack, push them out of S1 stack one by one and into S2 stack.

Transformation of the sample

The inverse Polish notation can be used to solve the problem of precedence operation of expressions. For example, for the infix expression 12 + (7-3) * 2 + 9/3, the inverse Polish representation should be: 12 7 3-2 * + 9 3 / +. With this expression, we will step by step explain how to convert our common operation expression (infix expression) into inverse Polish notation and evaluate it.

The input operation S1 S2
12 Stack S2 [] [12]
+ Stack S1 [+] [12]
( Stack S1 [+, (] [12]
7 Stack S2 [+, (] [12, 7)
– The top of S1 stack is (,, so push directly [+, -] [12, 7)
3 Stack S2 [+, -] [12, 7, 3]
) At the top of S1, the “-” and “(” are removed from the stack in sequence, and the” – “is pushed into S2 [+] [12, 7, 3 -]
* The multiplier has a higher priority than the plus sign, so push S1 directly [+, *] [12, 7, 3 -]
2 Stack S2 [+, *] [12, 7, 3, -, 2]
+ The plus sign has a priority less than The Times sign is equal to the plus sign, so push The Times sign and the plus sign of S1 into S2, and then push the plus sign into S1 [+] [12, 7, 3, -, 2, *, +]
9 Stack S2 [+] [12, 7, 3, -, 2, *, +, 9]
/ The divisor has a higher priority than the plus sign, and S1 is pushed directly [+ /] [12, 7, 3, -, 2, *, +, 9]
3 Stack S2 [+ /] [12, 7, 3, -, 2, *, +, 9, 3]
The remaining operators in the S1 stack go off the stack one by one and are pushed into the S2 stack [] [12, 7, 3, -, 2, *, +, 9, 3, /, +]

Stack S2 for [7, 12, 3 -, 2, *, +, 9, 3, /, +], converted to a string that is 7 * 9 + 3 / + 3 to 2

evaluation

Once the infix expression has been converted to inverse Polish notation, evaluation is straightforward. The way to do this is to iterate through the inverse Polish expression, if you encounter an operator, take out the first two numbers of the operator and operate, then replace the symbol with the result of the operation, and repeat the process until you get a number that is the result of the expression. Take 12 7 3-2 * + 9 3 / + as an example:

The operator Before operating operation After the operation
– 12, 7, 3 minus 2 times plus 9, 3 over plus The minus sign is preceded by a 7 and a 3, and a 7 and a 3 pop up. 7-3 = 4. 4 replaces the minus sign 12, 4, 2 times plus 9, 3 over plus
* 12, 4, 2 times plus 9, 3 over plus 4 * 2 = 8. 8 replaces the multiplication sign 12, 8 + 9, 3 / +
+ 12, 8 + 9, 3 / + 12 and 8 are in front of the plus sign, and 12 and 8 pop up. 12 + 8 = 20. 20 replaces the plus sign 20, 9, 3 / +
/ 20, 9, 3 / + 9 and 3 precede the division sign, and pop up 9 and 3. 9/3 = 3. 3 replaces the division sign 3 + 20
+ 3 + 20 Before the plus sign are 20 and 3, and 20 and 3 pop up. 20 + 3 = 23 23

So. 12 plus 7 minus 3 times 2 plus 9/3 is 23.

LeetCode bo

Evaluate the inverse Polish expression

150. Evaluate the inverse Pollan expression

var evalRPN = function(tokens) {
  const stack = [];
  const length = tokens.length;
  for(let i = 0; i < length; i++) {
    const c = tokens[i];
    if (c === '+' || c === The '-' || c === The '*' || c === '/') {
      const val1 = parseInt(stack.pop());
      const val2 = parseInt(stack.pop());
      switch(c) {
        case '+':
          stack.push(val2 + val1)
          break;
        case The '-':
          stack.push(val2 - val1);
          break
        case The '*':
          stack.push(val2 * val1);
          break;
        case '/':
          stack.push(parseInt(val2 / val1))
          break; }}else {
      stack.push(c)
    }
  }
  return stack[0];
};
Copy the code