首页 > 代码库 > 平衡的括号[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]