如何判定括号合法性

对括号的合法性判断是一个很常见且实用的问题,比如说我们写的代码,编辑器和编译器都会检查括号是否正确闭合。而且我们的代码可能会包含三种括号 [](){},判断起来有一点难度。

本文就来聊一道关于括号合法性判断的算法题,相信能加深你对这种数据结构的理解。

题目很简单,输入一个字符串,其中包含 [](){} 六种括号,请你判断这个字符串组成的括号是否合法。

  1. Input: "()[]{}"
  2. Output: true
  3. Input: "([)]"
  4. Output: false
  5. Input: "{[]}"
  6. Output: true

解决这个问题之前,我们先降低难度,思考一下,如果只有一种括号 (),应该如何判断字符串组成的括号是否合法呢?

一、处理一种括号

字符串中只有圆括号,如果想让括号字符串合法,那么必须做到:

每个右括号 ) 的左边必须有一个左括号 ( 和它匹配

比如说字符串 ()))(( 中,中间的两个右括号左边就没有左括号匹配,所以这个括号组合是不合法的。

那么根据这个思路,我们可以写出算法:

  1. bool isValid(string str) {
  2. // 待匹配的左括号数量
  3. int left = 0;
  4. for (char c : str) {
  5. if (c == '(')
  6. left++;
  7. else // 遇到右括号
  8. left--;
  9. if (left < 0)
  10. return false;
  11. }
  12. return left == 0;
  13. }

如果只有圆括号,这样就能正确判断合法性。对于三种括号的情况,我一开始想模仿这个思路,定义三个变量 left1left2left3 分别处理每种括号,虽然要多写不少 if else 分支,但是似乎可以解决问题。

但实际上直接照搬这种思路是不行的,比如说只有一个括号的情况下 (()) 是合法的,但是多种括号的情况下, [(]) 显然是不合法的。

仅仅记录每种左括号出现的次数已经不能做出正确判断了,我们要加大存储的信息量,可以利用栈来模仿类似的思路。

二、处理多种括号

栈是一种先进后出的数据结构,处理括号问题的时候尤其有用。

我们这道题就用一个名为 left 的栈代替之前思路中的 left 变量,遇到左括号就入栈,遇到右括号就去栈中寻找最近的左括号,看是否匹配

  1. bool isValid(string str) {
  2. stack<char> left;
  3. for (char c : str) {
  4. if (c == '(' || c == '{' || c == '[')
  5. left.push(c);
  6. else // 字符 c 是右括号
  7. if (!left.empty() && leftOf(c) == left.top())
  8. left.pop();
  9. else
  10. // 和最近的左括号不匹配
  11. return false;
  12. }
  13. // 是否所有的左括号都被匹配了
  14. return left.empty();
  15. }
  16. char leftOf(char c) {
  17. if (c == '}') return '{';
  18. if (c == ')') return '(';
  19. return '[';
  20. }

坚持原创高质量文章,致力于把算法问题讲清楚,欢迎关注我的公众号 labuladong 获取最新文章:

labuladong

上一篇:如何k个一组反转链表

下一篇:如何寻找消失的元素

目录