The application of the stack—Parentheses Matching(括号匹配）

浏览数：20 / 时间：2015年06月11日

The thought of the algorithm is as follows:

(1) Initially set up an empty stack, sequentially read in parentheses;

(2) If it is a right parentheses, or it matches the stack top element, or it is illegal;

(3) If it is a left parentheses, it will be pushed into the stack.

When the algorithm is end, if the stack is empty, the parentheses matching is successful;

if the stack is not empty, the parentheses matching is failing.

The codes are as follows(C++):

 1 #include "stdafx.h"
 2 #include<iostream>
 3 #include "string.h"
 4 using namespace std;
 5 #define stacksize 100
 6 //定义栈的结构
 7 struct stack{
 8     char stackstr[stacksize];
 9     int top;
10 };
11 //初始化栈
12 void InitStack(stack &s){
13     s.top = -1;
14 }
15 //入栈操作
16 void Push(stack &s, char ch){
17     if (s.top == stacksize - 1)
18         cout << "站已满" << endl;
19     else{
20         s.top++;
21         s.stackstr[s.top] = ch;
22     }
23 }
24 //出栈操作
25 char Pop(stack &s){
26     if (s.top == -1)
27         return 0;
28     else{
29         char ch = s.stackstr[s.top];
30         return ch;
31     }
32 }
33 //判断栈是否为空
34 int IsEmpty(stack &s){
35     if (s.top == -1)
36         return 0;
37     else
38         return 1;
39 }
40 //括号匹配
41 int PrintMatchedPairs(char *str){
42     stack s;
43     InitStack(s);
44     int strLen = strlen(str);
45     for (int i = 0; i < strLen; i++){
46         char ch = str[i];
47         switch(ch){
48         case ‘(‘:
49         case ‘[‘:
50         case ‘{‘:
51             Push(s, ch);
52             break;
53         case ‘)‘:
54             if (Pop(s) != ‘(‘)
55                 return 0;
56             break;
57         case ‘]‘:
58             if (Pop(s) != ‘[‘)
59                 return 0;
60             break;
61         case ‘}‘:
62             if (Pop(s) != ‘{‘)
63                 return 0;
64             break;
65         }
66     }
67     int re = 0;
68     re = IsEmpty(s);
69     if (re == 0)
70         return 0;
71     if (re == 1)
72         return 1;
73 }
74 int main(){
75     char str[100];
76     cout << "请输入一个括号的字符串：" << endl;
77     cin >> str;
78     int re=PrintMatchedPairs(str);
79     if (re == 0)
80         cout << "括号完全匹配" << endl;
81     else
82         cout << "括号不匹配"<<endl;
83     return 0;
84 }