题目描述:

在算术表达式中,除了加、减、乘、除等运算外,往往还有括号。

包括有大括号 {},中括号 [],小括号 (),尖括号 <> 等。

对于每一对括号,必须先左边括号,然后右边括号;如果有多个括号,则每种类型的左括号和右括号的个数必须相等;对于多重括号的情形,按运算规则,从外到内的括号嵌套顺序为:大括号 -> 中括号 -> 小括号 -> 尖括号,另外相同的括号可以嵌套。

例如,{[()]}, {(())}, {{}} 为一个合法的表达式,而 ([{}]), {([])}, [{<>}] 都是非法的。

输入格式:

第一行包含整数 n,表示共有 n 个表达式需要判断。

接下来 n 行,每行包含一个括号表达式。

输出格式:

每行输出一个表达式的判断结果。

如果合法输出 YES,否则输出 NO

数据范围:

  • 1 ≤ n ≤ 100
  • 表达式长度不超过 100

输入样例:

5
{[(<>)]}
[()]
<>()[]{}
[{}]
{()}

输出样例:

YES
YES
YES
NO
YES

题目分析: 给括号映射优先级,并使用栈来判断合法性。

代码实现:

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

int n;
string s;
unordered_map <char,int> mpv = {
    {'{',4},
    {'[',3},
    {'(',2},
    {'<',1}
};
unordered_map <char,char> mp = {
    {'}','{'},
    {']','['},
    {')','('},
    {'>','<'}
};
bool solve() {
    stack <char> st;
    cin >> s;
    for (auto& i : s) {
        if (st.empty()) {
            if (mpv.find(i) != mpv.end()) {
                st.push(i);
            }
            else return false;
        }
        else {
            if (st.top() == mp[i]) st.pop();
            else {
                if (mpv.find(i) != mpv.end()) {
                    if (mpv[i] <= mpv[st.top()]) st.push(i);
                    else return false;
                }
                else return false;
            }
        }
    }
    return st.empty();
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    while (n--) {
        solve() ? cout << "YES\n" : cout << "NO\n";
    }
    return 0;
}
分类: Stack

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status