美文网首页
算法 | 计算器系列 | 刷题打卡

算法 | 计算器系列 | 刷题打卡

作者: 彭旭锐 | 来源:发表于2021-03-11 18:46 被阅读0次

    点赞关注,不再迷路,你的支持对我意义重大!

    Hi,我是丑丑。本文「数据结构 & 算法」| 导读 —— 登高博见 已收录,这里有 Android 进阶成长路线笔记 & 博客,欢迎跟着彭丑丑一起成长。(联系方式在 GitHub)


    历史上的今天

    2016 年 3 月 9 日,AlphaGo 大战李世石 拉开序幕。9 日至15 日,在韩国首尔举行的人机围棋比赛中,谷歌旗下 DeepMind 开发的人工智能围棋软件 AlphaGo 最终以 4:1 战胜世界围棋冠军、职业九段选手李世石。继 “深蓝” 战胜卡斯帕罗夫之后,这场比赛被视为人类与人工智能的又一场较量。—— 《了不起的程序员》


    目录


    1. 题目描述

    实现一个基本的计算器来计算一个简单的字符串表达式的值。

    字符串表达式仅包含非负整数,+、 - 、*、/ 四种运算符,以及空格、左括号和右括号 。 整数除法仅保留整数部分。

    这几道题其实是计算器系列题目:

    • 第一道:加减法和括号
    • 第二道:四则运算
    • 第三道:四则运算 + 括号

    理解了第三道的解法,相信前两道都不会有大问题。


    2. 思路分析

    2.1 逆波兰表达式

    首先,你需要理解计算机是如何进行 “表达式求值” 的。我们平时使用的算术表达式,例如: 1 + 2 * 3,这种叫做 「中缀表达式」,也就是运算符都是放在两个操作数中间。中缀表达式符合人类的思考习惯,但是对计算机来说却并不友好,所以还有另外两种表达式形式:

    • 中缀表达式: 二元运算符置于两个操作数之间,例如:(1 + 2) * 3
    • 前缀表达式(波兰表达式): 二元运算符置于两个操作数之间,例如:* + 1 2 3
    • 后缀表达式(逆波兰表达式): 二元运算符置于两个操作数之间,例如:1 2 + 3 *

    相对于中缀表达式,前缀表达式和后缀表达式对计算机来说就友好很多了。它们在计算机看来却是比较简单易懂的结构,只需要依靠简单的入栈和出栈两种操作就可以完成计算。

    我们以后缀表达式求值为例:

    2.2 逆波兰表达式求值

    后缀表达式也叫逆波兰表达式(Reverse Polish notation,RPN),逆波兰表达式求值步骤如下:

    • 1、从左往右扫描逆波兰表达式:
    • 2、如果是数字,直接入栈;
    • 3、如果是运算符,那么弹出栈顶两个数字(四则运算需要两个运算数),执行运算;
    • 4、将运算结果重新入栈;
    • 5、重复步骤 3、4,直到遍历完成,最后栈中唯一的元素就是运算结果。

    提示: 波兰表达式和逆波兰表达式是没有括号的,中缀表达式中的括号在转换过程中已经被 “消化”。

    动画引用自 —— https://github.com/Mrxxd/LeetCodeAnimation

    参考代码:

    class Solution {
        fun evalRPN(tokens: Array<String>): Int {
            if (tokens.isEmpty()) {
                return 0
            }
    
            val stack = ArrayDeque<Int>()
    
            for (token in tokens) {
                when (token) {
                    "+" -> {
                        stack.push(stack.eval { o1, o2 -> o1 + o2 })
                    }
                    "-" -> {
                        stack.push(stack.eval { o1, o2 -> o1 - o2 })
                    }
                    "*" -> {
                        stack.push(stack.eval { o1, o2 -> o1 * o2 })
                    }
                    "/" -> {
                        stack.push(stack.eval { o1, o2 -> o1 / o2 })
                    }
                    else -> {
                        stack.push(token.toInt())
                    }
                }
            }
    
            return stack.pop()
        }
    
        private fun Deque<Int>.eval(operator: (Int, Int) -> Int): Int {
            val num1 = pop()
            val num2 = pop()
    
            return operator(num2, num1)
        }
    }
    

    2.3 中缀 -> 逆波兰

    逆波兰表达式求值很简单,但是我们的输入是普通的中缀表达式,我们要先转换为逆波兰表达式的形式,主要思想是 使用栈的特性来处理运算符和括号的优先级,步骤如下:

    • 1、从左往右扫描中缀表达式;
    • 2、如果是数字,直接输出;
    • 3、如果是左括号(,直接入栈;
    • 4、如果是右边括号),弹出栈顶元素,直到遇到左括号(;
    • 5、如果是运算符,则需要判断跟栈顶运算符的优先级:
      • 5.1 空栈或者优先级大于栈顶运算符,继续入栈;
      • 5.2 优先级小于等于栈顶运算符,弹出栈顶运算符,并输出;
      • 5.3 重复步骤 5.2,直到运算符大于栈顶运算符。
    • 6、重复步骤 2、3、4、5,直到遍历完成,最后将栈中剩余元素出栈。

    3. AC 代码

    class Solution {
        fun calculate(s: String): Int {
            // 1、中缀表达式转换为逆波兰表达式
            // 2、逆波兰表达式求值
            return s.toRPN().evalRPN()
        }
    
        // ------------------------------------------------------------------------
        // 1、中缀表达式转换为逆波兰表达式
        // ------------------------------------------------------------------------
    
        private fun String.toRPN(): List<String> {
    
            val list = ArrayList<String>()
            val stack = ArrayDeque<Char>()
    
            var num = 0
            var sign = 1
    
            outerFor@
            for ((index, token) in this.withIndex()) {
                when (token) {
                    ' ' -> continue@outerFor
    
                    in '0'..'9' -> {
                        num = num * 10 + (token.toInt() - 48)
                        if (index + 1 >= length || !(this[index + 1] in '0'..'9')) {
                            list.add("${sign * num}")
                            num = 0
                        }
                    }
    
                    '(' -> stack.push(token)
    
                    ')' -> {
                        while ('(' != stack.peek()) {
                            list.add("${stack.pop()}")
                        }
                        stack.pop() // 最后弹出 (
                    }
    
                    else -> {
                        // 先输出优先级相同或者更高的运算符
                        while (token.priority() <= stack.peek().priority()) {
                            list.add("${stack.pop()}")
                        }
                        stack.push(token)
                    }
                }
            }
            while (stack.isNotEmpty()) {
                list.add("${stack.pop()}")
            }
            return list
        }
    
        // 运算符优先级
        private fun Char?.priority(): Int {
            return when (this) {
                '+', '-' -> 1
                '*', '/' -> 2
                null -> -1
                else -> -1
            }
        }
    
        // ------------------------------------------------------------------------
        // 2、逆波兰表达式求值
        // ------------------------------------------------------------------------
    
        private fun Deque<Int>.eval(operator: (Int, Int) -> Int): Int {
            if(size > 1){
                val num1 = pop()
                val num2 = pop()
                return operator(num2, num1)
            }else{
                // 类似 -1 + 1 的情况
                return operator(0, pop())
            }
        }
    
        private fun List<String>.evalRPN(): Int {
    
            val stack = ArrayDeque<Int>()
    
            for (token in this) {
                when (token) {
                    "+" -> {
                        stack.push(stack.eval { o1, o2 -> o1 + o2 })
                    }
                    "-" -> {
                        stack.push(stack.eval { o1, o2 -> o1 - o2 })
                    }
                    "*" -> {
                        stack.push(stack.eval { o1, o2 -> o1 * o2 })
                    }
                    "/" -> {
                        stack.push(stack.eval { o1, o2 -> o1 / o2 })
                    }
                    else -> {
                        stack.push(token.toInt())
                    }
                }
            }
            return stack.pop()
        }
    }
    

    创作不易,你的「三连」是丑丑最大的动力,我们下次见!

    相关文章

      网友评论

          本文标题:算法 | 计算器系列 | 刷题打卡

          本文链接:https://www.haomeiwen.com/subject/rqtgqltx.html