括号匹配

【问题描述】

   字符串中只含有括号 (),[]判断输入的字符串中括号是否匹配。

   如果括号有互相包含的形式，从内到外必须是 (),[]例如。

   输入: [()] 输出:YES，而输入([ ])， ([ )]都应该输出NO。

   输入：一个由括号组成的长度不超过255的字符串（前括号的数量大于等于后括号数量）。


   输出：YES或NO。

【输入样例】

(())(())[[]][[]]

【输出标例】

YES

按顺序（[ 分支 → ( 分支 → ) 分支 → ] 分支 → 栈空判断）写，代码如下。

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    stack<char> st;

    for (char c : s) {
        // 图1：如果是 [，看栈顶是否是 (
        if (c == '[') {
            if (!st.empty() && st.top() == '(') {
                cout << "NO" << endl;
                return 0;
            }
            st.push('[');
        }
        // 图4：如果是 (，直接入栈
        else if (c == '(') {
            st.push('(');
        }
        // 图2：如果是 )，看栈顶是否是 (
        else if (c == ')') {
            if (!st.empty() && st.top() == '(') {
                st.pop();
            } else {
                cout << "NO" << endl;
                return 0;
            }
        }
        // 图3：如果是 ]，看栈顶是否是 [
        else if (c == ']') {
            if (!st.empty() && st.top() == '[') {
                st.pop();
            } else {
                cout << "NO" << endl;
                return 0;
            }
        }
    }

    // 图5：如果栈为空
    if (st.empty()) cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;
}

对照流程图

方法二：

#include <iostream>
#include <stack>
#include <string>
using namespace std;

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

  stack<char> st;
  bool ok = true;

  for (char c : s) {
    if (c == '(' || c == '[') {
      // 嵌套约束：( 里面不能再套 [
      if (c == '[' && !st.empty() && st.top() == '(') {
        ok = false;
        break;
      }
      st.push(c);
    } else if (c == ')') {
      if (st.empty() || st.top() != '(') {
        ok = false;
        break;
      }
      st.pop();
    } else if (c == ']') {
      if (st.empty() || st.top() != '[') {
        ok = false;
        break;
      }
      st.pop();
    }
  }

  if (ok && st.empty())
    cout << "YES" << endl;
  else
    cout << "NO" << endl;

  return 0;
}