In the past, I often encountered questions about matching brackets in the interview process, such as the following questions:

  1. Write a function that takes an arithmetic expression as an argument and returns the position where the parentheses are missing.
2.3 + 23/12 + (3.14 * 0.24Copy the code
  1. Implement a normalize function that converts a particular string into a particular structured data.
[a[b[c]]]
/ / into
{ value: 'a'.children: { value: 'b'.children: { value: 'c'}}}Copy the code

For the record, question 2 is ali’s interview question.

Then one day I read in the book “JavaScript Descriptions of Data Structures and Algorithms” that stacks can be used to determine whether the parentheses in an expression match.

The stack

What is a stack?

A stack is a special kind of list in which elements can only be accessed through one end of the list, called the top of the stack.

A stack of plates in a coffee shop is an example of a stack that is common in the real world. You can only take dishes from the top, and when they’re clean, you can only stack them on top of the same pile. The stack is referred to as a last-in-first-out (LIFO) data structure.

The two main operations on the stack are pushing an element onto the stack and pushing an element off the stack. Push () is used for pushing and pop() is used for pushing. The figure illustrates the process of loading and unloading the stack.

In fact, these feelings are quite abstract, slowly understand.

In actual combat

A palindrome is a phenomenon in which a word, phrase or number is written the same way from front to back as it is from back to front.

The word "dad", "racecar" is a palindrome as is the number 1001Copy the code
function isPalindrome(word) {
  let s = [];
  for (let i = 0; i < word.length; i++) {
    s.push(word[i]); / / into the stack
  }
  let rword = "";
  while (s.length > 0) {
    rword += s.pop(); / / out of the stack
  }
  if (word == rword) {
    return true;
  }
  else {
    return false; }}Copy the code

The characteristic of the stack is that characters are added to the array in positive order and taken out in reverse order. Because of this order, palindromes can be judged.

If the number 123, then the push is 1, 2, 3, and the push is 3, 2, 1, and the push and the push get different results, then they are not palindromes.

If the character dad, then the push is D, A, D, and the push is D, a, D, and the push and the push give the same result, then they are palindromes.

Now you understand the characteristics of the stack…

(1) The missing parentheses can be written as follows:

function demo (str) {
  let sign = '() {} []'
  let s = []
  for (let i = 0; i < str.length; i++) {
    if (sign.includes(str[i])) {
      let val = str[i];
      switch (val) {
        case '(':
        case '[':
        case '{': s.push(val); break;
        case ') ':
          let map1 = s.pop();
          if(map1 ! = ='(') {
            return ` position${i}The) does not match
          }
          break;
        case '] ':
          let map2 = s.pop();
          if(map2 ! = ='[') {
            return ` position${i}] does not match '
          }
          break;
        case '} ':
          let map3 = s.pop();
          if(map3 ! = ='{') {
            return ` position${i}} does not match '
          }
          break; }}}if (s.length) {
    return ` symbol${s.join()}No closure '
  } else {
    return 'Sign correct'}}Copy the code

Our parentheses include (){}[], and then the parentheses on the left side of the stack and the parentheses on the right side of the stack. When there is a corresponding relationship between the parentheses on the two sides, it means that the parentheses match correctly.

[a[b[c]] [b]]

function normalize (str) {
  let s = [];
  let list = [];
  let obj = {}
  for (let i = 0; i < str.length; i++) {
    let value = str[i]
    switch (value) {
      case '[':
        s.push(i)
        break;
      case '] ':
        let leftIndex = s.pop();
        list.unshift([leftIndex, i])
      default:
        break; }}let [start, end] = list[0]
  let parent = obj
  for (let i = 1; i < list.length; i++) {
    let [a, b] = list[i];
    let result = str.slice(start + 1, a) + str.slice(b + 1, end);
    start = a;
    end = b;
    parent.value = result;
    parent.children = {};
    parent = parent.children;
  }
  let [x, y] = list[list.length - 1]
  parent.value = str.slice(x + 1, y)
  return obj
}
Copy the code

[[0, 8], [2, 7], [4, 6]], then we can know the contents of the left and right sides by the range of the range (0 to 2 and 7 to 8 are the contents of the first parentheses, and so on. Note that the final content is 4 to 6, which is the closed relation), and then you can get it by string interception. Finally, the object is converted to a tree structure by its previous reference relationship.