文章

20

粉丝

223

获赞

52

访问

125.3k

头像
栈的应用——带优先级的括号匹配问题
P1067 中山大学2019年机试题
发布于2022年2月3日 14:27
阅读数 6.4k

题目解析:用栈模拟即可,首先判断括号优先级,若判断错误则直接输出 NO,否则判断括号是否均配对,栈顶元素匹配就说明配对成功,将栈顶元素出栈,否则配对不成功,就将当前元素入栈。最后查看栈是否为空,若为空则是 YES,否则就是 NO。
 

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

int main() {
	int n;
	char s[256];
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%s", s);
		int len = strlen(s), flag = 0;  // flag用来标志括号嵌套是否合法
		stack<char> st;
		for (int i = 0; i < len; ++i) {
			if (!st.empty()) {
				char now = st.top();
				// 判断括号嵌套是否合法
				if (now == '<' && s[i] == '(' || now == '<' && s[i] == '[' 
					|| now == '<' && s[i] == '{' || now == '(' && s[i] == '[' 
					|| now == '(' && s[i] == '{' || now == '[' && s[i] == '{') {
						flag = 1;
						break;
				} else {
					// 判断括号是否配对 
					if (now == '<' && s[i] == '>' || now == '(' && s[i] == ')' 
						|| now == '[' && s[i] == ']' || now == '{' &&...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发