Shulou(Shulou.com)06/01 Report--

This article mainly introduces the relevant knowledge of how to use swift language to realize the judgment of valid parentheses, the content is detailed and easy to understand, the operation is simple and fast, and has a certain reference value. I believe you will gain something after reading this article on how to use swift language to achieve valid parentheses. Let's take a look.

1. Opening question: valid parentheses [1]

If you were asked to solve the problem now, what kind of solution would you think of? This will use the "stack" data structure that we are going to talk about today. With this question in mind, let's learn today's content. two。 How to understand "stack"?

About the stack, there is a very appropriate game-Hanoi Tower. When we play this game, we put it one by one from the bottom to the top; when we take it, we also take it one by one from the top to the bottom, and we can't pull it out at will from the middle. The last one comes out first, and the first one comes out later. This is the typical "stack" structure.

From the operational characteristics of the stack, the stack is a "operation-limited" linear table, which only allows data to be inserted and deleted at one end.

Definition of stack [2]:

Stack, also known as stack, is a linear table with limited operations. Qualifies linear tables that insert and delete only at the end of the table. This end is called the top of the stack, on the contrary, the other end is called the bottom of the stack. Inserting a new element into a stack is also called entering, entering, or pressing the stack. It puts the new element on top of the stack and makes it a new top element. Removing an element from a stack is also called making a stack or unstack. It removes the top element of the stack and makes its adjacent elements a new top element of the stack. 3. How to implement the stack from the definition of the stack just now, we can see that the stack mainly consists of two operations, entering and unstacking, that is, inserting a data at the top of the stack and deleting a data from the top of the stack. Now that we understand the definition of a stack, let's take a look at how to implement a stack in code. This article uses the swift language to write code, readers should not be afraid of difficulties because of different programming languages, the important thing is thinking and logic, language is just a way of expression. You can use your own familiar language to express your logic, you can first try to write] Talking is cheap,show you the code. Class Stack {

/ / initialize the array

Var datas = [Int] ()

/ / unstack operation

Func pop ()-> Int? {

Return datas.popLast ()

}

/ / Stack operation

Func push (obj: Int) {

Datas.append (obj)

}

/ / object on top of stack

Func top ()-> Int? {

Return datas.last

}

}

4. Application of Stack in actual Development process

Application of Stack in function call

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

}

We can see from the code that the calculate () function calls the add () function, passes in the temporary variables an and b, gets the result of the calculation, and finally prints the value of result. In order to give you a clear view of the operation of the function stack corresponding to this process, I have drawn a diagram. The figure shows what happens when the function call stack is executed to the add () function.

Recursion

One of the ideas that are often used in algorithms is recursive thinking. The famous Fibonacci sequence [3] F (0) = 0

F (1) = 1

F (n) = F (nmur1) + F (nmel2) (n ≥ 2 ∈ N *)

When calculating F (n), we need to calculate F (nmur1) and F (nMur2) first.

When calculating F (nmur1), we need to calculate F (nmur2) and F (nmur3) first.

When calculating F (nmur2), we need to calculate F (nmur2) and F (nmur3) first.

The end result is that a lot of intermediate values are pushed into the stack, which is why, when n is very large, it consumes a lot of memory. Therefore, in the actual development, mastering the underlying development foundation will help you to choose the appropriate technical solution. 5. Concept distinction: data structure stack VS stack in memory when we learn the basics of computers, we know that there are stack areas and stack areas in memory. So what's the difference between it and the stack in the data structure? are they the same concept? The stack in memory and the stack of data structure are not a concept, it can be said that the stack in memory is a real physical area, and the stack in data structure is an abstract data storage structure. Logically, the memory space is divided into three parts: code area, static data area and dynamic data area, and the dynamic data area is divided into stack area and stack area. Code area: stores the binary code of the method body. High-level scheduling (job scheduling), intermediate scheduling (memory scheduling), and low-level scheduling (process scheduling) control the switching of code execution in the code area. Static data area: stores global variables, static variables, constants, including final-modified constants and String constants. The system automatically allocates and recycles. Stack area: stores the formal parameters, local variables, and return values of the running method. Automatically allocated and recycled by the system. Heap area: new the reference or address of an object is stored in the stack area, pointing to the real data that the object stores in the heap area. 6. The answer begins. I think you have fully understood the concept of stack by now. Let's come back to the opening question, how to achieve the judgment of valid parentheses? In fact, the idea of using stack can solve this problem perfectly. Let's start the analysis: 1. If it starts with closing parentheses),],}, which is obviously illegal, return false2 directly. If it is a left parenthesis (, [, {, press the stack. If it is a closing parenthesis),],}, if the stack has a value, it matches the element at the top of the stack. If the match passes, the element at the top of the stack goes out of the stack, otherwise it directly returns false. The following is the swift problem solving implementation code 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) / / enter the stack if it is a left parenthesis

} else {

If stack.count > 0 & & c.description = = dict [stack.last!] {/ / if it is a closing parenthesis and the match is out of the stack

Stack.removeLast ()

} else {

Return false

}

}

}

Return stack.count = = 0

}

}

There are also many language solutions on LeetCode. Here we share a solution of python [4] on "how to use swift language to judge valid parentheses." this is the end of this article. Thank you for reading! I believe that everyone has a certain understanding of the knowledge of "how to use swift language to judge valid parentheses". If you want to learn more, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.