计算题
题目
把人逼急了什么都做得出来，除了数学题。
新学期，小J和小R发现他们怎么还有数学课，同时需要计算的式子越来越长了。
他俩发现现在的符号也越来越多了，有 [], (), {}, <>，令他们眼花缭乱，不过小R发现因为符号太多其中有一些式子的括号并没有完全匹配上，想让小J帮他检查一下。
但小J离散数学的作业还没有做完，现在分身乏术，想要你来帮助他！
小J和小R拿到了一个充满各种括号的式子，不过他们现在并不关心式子是否符合要求，也不关心括号的优先级，他们只想看看是不是所有括号都能被合法匹配。（合法匹配指每一个对应的左括号和对应的右括号之间不存在未被匹配的右括号）
输入：共三行，每行一个括号串，数据保证不存在题目要求括号以外的其他符号。
输出：对于每个括号串进行检查，如果能够完全匹配输出 YES，否则输出 NO。
样例1：
输入
{}[](<<{}>>)
(({}<>))
<({)}>}
输出
YES YES NO
样例2：
输入
{([<>]<>)()}
<>{[]{()}}()
({[<>]}{}{{<}>})
输出
YES YES NO
提示：对于 30% 的数据，保证每个字符串长度不超过 100，只存在（）。对于 60% 的数据，保证每个字符串长度不超过 1000。对于 100% 的数据，保证每个字符串长度不超过 100000。
思路
用栈来逐字符处理括号串。遇到左括号 ( [ { < 就入栈；
遇到右括号时，先判断栈是否为空（空则无左括号可匹配，直接 NO），
再判断栈顶的左括号与当前右括号是否是同一类型，不匹配则 NO，匹配则弹出栈顶。
遍历完整个字符串后，还需检查栈是否为空——若栈中仍有剩余左括号，说明未完全匹配，输出 NO；
全部通过才输出 YES。
#include<bits/stdc++.h>
using namespace std;
bool isMatch(char left, char right) {
if (left == '(' && right == ')') return true;
if (left == '[' && right == ']') return true;
if (left == '{' && right == '}') return true;
if (left == '<' && right == '>') return true;
return false;
}
void solve(string s) {
stack<char> st;
bool valid = true;
for (char c : s) {
if (c == '(' || c == '[' || c == '{' || c == '<') {
st.push(c);
} else {
if (st.empty()) {
valid = false;
break;
}
char topChar = st.top();
if (!isMatch(topChar, c)) {
valid = false;
break;
}
st.pop();
}
}
if (valid && st.empty()) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string line;
for (int c = 0; c < 3; c++) {
if (cin >> line) solve(line);
}
return 0;
}复杂度分析
- 时间复杂度：O(n)，每个字符入栈或出栈各一次。
- 空间复杂度：O(n)，栈最多存 n 个左括号。
遍历完还要检查栈是否为空，这个细节很容易漏掉。