C++栈实现括号匹配 |21xrx.com

C++栈实现括号匹配

2023-07-12 13:25:31 深夜i -- --

C++ 栈括号匹配

括号匹配是程序员在日常代码编写中经常遇到的问题，而实现括号匹配的关键是利用栈这一数据结构。在C++中，实现栈非常简单，只需要利用STL库中的stack容器即可轻松实现栈的操作。本文将介绍如何使用C++栈来实现括号匹配。

首先，我们需要了解什么是栈。栈是一种后进先出（Last In First Out，LIFO）的数据结构，即最后一个进入栈中的元素最先出栈。栈可以使用数组或链表实现，但在C++中，我们可以更方便地使用STL库中的stack容器。

接下来，我们需要思考如何使用栈实现括号匹配。括号匹配是指在一个字符串中，括号的左右是能够对应上的。例如，有一个字符串“{[()]}”，那么它是一个合法的括号匹配，因为每个左括号都有与之对应的右括号。而如果有一个字符串“{[()]”，那么它就不是一个合法的括号匹配，因为最后一个右括号没有与之匹配的左括号。

具体实现时，我们可以使用栈来存储左括号，并在遍历字符串时，每当遇到一个右括号时，都从栈中推出一个左括号，看看两者是否匹配。如果匹配，则继续遍历，否则括号匹配失败。

下面是使用C++栈实现括号匹配的代码：


#include <iostream>
#include <stack>
#include <string>
bool checkValid(std::string s) {
  std::stack<char> stk;
  for (char ch : s) {
    if (ch == '(' || ch == '[' || ch == '{') {
      // 遇到左括号，将其入栈
      stk.push(ch);
    } else {
      if (stk.empty()) 说明没有左括号与该右括号匹配
        return false;
       else if ((ch == ')' && stk.top() == '(')
          || (ch == ']' && stk.top() == '[')
          || (ch == '}' && stk.top() == '{')) {
        // 栈顶元素与该右括号匹配，弹出栈顶元素
        stk.pop();
      } else
        // 栈顶元素与该右括号不匹配
        return false;
      
    }
  }
  return stk.empty();
}

在上述代码中，我们首先声明一个栈`stk`，并遍历字符串`s`中的每个字符。如果当前字符是左括号，则将其压入栈中；如果当前字符是右括号，则从栈顶弹出一个元素。如果栈为空，则说明没有左括号与该右括号匹配；如果栈顶元素与该右括号不匹配，则说明括号匹配失败；否则，我们继续遍历字符串。最终，如果栈为空，则说明括号匹配成功，否则括号匹配失败。

总结来说，使用C++栈实现括号匹配非常简单，只需要利用STL库中的stack容器，可以轻松实现栈的操作，判断括号是否匹配的关键是遍历字符串，当遇到左括号时，将其入栈；当遇到右括号时，从栈中弹出一个元素，看看两者是否匹配。对于每一个合法的左括号，一定有与之匹配的右括号，因此遍历结束后，只需要判断栈是否为空即可判断括号匹配是否成功。

上一篇: idea打包java可执行jar包

下一篇: C++如何输入多个数

评论区

()

相似文章