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

C++代码实现括号匹配

2023-07-05 12:11:14 深夜i -- --

C++ 代码实现括号匹配栈

括号匹配是一种常见的编程问题，需要在程序中进行括号匹配判断。在C++中可以通过使用栈来实现括号匹配功能。

栈是一种具有后进先出（LIFO）特点的数据结构，我们可以用栈来存储括号。当遇到左括号时，将其压入栈中；遇到右括号时，我们需要判断栈是否为空，如果栈为空，则说明存在不匹配的情况；如果栈不为空，则弹出栈顶元素，再将当前右括号与弹出栈顶元素进行匹配，如果匹配成功，继续执行程序，否则说明存在不匹配的情况。

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


#include <iostream>
#include <stack>
#include <cstring>
using namespace std;
bool isMatch(char a, char b) {
  return (a == '(' && b == ')') || (a == '[' && b == ']') || (a == '' && b == '');
}
bool isValid(string s) {
  stack<char> st;
  for (int i = 0; i < s.size(); ++i) {
    if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
      st.push(s[i]);
    } else {
      if (st.empty() || !isMatch(st.top(), s[i]))
        return false;
      
      st.pop();
    }
  }
  return st.empty();
}
int main() {
  string s1 = "()";
  string s2 = "()[]{}";
  string s3 = "(]";
  string s4 = "([)]";
  string s5 = "{[]}";
  
  cout << boolalpha << isValid(s1) << endl;
  cout << boolalpha << isValid(s2) << endl;
  cout << boolalpha << isValid(s3) << endl;
  cout << boolalpha << isValid(s4) << endl;
  cout << boolalpha << isValid(s5) << endl;
  
  return 0;
}

我们定义一个isMatch函数来判断左右括号是否匹配。使用stack st来存储括号，遍历字符串s的每一个字符，如果遇到左括号，将其压入栈中；如果遇到右括号，则弹出栈顶元素并与当前字符进行匹配，如果匹配成功则继续执行，否则说明存在不匹配的情况。最后判断栈是否为空，如果为空则说明所有括号均匹配。

在main函数中，我们分别测试了五组括号字符串，输出了每个字符串是否匹配的结果。通过运行结果可以看出，我们的括号匹配程序能够正确判断所有括号字符串的匹配情况。

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

下一篇: 如何在C++中实现数字倒序输出

评论区

()

相似文章