C++实现括号匹配算法 - 检查字符串中的括号是否有效

C++实现括号匹配算法 - 检查字符串中的括号是否有效

在编程中，经常需要检查字符串中的括号是否匹配。例如，在解析表达式或验证代码语法时，这是一个常见的需求。 本文将介绍如何使用C++实现一个简单的括号匹配算法。

问题描述

给定一个只包含字符 '(', ')', '[', ']', '{', '}' 的字符串，判断输入字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。2. 左括号必须以正确的顺序闭合。

算法思路

可以使用栈（Stack）这种数据结构来实现括号匹配算法。栈是一种后进先出（LIFO）的数据结构，非常适合用来跟踪括号的开闭关系。

算法步骤如下：

1. 创建一个空栈。2. 从左到右遍历字符串中的每个字符。3. 如果遇到左括号，则将其压入栈中。4. 如果遇到右括号，则进行以下判断： * 如果栈为空，则说明缺少左括号，匹配失败，返回 false。 * 如果栈不为空，则弹出栈顶元素，并判断弹出的左括号是否与当前的右括号匹配。 * 如果匹配，则继续遍历字符串。 * 如果不匹配，则说明括号类型不匹配，返回 false。5. 遍历完整个字符串后，如果栈为空，则说明所有括号都已匹配，返回 true；否则，说明缺少右括号，返回 false。

C++ 代码实现cpp#include #include using namespace std;

bool isValidParentheses(string str) { stack st; int len = str.size();

for (int i = 0; i < len; i++) {        if (str[i] == '(' || str[i] == '[' || str[i] == '{') {            st.push(str[i]);        }        else if (str[i] == ')') {            if (!st.empty() && st.top() == '(') {                st.pop();            }            else {                return false;            }        }        else if (str[i] == ']') {            if (!st.empty() && st.top() == '[') {                st.pop();            }            else {                return false;            }        }        else if (str[i] == '}') {            if (!st.empty() && st.top() == '{') {                st.pop();            }            else {                return false;            }        }    }

return st.empty();}

int main() { string str; cin >> str;

if (isValidParentheses(str)) {        cout << 'OK';    }    else {        cout << 'Wrong';    }

return 0;}

总结

本文介绍了如何使用C++实现一个简单的括号匹配算法，并提供了完整的代码示例。该算法利用栈这种数据结构，能够高效地判断字符串中的括号是否匹配。希望本文对您有所帮助！