波兰表达式 & 逆波兰表达式

1、概述

1.1、什么是波兰表达式

先来看看维基百科对于波兰表达式和逆波兰表单的解释：

波兰表示法（Polish notation，或波兰记法），是一种逻辑、算术和代数表示方法，其特点是操作符置于操作数的前面，因此也称做前缀表示法。如果操作符的元数（arity）是固定的，则语法上不需要括号仍然能被无歧义地解析。

逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式形式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。

这个解释听起来有点难理解。波兰表达式也称为前缀表达式，逆波兰表达式也称为后缀表达式。以表达式 (1 + 2) * (3 + 4) 为例，这个表达式称为中缀表达式。

与中缀表达式相比，前缀表达式和后缀表达式有个好处，没有圆括号，在计算的时候无需考虑优先级，能够提高计算机的运算效率。

1.2、相互转化

中缀表达式得出的前缀后缀表达式不唯一，只要不破坏中缀表达式里本身的运算优先级，就能得到与中缀表达式得到一致的结果。

• 将中缀表达式依据优先级关系括起来，将运算符移到对应括号的前方，去掉括号，即得波兰表达式。
• 将中缀表达式依据优先级关系括起来，将运算符移到对应括号的后方，去掉括号，即得逆波兰表达式。

举例说明：

中缀表达式 : a + b

前缀表达式 ： + a b

后缀表达式 :  a b + 

中缀表达式 : ( a + b ) * c + d - ( e + g ) * h

前缀表达式 ： 

1、 (( a + b ) * c + d ) - (( e + g ) * h )  // 变成 2 个表达式

2、 - r s  // 记 r = ( a + b ) * c + d   s = ( e + g ) * h 

3、 对于 r ，同样添加圆括号，变成 2 个子表单式  ( ( a + b ) * c ) + d   

    3.1  + ( a + b ) * c d
    
    3.2  + * ( a + b ) c d
    
    3.3  + * +  a b c d
    
4、 对于 s , ( e + g ) * h 

    4.1  * ( e + g ) h
    
    4.2  * + e g h
    
5、 最终结果 - + * + a b c d * + e g h


后缀表达式 :  a b + c * d + e g + h * -  ( 后缀表达式的推到过程与前缀表达式推导类似，只不过运算符已到括号后方)

2、逆波兰表达式计算 - 算法

  以 LeetCode 的第 150 题为例 。 在该例子中，tokens 即为后缀表达式（逆波兰表达式）

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]

输出：22

解释：该算式转化为常见的中缀算术表达式为：

  ((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

  利用逆波兰表达式计算时，使用一个栈来存储操作数，从左到右遍历逆波兰表达式，进行如下操作：

• 如果遇到操作数，则将操作数入栈；
• 如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈；
• 遍历完成后，栈内只有一个元素，该元素即为逆波兰表达式的值。

  如果利用波兰式来计算表单式的话，对操作的的遍历从后到前，同时出栈操作，第一个操作是左操作数，第二个操作数是右操作数。

  官方代码如下：

var evalRPN = function(tokens) {
    const stack = [];
    const n = tokens.length;
    for (let i = 0; i < n; i++) {
        const token = tokens[i];
        if (isNumber(token)) {
            stack.push(parseInt(token));
        } else {
            const num2 = stack.pop();
            const num1 = stack.pop();
            if (token === '+') {
                stack.push(num1 + num2);
            } else if (token === '-') {
                stack.push(num1 - num2);
            } else if (token === '*') {
                stack.push(num1 * num2);
            } else if (token === '/') {
                stack.push(num1 / num2 > 0 ? Math.floor(num1 / num2) : Math.ceil(num1 / num2));
            }
        }
    }
    return stack.pop();
};

const isNumber = (token) => {
    return !('+' === token || '-' === token || '*' === token || '/' === token );
}

  更简洁的版本：

var evalRPN = function(tokens) {
    const stack=[];
    const obj = {
      '+': (a, b) => +b + +a,
      '-': (a, b) => b - a,
      '*': (a, b) => b * a,
      '/': (a, b) => b / a | 0
    };
    tokens.forEach((v)=>{
        stack.push(isNaN(v)?obj[v](stack.pop(),stack.pop()):v);
    })
    return stack[0];
};

3、中缀表达式计算 - 算法

  以上边的 LeetCode 的实例继续讲解，如果用中缀表单式来计算的，该如何操作：

对应的前缀表达式： ( ( ( 10 * ( 6 / ( ( 9 + 3 ) * -11 ) ) ) + 17 ) + 5 )
为了与上例中格式保持一致，对中缀表达式转换成数组格式：

tokens = ["(", "(", "(", "10", "*", "(", "6", "/", "(", "(", "9", "+", "3", ")", "*", "-11", ")", ")", ")", "+", "17", ")", "+", "5", ")"]

  解决思路：

1. 初始化 2 个栈，一个用来存储运算符 S1， 一个用来存储操作数 S2；
2. 遇到左括号、操作符直接入栈S1，遇到数字直接入栈S2；
3. 遇到右括号，S1依次弹出操作符，S2弹出2个操作数，先弹出的作为右操作数，后弹窗的左右左操作数，并将执行结果重新入栈S2；
4. 直至S1全部入栈，此时S2中只有一个数据，即为计算的结果。

  算法如下：

var evalMiddle = function (tokens) {
  const s1 = []  //用于存储运算符
  const s2 = []  //用于存储操作数
  const n = tokens.length
  for (let i = 0; i < n; i++) {
    const token = tokens[i]
    if (isNumber(token)) {
      s2.push(parseInt(token))
    } else {
      if (token === ')') {
        // 弹出操作数
        const num2 = s2.pop()
        const num1 = s2.pop()
        // 弹出操作符，同时弹出左括号
        const _token = s1.pop()
        const leftParentheses = s1.pop()

        if (_token === '+') {
          s2.push(num1 + num2)
        } else if (_token === '-') {
          s2.push(_token - num2)
        } else if (_token === '*') {
          s2.push(num1 * num2)
        } else if (_token === '/') {
          s2.push(num1 / num2 > 0 ? Math.floor(num1 / num2) : Math.ceil(num1 / num2))
        }
      } else {
        s1.push(token)
      }
    }
  }
  return s2.pop()
}

var isNumber = (token) => {
  return !('+' === token || '-' === token || '*' === token || '/' === token || '(' === token || ')' === token)
}

var tokens = ["(", "(", "(", "10", "*", "(", "6", "/", "(", "(", "9", "+", "3", ")", "*", "-11", ")", ")", ")", "+", "17", ")", "+", "5", ")"]

console.log(evalMiddle(tokens))

 由以上代码可知，通知中缀表达式计算时，为了能更好的阐述表单式之间的的优先级时，需要通过2个堆栈来维护。
在上述算法中，针对中缀表达式的每个子表单式都添加括号，在实际过程中，我们针对上例的通常是如下写法，则在中缀表达式计算时可能还要考虑符号的优先级，算法相对会更加复杂一些。

 10 * (6 / ((9 + 3) * -11)) + 17) + 5
 
 而不是
 
 ( ( ( 10 * ( 6 / ( ( 9 + 3 ) * -11 ) ) ) + 17 ) + 5 )
 

4、总结

 中缀表达式更利于显示世界中的计算，他表达跟清晰；前、后缀表达式更利于计算机计算，因为他只需要一个数据栈就能够解决计算结果。

 关于中缀表达式和前缀表达式、后缀表单式之间的相互转换算法，本质上与中缀表单式计算的算法差不多，仍旧需要一个栈存储操作数、一个栈存储操作符，有兴趣的可以执行编码实现。

参考文献：

https://www.bilibili.com/video/BV1aJ411i7G7?from=search&seid=15042777190091941319

https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/solution/ni-bo-lan-biao-da-shi-qiu-zhi-by-leetcod-wue9/

https://juejin.cn/post/6844903750994231303#heading-4