首页 > 代码库 > 平衡的括号[UVA-673]
平衡的括号[UVA-673]
UVA673 Parentheses Balance
书上习题6-1,题比较简单,主要是使用栈这个“后进先出”的数据结构。因为平衡的括号,必然可以在左半括号进行push而右半括号进行pop,当到达序列末尾而栈不空,显然不满足题意了。
抛开题目说几点内容:一是之前看王爽的《汇编语言》,对栈的pop操作有些误解。在汇编语言中(8086包括现在的IA32、X86-64指令),pop指令有一个操作数,表示将栈顶的元素出栈后所放置的内存单元地址;而在数据结构的栈中,pop操作只是将栈顶元素出栈,直接就丢了。我一开始是用汇编语言的栈去理解,总是以为pop必然可以返回栈顶元素。事实上应该先用top操作去获得栈顶元素,而后用pop弹出栈顶元素。push操作则比较类似了,都带有一个操作数,都表示要压栈的元素。二是本题的描述使用了离散数学课程中的递归定义,[(])显然是不符合这个递归定义的,因为假设[]合法,两个中括号夹着的的A=(必然也需要合法,而实际上只有半个括号,是不合法的,与假设矛盾。除此之外,gets()函数需要考虑之前的空行,不然读入的是包含换行符的空串。
C++实现如下:
1 #include<iostream> 2 #include<cstdio> 3 #include<stack> 4 #include<cstring> 5 using namespace std; 6 int main() 7 { 8 stack<char> s; 9 char buf[200]; 10 int cases; 11 cin >> cases; 12 getchar(); 13 while (1) 14 { 15 RESTART: 16 if (!cases--) 17 break; 18 while (!s.empty()) 19 s.pop(); 20 gets(buf); 21 if (strcmp(buf, "\n") == 0) 22 { 23 printf("Yes\n"); 24 continue; 25 } 26 for (int i = 0; buf[i] != 0; i++) 27 { 28 switch (buf[i]) 29 { 30 case ‘(‘: 31 case ‘[‘: 32 s.push(buf[i]); 33 break; 34 case ‘)‘: 35 if (s.empty() || s.top() != ‘(‘) 36 { 37 printf("No\n"); 38 goto RESTART; 39 } 40 else 41 s.pop(); 42 break; 43 case ‘]‘: 44 if (s.empty() || s.top() != ‘[‘) 45 { 46 printf("No\n"); 47 goto RESTART; 48 } 49 else 50 s.pop(); 51 break; 52 } 53 } 54 if (s.empty()) 55 printf("Yes\n"); 56 else 57 printf("No\n"); 58 } 59 return 0; 60 }
平衡的括号[UVA-673]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。