# rpn.js

**Repository Path**: phoenixor/rpn.js

## Basic Information

- **Project Name**: rpn.js
- **Description**: js库实现中缀表达式（即日常使用的四则运算表达式）转换成后缀表达式（逆波兰式），方便计算机计算
- **Primary Language**: JavaScript
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 7
- **Forks**: 2
- **Created**: 2018-03-31
- **Last Updated**: 2025-05-28

## Categories & Tags

**Categories**: javascript-toolkits

**Tags**: None

## README

# rpn.js
## 功能概述


> 数学运算表达式分3种：
>  * 1.前缀表达式（波兰式Prefix Expression）：运算符在操作数之前。
>  * 2.中缀表达式（Infix Expression）：一种通用的算术或逻辑公式表示方法，操作符以中缀形式处于操作数的中间，是人们常用的算术表示方法。
>  * 3.后缀表达式（Postfix Expressions，逆波兰式Reverse Polish notation）：与前缀表达式类似，只是运算符位于操作数之后。
>  * 前缀和后缀表达式都方便计算器进行运算。

rpn.js实现了中缀表达式（即日常使用的四则运算表达式，如1*（2+3））转换成后缀表达式即逆波兰式（123+*），方便计算机计算。
因为中缀表达式利于阅读，是大部分人接触到的数学计算表达式，但是对于计算机，想要判断运算符的优先级很困难，因此后缀表达式出现了，利用栈的原理很容易计算出表达式的结果。

 **_这个模型常用于数学表达式计算，为了展示效果，我做了一个计算器小程序（one计算器），二维码在末尾，微信扫码即可体验，个人开发者不易，也请在小程序内打赏我。_** 

## 代码片段
首先是几个功能函数，下面是判断是否是合法的四则运算符
```
function isOperator(value) {
    var operatorString = '+-*/()×÷';
    return operatorString.indexOf(value) > -1;
}
```
计算运算符优先级，并比较两个运算符的优先级先后
```
function getPriority(value) {
    if (value == '-' || value == '+') {
        return 1;
    } else if (value == '*' || value == '/' || value == '×' || value ==
        '÷') { return 2; } else { return 0; }
}

function priority(v1, v2) {
    return getPriority(v1) <= getPriority(v2);
}
```
有了这些功能函数后，下面是主要的函数：中缀表达式转换成后缀表达式。利用了栈的思想，理论如下：
> 【中缀转后缀】

>  设置输入栈s1存储中缀表达式各个元素，输出队列s存储生成的后缀表达式，栈s2存储运算符
>  * 一、中缀表达式看成一个字符串，从左到右开始扫描中缀表达式；
>  * 二、若是数字就直接给队列s；
>  * 三、若是运算符号：
>  * 	1.若为'('，压入栈s2。
>  * 	2.若为')'，则依次把栈s2中的运算符加入队列s中，直到出现'('，从栈中删除')'.
>  * 	3.若为除括号以外的其他运算符，当其优先级高于其他运算符时，直接入栈s2。否则从栈顶开始依次弹出比当前运算符优先级高和相等的运算符并压入队列s，直到一个比它优先级低的或者遇到一个左括号为止。
>  * 四、扫描结束时，栈s2中剩余的运算符依次出栈加入队列s。 

完整代码如下见 **infix2Rpn(exp)** 函数。

有了后缀表达式之后，就是利用队列的思想计算结果，理论如下：


> 【后缀表达式计算机求值】
>  * 1.设置一个空堆栈。
>  * 2.从左至右扫描表达式，遇到数字时，将数字压入堆栈。
>  * 3.遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 opt 栈顶元素），并将结果入栈。
>  * 4.重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。

具体代码实现见  **calRpnExp(rpnArr)**  函数。

但是平时计算时，都会直接传入中缀表达式计算，因此我将以上两个函数结合，传入中缀表达式直接计算结果，见  **calInfixExp(exp)**  函数。

![输入图片说明](https://gitee.com/uploads/images/2018/0331/132836_9b94b078_1819189.jpeg "one计算器小程序码.jpg")

## 参考文章

[1.Shunting-yard algorithm调试场算法](https://en.wikipedia.org/wiki/Shunting-yard_algorithm)

[2.Infix, Prefix and Postfix Expressions前缀、中缀和后缀表达式](http://www.interactivepython.org/runestone/static/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html)