堆栈小应用（一）：括号匹配程序

1、问题描述：

　　在这个问题中将要匹配一个字符串中的左、右括号。例如，字符串 ( a * ( b + c ) + d )在位置1 和4有左括号，在位置 8和 11 有右括号。位置 1 的左括号匹配位置 11 的右括号，位置 4的左括号匹配位置8的右括号。对于字符串 ( a + b ) ) (，位置 6的右括号没有可匹配的左括号，位置 7的左括号没有可匹配的右括号。我们的目标是编写一个 C + +程序，其输入为一个字符串，输出为相互匹配的括号以及未能匹配的括号。可用来解决 C + +程序中的 {和}的匹配问题。
可以观察到，如果从左至右扫描一个字符串，那么每个右括号将与最近遇到的那个未匹配的左括号相匹配。这种观察结果使我们联想到可以在从左至右的扫描过程中把所遇到的左括号存放到堆栈内。每当遇到一个右括号时，就将它与栈顶的左括号（如果存在）相匹配，同时从栈顶删除该左括号。
时间复杂度为O（n），n为字符串长度。

2、代码实现
堆栈可以用数组和链表方式实现。实现方式见：

堆栈的公式化描述实现，堆栈的链表方式实现

在这个问题中，2种方式实现方式基本相同，只是实例化堆栈时略有不同。

C++实现（公式化堆栈）：

 1 #include <iostream>
 2 #include <string>
 3 #include "ArrayStack.h"
 4 using std::cout;
 5 using std::cin;
 6 using std::endl;
 7 
 8 void outputMatchedPairs(const std::string& str);
 9 int main()
10 {
11     std::string str;
12     cout << "输入一个字符串:" << endl;
13     getline(cin,str);
14     cout << "你输入的字符串是：" << str << endl;
15     cout << "里面匹配的括号位置是" << endl;
16     outputMatchedPairs(str);
17 
18     system("pause");
19     return 0;
20 }
21 
22 void outputMatchedPairs(const std::string& str)
23 {
24     ArrayStack<char> S(str.length()+1);//实例化堆栈记录左括号
25     ArrayStack<int> pos(str.length()+1);//记录左括号位置
26     char temp;
27     int j;
28     for (int i = 1; i <=str.length();++i)
29     {
30         if (str[i-1]=='(')
31         {
32             S.Add(str[i-1]);
33             pos.Add(i);
34         }
35         else if(str[i-1]==')')
36         {
37             if (S.IsEmpty())
38             {
39                 cout << "没有与" << i << "处右括号匹配的左括号" << endl;
40             }
41             else
42             {
43                 pos.Delete(j);
44                 S.Delete(temp);
45                 cout << "MatchedPairs: " << j << " " << i << endl;
46             }
47         }
48     }
49 
50     while (!pos.IsEmpty())//若堆栈中还有左括号，则未匹配
51     {
52         S.Delete(temp);
53         pos.Delete(j);
54         cout << "没有与" << j << "处左括号匹配的右括号" << endl;
55 
56     }
57 }

链表方式实现：

 1 // BracketMatch2.cpp : 定义控制台应用程序的入口点。
 2 //
 3 
 4 #include "stdafx.h"
 5 #include <iostream>
 6 #include <string>
 7 #include "LinkedStack.h"
 8 
 9 using std::cout;
10 using std::cin;
11 using std::endl;
12 void outputMatchedPairs(const std::string& str);
13 
14 int _tmain(int argc, _TCHAR* argv[])
15 {
16     std::string str;
17     cout << "输入一个字符串:" << endl;
18     getline(cin, str);
19     cout << "你输入的字符串是：" << str << endl;
20     cout << "里面匹配的括号位置是" << endl;
21     outputMatchedPairs(str);
22 
23     system("pause");
24     return 0;
25 }
26 
27 void outputMatchedPairs(const std::string& str)
28 {
29     LinkedStack<char> S;
30     LinkedStack<int> pos;
31     char temp;
32     int j;
33     for (int i = 1; i <= str.length(); ++i)
34     {
35         if (str[i - 1] == '(')
36         {
37             S.Add(str[i - 1]);
38             pos.Add(i);
39         }
40         else if (str[i - 1] == ')')
41         {
42             if (S.IsEmpty())
43             {
44                 cout << "没有与" << i << "处右括号匹配的左括号" << endl;
45             }
46             else
47             {
48                 pos.Delete(j);
49                 S.Delete(temp);
50                 cout << "MatchedPairs: " << j << " " << i << endl;
51             }
52         }
53     }
54 
55     while (!pos.IsEmpty())
56     {
57         S.Delete(temp);
58         pos.Delete(j);
59         cout << "没有与" << j << "处左括号匹配的右括号" << endl;
60 
61     }
62 }

输出：