스택의 적용 - 괄호 일치

알고리즘의 생각은 다음과 같습니다.
(1) 처음에 빈 스택을 설정하고 괄호 안에 순차적으로 읽습니다.
(2) 오른쪽 괄호이거나 스택 맨 위 요소와 일치하거나 잘못된 경우;
(3) 왼쪽 괄호이면 스택에 푸시됩니다.
알고리즘이 종료될 때 스택이 비어 있으면 괄호 일치가 성공합니다.
스택이 비어 있지 않으면 괄호 일치가 실패합니다.
코드는 다음과 같습니다(C++).

 1 #include "stdafx.h"
 2 #include
 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 }

 

재인쇄: https://www.cnblogs.com/GavinLIU/p/3890940.html