逆波兰求值

[Geek-James]

什么是逆波兰?

来自百度百科的解释:

逆波兰表达式又叫做后缀表达式。在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，这种表示法也称为中缀表示。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法，按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。

大白话解释:

给你一组数字,从左向右遍历,如果遇到+-*/那么就逆序拿出运算符左边的2个数字进行运算,运算完之后继续放里面,继续遍历循环,直到结束,前提是要遵守最基本的四则运算。

例如
输入:["2","1","+",3,"/"]
逆波兰值为:
(2+1)/3 = 1

输入:["4","13","5","/","+"]
逆波兰值为:
4+(13/5) = 6

输入:["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
逆波兰值为:
((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

下面通过画图的方式来分析求逆波兰值的过程

通过上面的图,我们可以很清晰的看出其规律,其实就是压栈,出栈,压栈,出栈的过程,那么在JS中数组的push和pop就可以实现。

代码实现过程:

方案一:

var evalRPN = function (tokens) {
    // 定义一个数组栈
    let stack = [];
    for (let item of tokens) {
        switch (item) {
            case '+':
                let a1 = stack.pop();
                let b1 = stack.pop();
                stack.push(b1 + a1);
                break;
            case '-':
                let a2 = stack.pop();
                let b2 = stack.pop();
                stack.push(b2 - a2);
                break;
            case '*':
                let a3 = stack.pop();
                let b3 = stack.pop();
                stack.push(b3 * a3);
                break;
            case '/':
                let a4 = stack.pop();
                let b4 = stack.pop();
                stack.push(parseInt(b4 / a4));
                break;
            default:
                stack.push(parseInt(item));
        }
    }
    return parseInt(stack.pop());
}

精简代码封装一:

<script>
var evalRPN = function (tokens) {
    // 运算规则
    var caculate = function (right, left, operator) {
        switch (operator) {
            case '+':
                return Number(left) + Number(right);
            case '-':
                return Number(left) - Number(right);
            case '*':
                return Number(left) * Number(right);
            default:
                return parseInt(left / right);
        }
    }
    // 判断是否是 + - * /
    function isOperator(str) {
        return ["+", "-", "*", "/"].includes(str);
    }
    // 定义一个栈用来存放数据
    let stack = [];
    for (item of tokens) {
        // 遍历传过来的tokens并通过三目运算来计算值
        isOperator(item) ? stack.push(caculate(stack.pop(), stack.pop(), item)) : stack.push(parseInt(
            item));
    }
    return stack.pop();
}

var data = ["2", "1", "+", "3", "*"];
console.log(evalRPN(data)); 

正确答案:9
</script>

最终代码:

var evalRPN = function (tokens) {
    // 定义一个数组栈
    let stack = [];
    for (let item of tokens) {
        switch (item) {
            case '+':1 = ;
                stack.push(stack.pop() + stack.pop());
                break;
            case '-':
                stack.push(-stack.pop() + stack.pop());
                break;
            case '*':
                stack.push(stack.pop() * stack.pop());
                break;
            case '/':
                let right = stack.pop();
                stack.push(parseInt(stack.pop() / right));
                break;
            default:
                stack.push(parseInt(item));
        }
    }
    return parseInt(stack.pop());
}
var data = ["2", "1", "+", "3", "*"];
console.log(evalRPN(data));
// 输出答案为:9
</script>

小伙伴们可以复制以上代码到LeetCode 逆波兰表达式求值进行验证,如果您有更好的实现方案,也欢迎留言一起交流和讨论。

希望我的分享对你能有帮助,如何对你有所启发,以程序员最高礼遇点赞💓评论加转发的方式来鼓励我,你的肯定是我前进的最大动力!

如果你想获取前端整期学习视频和资料扫一扫下面的二维码,回复学习即可免费领取,也希望在前端进阶的路上,我们一起成长,一起进步!