有效的括号，成对字符合法性检测

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。

一、题目描述

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’?的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()"
输出：true

示例?2：

输入：s = "()[]{}"
输出：true

示例?3：

输入：s = "(]"
输出：false

二、思路分析

阅读完题目后，我们可以知道这道题目我们可以使用栈这个结构来进行解题，那么什么是栈呢？

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

JavaScript内部的Array数组即可以当成栈来使用，使用push方法入栈，pop方法出栈。

三、AC代码

var isValid = function(s) {
    let stack = [];
    const emuMap = {
      "}": "{",
      "]": "[",
      ")": "(",
    };
    for(let i = 0; i < s.length; i++){
        if(Object.keys(emuMap).includes(s[i])){
            if(stack.pop() != emuMap[s[i]]) return false;
        }else{
            stack.push(s[i]);
        }
    }
    return stack.length == 0;
};

四、实际应用

在我们日常编程中，括号都是成对出现的，比如“()”“[]”“{}”“<>”这些成对出现的符号。

那么具体处理的方法就是:凡是遇到括号的前半部分，即把这个元素入栈，凡是遇到括号的后半部分就比对栈顶元素是否该元素相匹配，如果匹配，则前半部分出栈，否则就是匹配出错。

如下图，我们可以使用栈这个特性来实现一个实时校验输入字符串合法性的功能。

字符串合法性实时监测

html部分

使用vue进行数据绑定来实时监听数据变化，数据变化时检验数据的合法性，不合法则标红显示。

<template>
  <div>
    <div>括号匹配校验</div>
    <div class="search-box">
      <div class="dir">
        <div class="title">检验字符串</div>
        <textarea placeholder="检验字符串" v-model="str"></textarea>
      </div>
      <div class="result-box">
        <div class="title">检验结果</div>
        <div class="result">
          <span
            v-for="(item, index) in result"
            :key="'str' + index"
            :style="item.style"
            >{{ item.text }}</span
          >
        </div>
      </div>
    </div>
  </div>
</template>

script部分

emuMap声明需要校验的字符对，在watch中监听字符串的变化，变化时触发校验方法。

<script>
const emuMap = {
  "}": "{",
  "]": "[",
  ")": "(",
  "）": "（",
};
export default {
  name: "stack",
  data() {
    return {
      str: "",
      result: "",
    };
  },
  watch: {
    str() {
      this.doCheck();
    },
  },
  created() {},
  methods: {
    getStyle(index) {
      let res = "";
      if (this.result === index + "") res += "color:red;";
      return res;
    },
    doCheck() {
      let res = [];
      for (let i = 0; i < this.str.length; i++) {
        res.push({
          text: this.str[i],
          style: "",
        });
      }
      let ind = this.getIndex();
      if (ind !== true) {
        while (ind < this.str.length) {
          res[parseInt(ind)].style = "color:red;";
          ind++;
        }
      }
      this.result = res;
    },
    getIndex() {
      let stack = [],
        stackI = [],
        s = this.str;
      for (let i = 0; i < s.length; i++) {
        if (Object.keys(emuMap).includes(s[i])) {
          stackI.pop();
          if (stack.pop() !== emuMap[s[i]]) return i;
        } else if (Object.values(emuMap).includes(s[i])) {
          stackI.push(i);
          stack.push(s[i]);
        }
      }
      return stackI.length == 0 || stackI[0];
    },
  },
};
</script>

css部分

<style lang="scss" scoped>
.search-box {
  border: 1px solid black;
  min-height: 300px;
  width: 600px;
  display: flex;
  flex-wrap: wrap;
  margin: auto;
  margin-top: 20px;
  .dir {
    flex: 1;
    margin-right: 1rem;
    textarea {
      width: 100%;
      height: 80%;
    }
  }
  .result-box {
    flex: 1;
    .result {
      border: 1px solid black;
      height: 80%;
    }
  }
}
</style>

公众号

关注公众号『前端也能这么有趣』，获取更多有趣内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。