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

C++栈实现括号匹配

2023-06-22 10:40:44 深夜i -- --

C++ 栈括号匹配

在计算机编程中，经常面临括号匹配问题。例如，在检查网页HTML代码或编写计算式等场景中，括号匹配是一项重要的任务，而栈是实现该问题的常用解决方案之一。

利用C++中的栈数据结构，可以简单并且高效地解决括号匹配问题。栈是一种后进先出（LIFO）的数据结构，意味着最后入栈的元素最先出栈。在括号匹配问题中，我们可以使用栈来记录待匹配的左括号，并在遇到右括号时检查其与栈顶元素是否匹配。若两者匹配，则栈顶元素出栈。否则，说明括号未匹配成功，程序返回“无法匹配”的信息。

以下是基于C++栈实现括号匹配的代码实现：


#include<iostream>
#include<stack>
#include<string>
using namespace std;
bool match(char left, char right){
  if (left == '(' && right == ')')
    return true;
  else if (left == '[' && right == ']')
    return true;
  else if (left == '' && right == '')
    return true;
  else
    return false;
}
bool isBalanced(string str){
  stack<char> stack1;
  for (int i = 0; i < str.length(); i++){
    if (str[i] == '(' || str[i] == '[' || str[i] == '{')
      stack1.push(str[i]);
    else if (str[i] == ')' || str[i] == ']' || str[i] == '}'){
      if (stack1.empty() || !match(stack1.top(), str[i]))
        return false;
      else
        stack1.pop();
    }
  }
  return stack1.empty();
}
int main(){
  string str1 = "({[]})"; //匹配例子
  string str2 = "([{}])}"; //不匹配例子
  cout << isBalanced(str1) << endl;
  cout << isBalanced(str2) << endl;
  return 0;
}

在以上代码实现中，我们使用了一个`match`函数来检查左右括号是否匹配，使用了`stack`库来实现栈数据结构。然后，我们将输入的字符串中的字符逐一扫描查找，当遇到左括号时，将其入栈，反之遇到右括号时，检查其与栈顶元素是否匹配。当不匹配或栈为空时，说明括号未匹配成功，返回false。若扫描完成后栈为空，则说明括号匹配成功，返回true。

总之，利用C++栈数据结构可以简单又高效地实现括号匹配，大大减少了人工检查的繁琐和错误。

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

下一篇: 如何阅读Java多线程代码

评论区

()

相似文章