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

简介: 算法 | 计算器系列 | 刷题打卡

目录

image.png


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,直到遍历完成,最后栈中唯一的元素就是运算结果。


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

image.png


动画引用自 —— github.com/Mrxxd/LeetC…


参考代码:


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()
    }
}


目录
相关文章
|
6月前
|
机器学习/深度学习 存储 算法
【算法沉淀】刷题笔记:并查集 带权并查集+实战讲解
【算法沉淀】刷题笔记:并查集 带权并查集+实战讲解
|
27天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
26 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
27天前
|
存储 算法 Java
数据结构与算法学习八:前缀(波兰)表达式、中缀表达式、后缀(逆波兰)表达式的学习,中缀转后缀的两个方法,逆波兰计算器的实现
前缀(波兰)表达式、中缀表达式和后缀(逆波兰)表达式的基本概念、计算机求值方法,以及如何将中缀表达式转换为后缀表达式,并提供了相应的Java代码实现和测试结果。
29 0
数据结构与算法学习八:前缀(波兰)表达式、中缀表达式、后缀(逆波兰)表达式的学习,中缀转后缀的两个方法,逆波兰计算器的实现
|
5月前
|
存储 算法 C语言
【数据结构与算法 刷题系列】合并两个有序链表
【数据结构与算法 刷题系列】合并两个有序链表
|
25天前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
12 0
|
3月前
|
算法 C++
第一周算法设计与分析 F : 模拟计算器
该文章 "第一周算法设计与分析 F : 模拟计算器" 的摘要或讨论。这篇文章介绍了如何设计一个程序来模拟一个基本的计算器,处理包含加、减、乘运算的表达式,并给出了相应的C++代码实现
|
3月前
【刷题记录】最大公因数,最小公倍数(辗转相除法、欧几里得算法)
【刷题记录】最大公因数,最小公倍数(辗转相除法、欧几里得算法)
|
3月前
|
算法 Python
【Leetcode刷题Python】改进的算法,高效求一个数的因子
一个高效的Python函数用于找出一个整数的所有因子,通过仅遍历到该数平方根的范围来优化性能。
37 0
|
5月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
5月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题