Repository navigation
Expand file tree
/
Copy pathStackAlgorithms.h
More file actions
245 lines (225 loc) · 10.6 KB
/
Copy pathStackAlgorithms.h
File metadata and controls
245 lines (225 loc) · 10.6 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
/*--------------------------------------------------------------------------*/
/*------------------------- File StackAlgorithms.h -------------------------*/
/*--------------------------------------------------------------------------*/
/** @file
* Algorithms that use a STACK [see `ADT.h`] only through its operations,
* beyond the book:
*
* - `isPalindrome()`, the characters pushed and then popped against the
* string from its start, \f$ O( n ) \f$;
* - `sortStack()`, which sorts a stack with its own operations and the
* recursion: a pass pops two items, pushes back the larger, makes a pass
* on the rest recursively and pushes the smaller on top, so that the
* largest item sinks to the bottom and the smaller ones rise by one place;
* \f$ n - 1 \f$ passes sort the stack, the least on top, in
* \f$ \Theta( n^2 ) \f$;
* - `removeGreater()`, which removes the items larger than \f$ k \f$
* keeping the order of the others, with an auxiliary stack;
* - `forEachBottomUp()`, which visits the items from the bottom to the top
* and leaves the stack as it was: the top is popped, the rest visited
* recursively, then the top visited and pushed back, in \f$ O( n ) \f$
* time and \f$ O( n ) \f$ space for the recursion;
* - `isDyckWord()`, whether a sequence of \f$ +1 \f$ and \f$ -1 \f$ has no
* negative prefix sum (exercise 1.2 of Morin's book): it does exactly
* when the pushes for \f$ +1 \f$ and the pops for \f$ -1 \f$, run on an
* empty stack, never pop an empty stack, the prefix sum being the size
* of the stack; a stack of items all alike is a counter, which the
* function keeps;
* - `isMatched()`, whether a string of the brackets `()`, `[]` and `{}` is
* matched (exercise 1.3 of Morin's book): an open bracket is pushed, a
* closed one must find its open twin on top and pops it, and the stack
* must be empty at the end, \f$ O( n ) \f$; it is the Dyck word of the
* sizes of the stack with the kinds of the brackets on its items;
* - `reverseWithQueue()`, the order of a stack reversed by a QUEUE alone
* (exercise 1.4 of Morin's book): the items popped into the queue come
* out of it in the order they went in, the old top first, and pushed back
* in that order they leave the old top at the bottom, \f$ O( n ) \f$.
*
* The contracts [see `Contract.h`]: `sortStack()` ensures a sorted stack
* with the same number of items, `removeGreater()` a stack with no item
* larger than \f$ k \f$, `forEachBottomUp()` the stack as it was, and
* `reverseWithQueue()` the items in the reverse order; all are audits,
* checked by popping the stack and pushing it back. The algorithms are
* defined in `StackAlgorithms.tpp`.
*
* \see A. Montresor, Algoritmi e Strutture Dati, 2025, section 4.3.1,
* https://algoritmicamente.it/materiali/libro/capitoli/cap04.pdf
* \see P. Morin, Open Data Structures (in C++), Edition 0.1G, 2013,
* https://opendatastructures.org/ods-cpp.pdf, exercises 1.2, 1.3 and 1.4
*
* \author Donato Meoli \n
* Dipartimento di Informatica \n
* Università di Pisa \n
*
* \copyright © by Donato Meoli
*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/
#ifndef __ADS_StackAlgorithms
#define __ADS_StackAlgorithms
/* self-identification: #endif constant */
/*--------------------------------------------------------------------------*/
/*------------------------------ INCLUDES ----------------------------------*/
/*--------------------------------------------------------------------------*/
#include "ADS/ADT.h"
#include "ADS/Contract.h"
#include "ADS/queue/LinkedQueue.h"
#include "ADS/sequence/List.h"
#include "ADS/stack/ArrayStack.h"
#include "ADS/stack/SequenceStack.h"
#include <algorithm>
#include <span>
#include <string>
#include <string_view>
#include <vector>
/*--------------------------------------------------------------------------*/
/*--------------------------- NAMESPACE ------------------------------------*/
/*--------------------------------------------------------------------------*/
namespace ADS
{
/// whether \f$ s \f$ reads the same from both ends
///
/// In pseudocode (section 4.3.1), the stack reversing the string:
/// \f[
/// \class{pseudocode}{\begin{array}{r@{\quad}l}
/// 1 & \textbf{function}\ \mathrm{isPalindrome}( s ) \cr
/// 2 & \quad S \gets \text{an empty stack};\ \textbf{foreach}
/// \ \text{character } c \text{ of } s\ \textbf{do}\ \mathrm{push}( S ,
/// c ) \cr
/// 3 & \quad \textbf{foreach}\ \text{character } c \text{ of } s
/// \ \textbf{do}\quad \triangleright\ S \text{ gives } s
/// \text{ backwards} \cr
/// 4 & \qquad \textbf{if}\ c \ne \mathrm{pop}( S )
/// \ \textbf{then return false} \cr
/// 5 & \quad \textbf{return true}
/// \end{array}}
/// \f]
inline bool isPalindrome( const std::string & s );
/// sorts \f$ s \f$ with the least item on top
///
/// In pseudocode (section 4.3.1, the bubble sort on a stack), \f$ n - 1 \f$
/// passes, each carrying the largest item it meets to the bottom:
/// \f[
/// \class{pseudocode}{\begin{array}{r@{\quad}l}
/// 1 & \textbf{procedure}\ \mathrm{pass}( s )\quad \triangleright
/// \ \text{the largest item to the bottom} \cr
/// 2 & \quad \textbf{if}\ \mathrm{empty}( s )\ \textbf{then return} \cr
/// 3 & \quad a \gets \mathrm{pop}( s ) \cr
/// 4 & \quad \textbf{if}\ \textbf{not}\ \mathrm{empty}( s )\ \textbf{then}
/// \cr
/// 5 & \qquad b \gets \mathrm{pop}( s );\ \mathrm{push}( s , \max( a , b )
/// );\ \mathrm{pass}( s );\ a \gets \min( a , b ) \cr
/// 6 & \quad \mathrm{push}( s , a ) \cr
/// 7 & \textbf{procedure}\ \mathrm{sortStack}( s ) \cr
/// 8 & \quad \mathrm{pass}( s ) \text{, } n - 1 \text{ times}
/// \end{array}}
/// \f]
/// \post \f$ s \f$ is sorted, the least on top, with the same number of
/// items (an audit)
template< Stack S >
void sortStack( S & s );
/// removes the items larger than \f$ k \f$, the others in their order
///
/// In pseudocode (section 4.3.1), the auxiliary stack reversing the order
/// twice:
/// \f[
/// \class{pseudocode}{\begin{array}{r@{\quad}l}
/// 1 & \textbf{procedure}\ \mathrm{removeGreater}( s , k ) \cr
/// 2 & \quad A \gets \text{an empty stack}\quad \triangleright
/// \ \text{the kept items, reversed} \cr
/// 3 & \quad \textbf{while not}\ \mathrm{empty}( s )\ \textbf{do} \cr
/// 4 & \qquad x \gets \mathrm{pop}( s );\ \textbf{if}\ \textbf{not}\ x > k
/// \ \textbf{then}\ \mathrm{push}( A , x ) \cr
/// 5 & \quad \textbf{while not}\ \mathrm{empty}( A )\ \textbf{do}
/// \ \mathrm{push}( s , \mathrm{pop}( A ) )\quad \triangleright
/// \ \text{the order restored}
/// \end{array}}
/// \f]
/// \post no item is larger than \f$ k \f$ (an audit)
template< Stack S >
void removeGreater( S & s , const typename S::Item & k );
/// `f( x )` on each item \f$ x \f$, from the bottom to the top
///
/// In pseudocode (section 4.3.1), the stack of the calls holding the items
/// popped:
/// \f[
/// \class{pseudocode}{\begin{array}{r@{\quad}l}
/// 1 & \textbf{procedure}\ \mathrm{forEachBottomUp}( s , f ) \cr
/// 2 & \quad \textbf{if}\ \textbf{not}\ \mathrm{empty}( s )\ \textbf{then}
/// \cr
/// 3 & \qquad x \gets \mathrm{pop}( s );\ \mathrm{forEachBottomUp}( s , f
/// )\quad \triangleright\ \text{the items below } x \text{ first} \cr
/// 4 & \qquad f( x );\ \mathrm{push}( s , x )
/// \end{array}}
/// \f]
/// \post \f$ s \f$ is as it was (an audit)
template< Stack S , class F >
void forEachBottomUp( S & s , F && f );
/// whether the sequence \f$ w \f$ of \f$ +1 \f$ and \f$ -1 \f$ is a Dyck word,
/// i.e., has no negative prefix sum
///
/// In pseudocode (Morin, exercise 1.2), the stack of items all alike kept
/// as its size \f$ h \f$:
/// \f[
/// \class{pseudocode}{\begin{array}{r@{\quad}l}
/// 1 & \textbf{function}\ \mathrm{isDyckWord}( w ) \cr
/// 2 & \quad h \gets 0 \cr
/// 3 & \quad \textbf{foreach}\ c \in w\ \textbf{do} \cr
/// 4 & \qquad \textbf{if}\ c = +1\ \textbf{then}\ h \gets h + 1
/// \quad \triangleright\ \mathrm{push} \cr
/// 5 & \qquad \textbf{else if}\ h = 0\ \textbf{then return false}
/// \ \textbf{else}\ h \gets h - 1\quad \triangleright\ \mathrm{pop} \cr
/// 6 & \quad \textbf{return true}
/// \end{array}}
/// \f]
/// \pre each item of \f$ w \f$ is \f$ +1 \f$ or \f$ -1 \f$
inline bool isDyckWord( std::span< const int > w );
/// whether \f$ s \f$, a string of the brackets `()`, `[]` and `{}`, is
/// matched, in \f$ O( n ) \f$
///
/// In pseudocode (Morin, exercise 1.3):
/// \f[
/// \class{pseudocode}{\begin{array}{r@{\quad}l}
/// 1 & \textbf{function}\ \mathrm{isMatched}( s ) \cr
/// 2 & \quad S \gets \text{an empty stack} \cr
/// 3 & \quad \textbf{foreach}\ \text{character } c \text{ of } s
/// \ \textbf{do} \cr
/// 4 & \qquad \textbf{if}\ c \text{ opens}\ \textbf{then}\ \mathrm{push}(
/// S , c ) \cr
/// 5 & \qquad \textbf{else if}\ \mathrm{empty}( S )\ \textbf{or}
/// \ \mathrm{pop}( S ) \text{ does not open } c
/// \ \textbf{then return false} \cr
/// 6 & \quad \textbf{return}\ \mathrm{empty}( S )
/// \end{array}}
/// \f]
/// \pre \f$ s \f$ holds only brackets
inline bool isMatched( std::string_view s );
/// the order of the items of \f$ s \f$ reversed by a QUEUE, the only
/// operations of \f$ s \f$ being `push()` and `pop()`
///
/// In pseudocode (Morin, exercise 1.4):
/// \f[
/// \class{pseudocode}{\begin{array}{r@{\quad}l}
/// 1 & \textbf{procedure}\ \mathrm{reverseWithQueue}( s ) \cr
/// 2 & \quad Q \gets \text{an empty queue} \cr
/// 3 & \quad \textbf{while not}\ \mathrm{empty}( s )\ \textbf{do}
/// \ \mathrm{enqueue}( Q , \mathrm{pop}( s ) ) \cr
/// 4 & \quad \textbf{while not}\ \mathrm{empty}( Q )\ \textbf{do}
/// \ \mathrm{push}( s , \mathrm{dequeue}( Q ) )
/// \end{array}}
/// \f]
/// \post the items of \f$ s \f$ in the reverse order (an audit)
template< Stack S , Queue Q = LinkedQueue< typename S::Item > >
void reverseWithQueue( S & s );
/*--------------------------------------------------------------------------*/
} // end( namespace ADS )
/*--------------------------------------------------------------------------*/
/*-------------------------- IMPLEMENTATION --------------------------------*/
/*--------------------------------------------------------------------------*/
#include "ADS/stack/impl/StackAlgorithms.tpp"
/*--------------------------------------------------------------------------*/
#endif /* StackAlgorithms.h included */
/*--------------------------------------------------------------------------*/
/*----------------------- End File StackAlgorithms.h -----------------------*/
/*--------------------------------------------------------------------------*/