C++」给定一个只包括「(」「)」「{」「}」「[」「]」的字符串 |21xrx.com

C++」给定一个只包括「(」「)」「{」「}」「[」「]」的字符串

2023-06-27 04:06:01 深夜i -- --

C++ 括号匹配字符串处理栈数据结构递归函数

，判断字符串是否有效。输入的字符串在长度上最长可能达到10000，其中只包含「(」「)」「{」「}」「[」「]」六种字符。

在日常的编程中，我们经常会遇到需要判断字符串有效性的问题，尤其是在处理一些数据结构的实现时，比如栈、队列等。而对于一个只包含「(」「)」「{」「}」「[」「]」的字符串，如何判断其是否有效呢？

我们可以借助栈的思想来解决这个问题。具体来说，我们从字符串的左侧开始遍历，将遇到的左括号按顺序入栈。当遇到右括号时，我们检查栈顶元素是否与该右括号匹配，若匹配，则弹出栈顶元素；否则，返回false。

以下是具体实现过程：


bool isValid(string s) {
  stack<char> st;
  for (char c : s) {
    if (c == '(' || c == '{' || c == '[') {
      st.push(c);
    } else if (c == ')' || c == '}' || c == ']') {
      if (st.empty())
        return false;
      
      char t = st.top();
      st.pop();
      if ((c == ')' && t != '(') ||
        (c == '}' && t != '{') ||
        (c == ']' && t != '['))
        return false;
      
    }
  }
  return st.empty();
}

其中，stack是STL中的栈容器，st.top()返回栈顶元素，st.pop()弹出栈顶元素。

时间复杂度为O(n)，空间复杂度为O(n)。

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

下一篇: C++是一种编程语言吗？

评论区

()

相似文章