Loading... [来自KeChang](https://blog.silvery.me/index.php/2023/07/17/%e4%b8%ad%e5%b1%b1%e5%a4%a7%e5%ad%a62019%e5%b9%b4-%e6%8b%ac%e5%8f%b7%e7%9a%84%e5%8c%b9%e9%85%8d/) **题目描述:** 在算术表达式中,除了加、减、乘、除等运算外,往往还有括号。 包括有大括号 `{}`,中括号 `[]`,小括号 `()`,尖括号 `<>` 等。 对于每一对括号,必须先左边括号,然后右边括号;如果有多个括号,则每种类型的左括号和右括号的个数必须相等;对于多重括号的情形,按运算规则,从外到内的括号嵌套顺序为:大括号 -> 中括号 -> 小括号 -> 尖括号,另外相同的括号可以嵌套。 例如,`{[()]}`, `{(())}`, `{{}}` 为一个合法的表达式,而 `([{}])`, `{([])}`, `[{<>}]` 都是非法的。 **输入格式:** 第一行包含整数 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; } ``` 最后修改:2023 年 08 月 06 日 © 允许规范转载 赞 如果觉得我的文章对你有用,请随意赞赏