逆波兰表达式简介

逆波兰表达式又叫做后缀表达式。逆波兰表示法是波兰逻辑学家J・卢卡西维兹(J・ Lukasiewicz)于1929年首先提出的一种表达式的表示方法 。后来,人们就把用这种表示法写出的表达式称作“逆波兰表达式”。逆波兰表达式把运算量写在前面,把算符写在后面。

逻辑提问式类似于算术表达式，对于检索而言，这种表达式并不是最优和最简洁的形式，需要进行必要的转换。1929年波兰的逻辑学家卢卡西维兹(Jan Lucasiewicz)提出了将运算符放在运算项后面的逻辑表达式，又称“逆波兰表达式”。采用这种表达式组织逻辑提问式非常方便检索运算，是日本的福岛先生最早将逆波兰表达式应用于情报检索的，故又称为“福岛方法”

逆波兰表达式又叫做后缀表达式，是一种没有括号，并严格遵循“从左到右”运算的后缀式表达方法，如下表所示：

用途

逆波兰表达式是一种十分有用的表达式，它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式。例如(a+b) (c+d)转换为ab+cd+ 。

它的优势在于只用两种简单操作，入栈和出栈就可以搞定任何普通表达式的运算。其运算方式如下：

如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。

逆波兰表达式构造算法

1、首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。

2、读入一个用中缀表示的简单算术表达式，为方便起见，设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。

3、从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。

4、如果不是数字，该字符则是运算符，此时需比较优先关系。

具体做法是：将该字符与运算符栈顶的运算符的优先关系相比较。如果该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。若不是的话，则将栈顶的运算符从栈中弹出，直到栈项运算符的优先级低于当前运算符，将该字符入栈。

5、重复步骤1～2，直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。

如：((10 * (6 / ((9 + 3) * -11))) + 17) + 5的逆波兰表达式为[“10”,“6”,“9”,“3”,"+","-11","","/","",“17”,"+",“5”,"+"]；

根据逆波兰表示法，求表达式的值

问题描述

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

注意 两个整数之间的除法只保留整数部分。

可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

题目取自 LeetCode 150. 逆波兰表达式求值

示例

输入：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

解题思路

上面我们已经了解了一个逆波兰表达式是如何构造出来的，所以我们可以反向构造出其原来的算式表达式，逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时，使用一个栈存储操作数，从左到右遍历逆波兰表达式，进行如下操作：

• 如果遇到操作数，则将操作数入栈；

• 如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。

整个逆波兰表达式遍历完毕之后，栈内只有一个元素，该元素即为逆波兰表达式的值，这时候可能有人就回问了，如果最后栈内不止一个元素呢？那你就要好好检查你的代码了，代码没问题的话就要检查逆波兰表达式是否正确了。

代码

/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function(tokens) {
    let tmp = [],
        a = 0,
        b = 0;
    for(let i = 0; i < tokens.length; i++){
        if(tokens[i] == '+'){
            a = parseInt(tmp.pop());
            b = parseInt(tmp.pop());
            tmp.push(a + b);
        }else if(tokens[i] == '-'){
            a = parseInt(tmp.pop());
            b = parseInt(tmp.pop());
            tmp.push(b - a);
        }else if(tokens[i] == '*'){
            a = parseInt(tmp.pop());
            b = parseInt(tmp.pop());
            tmp.push(a * b);
        }else if(tokens[i] == '/'){
            a = parseInt(tmp.pop());
            b = parseInt(tmp.pop());
            tmp.push(parseInt(b / a));
        }else{
            tmp.push(tokens[i]);
        }
    }
    return tmp[0];
};