JS实现逆波兰表达式

墨蓝 2024-04-20 09:00 61阅读 0赞

常见的算术表达式，称为中缀表达式，例如：

5 + ( 6 – 4 / 2 ) * 3

波兰表达式也称为前缀表达式，以上面的例子为例，其波兰表达式为：

+ 5 * - 6 / 4 2 3

# 波兰表达式 #

## 中缀表达式转换前缀表达式的操作过程为： ##

（1）首先设定一个操作符栈，**从右到左**顺序扫描整个中缀表达式：

*  如果是操作数，则直接归入前缀表达式；
 *  如果是括号：如果是右括号，则直接将其入栈；如果是左括号，则将栈中的操作符依次弹栈，归入前缀表达式，直至遇到右括号，将右括号弹栈，处理结束；
 *  如果是其他操作符，则检测栈顶操作符的优先级与当前操作符的优先级关系，如果栈顶操作符优先级大于当前操作符的优先级，则弹栈，并归入前缀表达式，直至栈顶操作符优先级小于等于当前操作符优先级，这时将当前操作符压栈。

（2）当扫描完毕整个中缀表达式后，检测操作符栈是否为空，如果不为空，则依次将栈中操作符弹栈，归入前缀表达式。

（3）最后，将前缀表达式翻转，得到中缀表达式对应的前缀表达式。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70]

## 波兰表达式计算 ##

1.  对前缀表达式从后向前扫描，设定一个操作数栈，如果是操作数，则将其直接入栈。
2.  如果是操作符，则从栈中弹出操作符对应的操作数进行运算，并将计算结果压栈。
3.  直至从右到左扫描完毕整个前缀表达式，这时操作数栈中应该只有一个元素，该元素的值则为前缀表达式的计算结果。

# 逆波兰表达式 #

逆波兰表达式也称为后缀表达式，以上面的例子为例，其逆波兰表达式为：

5 6 4 2 / - 3 * +

## 中缀表达式转换后缀表达式的操作过程为： ##

（1）**自右向左**顺序扫描整个中缀表达式；

*  如果当前元素为操作数，则将该元素直接存入到后缀表达式中；
 *  如果当前元素为“(”，则将其直接入栈；如果为“)”，则将栈中的操作符弹栈，并将弹栈的操作符存入到后缀表达式中，直至遇到“(”，将“(”从栈中弹出，并不将其存入到后缀表达式中；
 *  如果是其他操作符，如果其优先级高于栈顶操作符的优先级，则将其入栈，如果是小于或低于栈顶操作符优先级，则依次弹出栈顶操作符并存入后缀表达式中，直至遇到一个栈顶优先级小于当前元素优先级时或者栈顶元素为“(”为止，保持当前栈顶元素不变，并将当前元素入栈；

（2）当扫描完毕整个中缀表达式后，检测操作符栈是否为空，如果不为空，则依次将栈中操作符弹栈，归入后缀表达式。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 2]

## 逆波兰表达式计算 ##

1.  从左到右顺序扫描整个后缀表达式；
2.  如果是操作数，则将该操作数压入到栈中；
3.  如果是操作符，则从栈中弹出对应的操作数，注意操作数的顺序；根据操作符进行运算，并将结果重新压入到栈中；
4.  直至将整个栈扫描完毕；
5.  如果后缀表达式是合法的，则扫描完毕后，栈中只有一个元素，该元素的值即为后缀表达式的结果。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 3]

/**
     * @param {string[]} tokens
     * @return {number}
     */
    
    var calc = function (s1, s2, char) {
        
      switch (char) {
        
        case "+": return s1 + s2;
        case "-": return s1 - s2;
        case "*": return s1 * s2;
        case "/": return (s1 / s2) <= 0 ? Math.ceil(s1 / s2) : Math.floor(s1 / s2);
      }
    }
    var evalRPN = function (tokens) {
        
      let stack = [],
        len = tokens.length;
      let res = null;
      for (let i = 0; i < len; i++) {
        
        if (tokens[i] === "+"
          || tokens[i] === "-"
          || tokens[i] === "*"
          || tokens[i] === "/") {
        
          let s2 = stack.pop(),
            s1 = stack.pop();
          res = calc(s1 * 1, s2 * 1, tokens[i]);
          stack.push(res);
        } else {
        
          stack.push(tokens[i]);
        }
      }
      return stack.pop();
    };

参考：  
[波兰表达式与逆波兰表达式][Link 1]  
[js实现逆波兰式][js]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/3698b417d6d947f188ec9ef2d6b59b74.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/927347a4cf4d4bb5a25638753c05bf7b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/769413bf88bd4cf5b5dba4be2fca62bb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/ec5fc9e647a148f991865d805846018b.png
[Link 1]: https://blog.csdn.net/yuanlaijike/article/details/82346369
[js]: https://blog.csdn.net/binglinglong2/article/details/80759365