括号序列：使用C++检查括号有效性

GeekLiHua

发布于 2025-01-21 07:30:34

23500

代码可运行

文章被收录于专栏：JavaJava

运行总次数：0

代码可运行

解析括号序列：使用C++检查括号有效性

什么是括号序列？

括号序列是指由左右括号组成的字符串，如"([])", “{[()]}”。括号序列通常用于编程语言中的控制结构、函数调用和表达式等地方。在这些场景中，括号必须以正确的顺序和嵌套方式出现，否则程序将出现语法错误或逻辑错误。

算法思路

为了检查括号序列的有效性，我们将使用栈这一数据结构。栈是一种后进先出（LIFO）的数据结构，非常适合处理括号的嵌套关系。以下是我们的算法思路：

初始化一个栈，用于存储遇到的左括号。
遍历括号序列中的每个字符。
对于每个字符：
- 如果是左括号（‘(’，‘{’，‘[’），将其压入栈中。
- 如果是右括号（‘)’，‘}’，‘]’），检查栈是否为空。
  - 如果栈为空，说明右括号多于左括号，括号序列无效。
  - 如果栈不为空，弹出栈顶元素，检查是否与当前右括号匹配。
遍历完成后，检查栈是否为空。如果不为空，说明左括号多于右括号，括号序列无效。

C++实现

下面是使用C++实现的算法代码：

#include <iostream>
#include <stack>
#include <string>

using namespace std;

bool isValidParentheses(const string& s) {
    stack<char> st;

    for (char bracket : s) {
        if (bracket == '(' || bracket == '[' || bracket == '{') {
            st.push(bracket);
        } else {
            if (st.empty()) {
                return false;  // 右括号多于左括号，序列无效
            }

            char top = st.top();
            st.pop();

            if ((bracket == ')' && top != '(') ||
                (bracket == ']' && top != '[') ||
                (bracket == '}' && top != '{')) {
                return false;  // 括号不匹配，序列无效
            }
        }
    }

    return st.empty();  // 如果栈不为空，说明左括号多于右括号，序列无效
}

int main() {
    // 测试例子
    string example = "([])";
    if (isValidParentheses(example)) {
        cout << "括号序列有效" << endl;
    } else {
        cout << "括号序列无效" << endl;
    }

    return 0;
}