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

Algorithmic data structure interview sharing symbol matching problem

Today, I saw a student in the post asking, if a string contains curly braces and parentheses, how should we solve the problem of parenthesis matching? Let's take a look at this problem today. Follow our previous routine, step by step:

1. Make sure we understand the problem and try an example to make sure we understand it correctly.

For example, such parentheses match, (), {}, ({}), ({()} () {}), while similar to {(, ()) are not matched.

two。 Think about what you can do to solve the problem, which one will you choose, and why?

Let's take this string as an example, ({()} () {}), the last match is the first (, the penultimate} match is the penultimate third. So we can scan from tail to head, the first) we record first, the first} we record, the third {we find it and} match, eliminate, the fourth is), we save, the fifth is (, we found a match with the fourth, eliminated, and so on, to the last (, we found that it was also the first match at the beginning. So we naturally think of the stack, if we don't match, we go into the stack, and if we match, we go out of the stack.

3. Explain your algorithm and implementation

We declare two stacks, first put all the characters into the stack, and then one by one out of the stack, we check whether the first character in the auxiliary stack matches, if it matches us out of the stack, otherwise enter the stack. When all the characters in the main stack are off the stack, we check to see if the auxiliary stack is empty. Null indicates an exact match, otherwise it does not match.

4. When writing code, remember, be sure to explain what you are doing now

Let's first define a stack, usually with the help of arrays, here we simply use the list to deal with, implement its Pop, Push, IsEmpty methods, look at the code:

Public class Mystack {private List list = new List (); public Mystack () {} public Mystack (T [] input) {if (input! = null) {for (int index = 0; index < input.Length; index++) {list.Add (input [index]) } public T Pop () {if (! this.IsEmpty ()) {T element = list [list.Count-1]; list.RemoveAt (list.Count-1); return element } throw new IndexOutOfRangeException ("The stack is empty already.");} public void Push (T element) {list.Add (element);} public bool IsEmpty () {return this.list.Count = = 0 }} next, let's look at the algorithm: public static bool IsMatch (string input) {if (! string.IsNullOrEmpty (input)) {Mystack stack = new Mystack (input.ToArray ()); Mystack secondStack = new Mystack () While (! stack.IsEmpty ()) {char current = stack.Pop (); if (secondStack.IsEmpty ()) {secondStack.Push (current) } else {char target = secondStack.Pop (); if (! IsClosed (current, target)) {secondStack.Push (target); secondStack.Push (current) } return secondStack.IsEmpty ();} return false;}

This uses an IsClosed method, which we use to match (and), {and}, look at the code:

Private static bool IsClosed (char first, char second) {if (first = ='(') return second = =')'; if (first ='{') return second = ='}'; return false;}

Finally, let's test this method together:

Static void Main (string [] args) {string input = "({() {}})"; var result = IsMatch (input); Console.WriteLine (result);}

Welcome to follow my official account and my feature series:

Video tutorials, data structures and algorithms, classic algorithms, face-to-face questions, sorting topics, linked list topics.

If you have any better solution, you are welcome to discuss it.

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.