使用C++语言实现栈的创建、进栈、出栈、判断栈空等功能。
1 #include <iostream>
2 #include <string.h>
3 using namespace std ;
4
5 #define ERROR -1
6 #define CORRECT 1
7
8 //堆栈的定义,定义一个堆栈结构,其存储结构包含栈底指针base和栈顶指针top
9 #define MAXSTACKSIZE 100
10 typedef struct SqStack
11 {
12 char base[MAXSTACKSIZE] ;
13 char *top ;
14 } SqStack ;
15
16 SqStack MBStack ;
17
18 //初始化堆栈,若栈不存在(base == NULL),返回ERROR,将top指向base
19 int InitStack (SqStack &S)
20 {
21 if (S.base == NULL)
22 {
23 return (ERROR) ;
24 }
25 else
26 {
27 S.top = S.base ; //初始化堆栈(清空)
28 return (CORRECT) ;
29 }
30 }
31
32 //进栈,若top超出范围,返回ERROR,将数据(e)插入栈顶指定位置(top)上,栈顶指针(top)加一
33 int Push (SqStack &S , char e)
34 {
35 if ((S.top-S.base) >= MAXSTACKSIZE)
36 {
37 return (ERROR) ;
38 }
39 else
40 {
41 S.base[S.top - S.base] = e ;
42 S.top++ ;
43 return (CORRECT) ;
44 }
45 }
46
47 //出栈,若为空,返回ERROR,否则取出一个数据放入变量e中,top--
48 int Pop (SqStack &S , char &e)
49 {
50 if (S.top <= S.base)
51 {
52 return (ERROR) ;
53 }
54 else
55 {
56 e = S.base[S.top - S.base - 1] ;
57 S.top-- ;
58 return (CORRECT) ;
59 }
60 }
61
62 //判断栈空
63 int StackEmpty (SqStack &S)
64 {
65 if (S.top <= S.base)
66 {
67 return (ERROR) ;
68 }
69 else
70 {
71 return (CORRECT) ;
72 }
73 }
74
75 //括号匹配
76 int MatchBracket (SqStack &S , char *BracketString)
77 {
78 int i ;
79 char C , sC ;
80
81 InitStack (S) ; //清空堆栈
82 for (i = 0 ; i < strlen (BracketString) ; i++)
83 {
84 C = BracketString[i] ;
85
86 if ((C == '(') || (C == '[') || (C == '{'))
87 {
88 Push (S , C) ;
89 }
90 if ((C == ')') || (C == ']') || (C == '}'))
91 {
92 if (StackEmpty (S) == ERROR)
93 {
94 return (-2) ; //右多于左
95 }
96 Pop (S , sC) ;
97 if ((C == ')') && (sC != '('))
98 {
99 return (-1); //左右次序不对
100 }
101 if ((C == ']') && (sC != '['))
102 {
103 return (-1); //左右次序不对
104 }
105 if ((C == '}') && (sC != '{'))
106 {
107 return (-1); //左右次序不对
108 }
109 }
110 }
111
112 if (StackEmpty (S) != ERROR) //非空
113 {
114 return (-3) ; //左多于右
115 }
116
117 else
118 {
119 return (0) ; //栈空则正确
120 }
121 }
122
123 //主函数
124 int main (int argc , char* argv[])
125 {
126 int i , SampleNum ;
127 char BracketString[MAXSTACKSIZE] ;
128
129 cin >> SampleNum ;
130 for (i = 0 ; i < SampleNum ; i ++)
131 {
132 cin >> BracketString ;
133 cout << MatchBracket (MBStack , BracketString) << endl ;
134 }
135 return 0 ;
136 }
原文链接: https://www.cnblogs.com/maoguy/p/6002523.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/242895
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!