千家信息网

怎么用swift语言实现有效括号的判断

发表于:2024-11-22 作者:千家信息网编辑
千家信息网最后更新 2024年11月22日,这篇文章主要介绍了怎么用swift语言实现有效括号的判断的相关知识,内容详细易懂,操作简单快捷,具有一定借鉴价值,相信大家阅读完这篇怎么用swift语言实现有效括号的判断文章都会有所收获,下面我们一起
千家信息网最后更新 2024年11月22日怎么用swift语言实现有效括号的判断

这篇文章主要介绍了怎么用swift语言实现有效括号的判断的相关知识,内容详细易懂,操作简单快捷,具有一定借鉴价值,相信大家阅读完这篇怎么用swift语言实现有效括号的判断文章都会有所收获,下面我们一起来看看吧。

1.开篇问题:有效的括号[1]

假如现在要你来解这道题,你会想到怎样的解法了?

这就要用到我们今天要讲的"栈"这种数据结构。带着这个问题,我们来学习今天的内容。

2.如何理解"栈"?

关于栈,有一个非常贴切的游戏--汉诺塔。玩这个游戏的时候,我们都是从下往上一个一个放;取的时候,我们也是从上往下一个一个地依次取,不能从中间任意抽出。后进者先出,先进者后出,这就是典型的"栈"结构

从栈的操作特性上来看,栈是一种"操作受限"的线性表,只允许在一端插入和删除数据。
栈的定义[2]

栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

3.如何实现栈

从刚才栈的定义里,我们可以看出,栈主要包含两个操作,入栈和出栈,也就是在栈顶插入一个数据和从栈顶删除一个数据。理解了栈的定义之后,我们来看一看如何用代码实现一个栈。
【本文使用 swift 语言来编写代码,读者朋友们不要因为编程语言不同而有畏难情绪,重要的是思维和逻辑,语言只是表达方式。你可以用你自己熟悉的语言来表达你的逻辑,可以先试着写一写】
Talking is cheap,show you the code.
  
class Stack {
//初始化数组
var datas = [Int]()
//出栈操作
func pop() -> Int? {
return datas.popLast()
}
//入栈操作
func push(obj: Int) {
datas.append(obj)
}
//栈顶对象
func top() -> Int? {
return datas.last
}
}

4.栈在实际开发过程中的应用

  • 栈在函数调用中的应用

      
func calculate() {
let a = 3
let b = 5
var result = 0
result = add(x: a, y: b)
print(result)
}

func add(x: Int, y: Int) -> Int {
var sum= 0
sum = x + y
return sum
}
从代码中我们可以看出,calculate() 函数调用了 add() 函数,传入临时变量a和b,获取计算结果,最后打印 result 的值。
为了让你清晰地看到这个过程对应的函数栈里出栈、入栈的操作,我画了一张图。图中显示的是,在执行到 add() 函数时,函数调用栈的情况。
  • 递归

在算法中,经常会使用的一个思想就是递归思想。很著名的就是斐波那契数列 [3]
F(0) =0,
F(1) =1,
F(n) = F(n-1)+F(n-2)(n≥2,n∈N*)
计算 F(n) 时需要先计算 F(n-1)F(n-2)
计算 F(n-1) 时需要先计算 F(n-2)F(n-3)
计算 F(n-2) 时需要先计算 F(n-2)F(n-3)
···
最后的效果是,会有很多中间值压入栈中,这也是为什么,当 n 很大的时候,会非常消耗内存。所以在实际的开发中,掌握这些底层的开发基础,会有助你选择合适的技术方案。

5.概念区分:数据结构堆栈 VS 内存中的堆栈

在学习计算机基础的时候,我们知道内存中有栈区和堆区。那它与数据结构中的堆栈有什么区别了,它们是同一个概念吗?
内存中的堆栈数据结构堆栈不是一个概念,可以说内存中的堆栈是真实存在的物理区,数据结构中的堆栈是抽象的数据存储结构。
内存空间在逻辑上分为三部分:代码区、静态数据区和动态数据区,动态数据区又分为栈区和堆区。
代码区:存储方法体的二进制代码。高级调度(作业调度)、中级调度(内存调度)、低级调度(进程调度)控制代码区执行代码的切换。
静态数据区:存储全局变量、静态变量、常量,常量包括final修饰的常量和String常量。系统自动分配和回收。
栈区:存储运行方法的形参、局部变量、返回值。由系统自动分配和回收。
堆区:new一个对象的引用或地址存储在栈区,指向该对象存储在堆区中的真实数据。

6.解答开篇

好了,我想现在你已经完全理解了栈的概念。我们再回来看看开篇的思考题,如何实现有效括号的判断?其实使用栈的思想就可以非常完美的解决这个问题。
我们开始分析:
  • 1.如果开始就是右括号 )、]、} ,很明显不合法,直接返回false
  • 2.如果是左括号 (、[、{ ,就压栈。如果是右括号 )、]、} ,在stack有值的情况下与栈顶元素匹配,匹配通过则栈顶元素出栈,否则直接返回false。
下面是 swift 解题的实现代码
      
class Solution {

func isValid(_ s: String) -> Bool {

if s.count == 0 { return false }
var stack = [String]()
let dict: [String:String] = ["(":")","[":"]","{":"}"]

for c in s {
if dict.keys.contains(c.description) {
stack.append(c.description) //如果是左括号就入栈
}else {
if stack.count > 0 && c.description == dict[stack.last!] { //如果是右括号,并且匹配就出栈
stack.removeLast()
}else {
return false
}
}
}
return stack.count == 0
}
}
在LeetCode上也有很多种语言的解法,这里分享一个python [4] 的解法

关于"怎么用swift语言实现有效括号的判断"这篇文章的内容就介绍到这里,感谢各位的阅读!相信大家对"怎么用swift语言实现有效括号的判断"知识都有一定的了解,大家如果还想学习更多知识,欢迎关注行业资讯频道。

0