2020牛客寒假算法基础集训营4.B——括号序列STL _算法

知识就是力量，时间就是生命。这篇文章主要讲述2020牛客寒假算法基础集训营4.B——括号序列STL相关的知识，希望能为你提供帮助。

??题目传送门??
题目描述
给出一个仅包含’[’,’]’,’(’,’)’,’’,’六种字符的括号序列，判断其是否合法。

空串是一个合法的括号序列
如果A, B 都是合法的括号序列，那么AB也是合法的括号序列
如果A是合法的括号序列，(A) , [A], A都是合法的括号序列

输入描述:
一行一个字符串S，只包含题目中的六种括号字符
输出描述:
输出为一行"Yes" 或"No"
输入

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

输出

【2020牛客寒假算法基础集训营4.B——括号序列STL】Yes
Yes
No

备注:

题解

使用栈，从左到右处理每一个括号：
如果是左括号，那么入栈，然后继续读下一个括号
如果是右括号，那么就要看这个右括号和栈顶的括号是否匹配
如果匹配，那么弹出栈顶的括号，继续读下一个括号，否则说明不合法
最后，如果栈为空，说明此括号序列是合法的。
注意特殊样例 ‘(’，输出注意栈是否为空即可

AC-Code

#include < bits/stdc++.h>
using namespace std;
#define
typedef long long ll;

const int INF = 0x7fffffff;
const int maxn = 1e6 + 7;

bool check(char a, int b)

if (a == ( & & b == )) return true;
else if (a == [ & & b == ]) return true;
else if (a ==& & b == )return true;
else return false;

int main()
string s;
while (cin > > s)
stack< char> st;
bool flag = true;
for (int i = 0; i < s.length(); ++i)
if (s[i] == [ || s[i] == ( || s[i] == )
st.push(s[i]);

else
if (st.empty())// 注意特判为空
flag = false;
break;

char t = st.top();
st.pop();
if (!check(t, s[i]))
flag = false;
break;

if (flag & & st.empty())cout < < "Yes" < < endl; // 注意判空
elsecout < < "No" < < endl;

return 0;