# Stack datastructure using LaTeX

A very common programming data structure is a stack. A stack is simply a one dimensional array. Stack elements are pushed in or popped out of the stack one at a time as LIFO (Last In First Out).

I am trying to build a general routine to represent such stacks using LaTeX2e. The stack has two operations a pop and a push.

The popped elements are stored in a macro \popped@element, so that they can be pushed into another stack if necessary or typeset material. At this point I provided a\before@pop@hook and an \after@pop@hook, to enable surrounding material to be added. Not sure if this correct from a design point. To get material in an fbox the construction became very weird (see lines 71-72):

\def\before@pop@hook{\bgroup\color{blue}\fbox}
\def\after@pop@hook{\egroup}


I am looking for improvements/corrections to the code to make it more robust and accept any type of input such as verbatim text, ability to be inserted into tables, i.e, which sections of the code would need to become outer etc.

So far I have come up with this MWE:

\documentclass{book}
\usepackage[latin]{babel}
\usepackage{xcolor,lipsum}
\parindent0pt
\makeatletter
\newcommand\lorem{Fusce adipiscing justo nec ante. Nullam in enim.
Pellentesque felis orci, sagittis ac, malesuada et, facilisis in,
ligula. Nunc non magna sit amet mi aliquam dictum. In mi. Curabitur
sollicitudin justo sed quam et quadd.}
% Define a new stack by letting it to \@empty
\newcommand\newstack[1]{%
\let#1\@empty
}
% #1 stack name
%  #2 element contents
\def\element{#2}%
\push@element{#1}
}
% #1 stack name
\newcommand{\push@element}[1]{%
\xdef#1{\element+#1}
}

%% Add hooks here for typesetting

\def\before@pop@hook{\bgroup\color{red}}
\def\after@pop@hook{\egroup}

\def\before@pop@hook{}
\def\after@pop@hook{}

\long\def\pop@#1+#2\@nil#3{%
\def\popped@element@{\before@pop@hook{#1}\after@pop@hook}
\def\popped@element{#1}
% \xdef\element{#1} if required?
% remaining list
\def#3{#2}%
}

% stack name #1
\newcommand\pop@element[1]{%
\ifx #1\@empty  Error\else
\expandafter\pop@#1\@nil#1
\fi
}

\begin{document}
% Create two stacks
\newstack{\stack}
\newstack{\tempstack}
% add some elements to stack
\def\elt@start{Start }\def\elt@stop{Stop}

% pop some elements from \stack
% and put them in boxes
Popped from stack

\pop@element{\stack}
\popped@element@
\pop@element{\stack}
\popped@element@

% add last popped element from \stack to \temp
% pop it into blue box
\def\before@pop@hook{\bgroup\color{blue}\fbox}
\def\after@pop@hook{\egroup}
\parbox{3cm}{\popped@element@}

\def\X{german}
\def\Y{\popped@element}

In temp stack \tempstack

\def\before@pop@hook{}
\def\after@pop@hook{}

\pop@element{\stack}
\parbox{3.9cm}{\popped@element@}

\end{document}


LaTeX3 and Lua solutions are also welcome, provided they come with long explanations.

Update

It is a pity that I cannot accept all the answers as they are all great and examined the issues from all aspects. I was especially impressed with Frank's and Joseph's answers and their explanations. cjorssen's Lua solution is very promising and can be very useful, if one wanted to parse the contents further. I have accepted Bruno's answer as it was the one with a MWE and clearly demonstrating the use of verbatim text in lists.

-
(1) Assuming that eTeX extension are available, most of your \def\foo{...} should be turned into \edef\foo{\unexpanded{...}}, to allow macro parameters to appear in elements of your stacks (see e.g., the definition of \tl_set:Nn in l3tl.dtx). (2) Using + as a delimiter strikes me as very unsafe. Either use a private cs as a delimiter (possibly let to \relax, or with the appropriate \noexpand at various places). (3) Better than <delim><item><delim><item> is <cs>{<item>}<cs>{<item>}: then the <item> can contain arbitrary (non-outer) tokens. –  Bruno Le Floch Feb 27 '12 at 8:48
(4) You are not consistent between local and global assignments (using \xdef in \push@element and \def in \pop@). Either stick to one, or provide both. (5) It is good to catch the case of an empty stack when popping, but I'd go for an actual error (using \errmessage --- or \PackageError, whatever). (6) Hard-wiring \popped@element into the definitions seems to restrict the generality of your code. (7) Your \def\Y{\popped@element} seems incorrect: you may want \edef, or \edef\Y{\unexpanded\expandafter{\popped@element}}. (8) I could list a bunch of functions to add... –  Bruno Le Floch Feb 27 '12 at 8:56
@BrunoLeFloch Thanks, used + as a quick delimiter as I am testing with text only. Will have a look at l3tl.dtx. –  Yiannis Lazarides Feb 27 '12 at 8:58
I think you should welcome good explanations, not long. –  Marc van Dongen Feb 27 '12 at 8:58
You could also have a look at Section 14.5 of TeX by Topic where an example is given of using a token list as a stack. –  Roelof Spijker Feb 27 '12 at 9:05

The question allows us to use TeX macros or Lua in the answer: I will stick to macros, and leave the Lua answer to an expert! A lot of what I will discuss here is implemented in the LaTeX3 module l3seq, which uses 'sequences' for stack operations. This LaTeX3 module has been through a number of internal revisions, which reflect some of the issues I will try to cover.

For a truly general stack, you want to be able to handle any tokens given as input. That leads to two conclusions:

• Using a macro for storage is fine when using e-TeX, but if the solution has to work with only TeX primitives then a toks should be used for the underlying storage. With e-TeX, we can use the

\edef\foo{\unexpanded{...}}


approach to put # tokens inside a macro safely.

• Using a 'special' token for delimiting items

\marker item1\marker item2\marker


is no good as we cannot put \marker in any of the items without braces. This approach also risks dropping braces around items, so the distinct input {item} and item may end up the same when popped. Instead, a macro which takes an argument should be used for the structure

\item@marker{item1}\item@marker{item2}


This is also useful when it comes to mapping to a stack, as you can redefine the marker macro so it acts on the item, rather than simply marking it's position. (This is similar to how for example \dospecials works: \do is a delimiter or a function, depending on what we want.)

So taking the above into account, the basic structure for a stack can be implemented with something like

\newcommand{\stack@item}[1]{\ERROR}


where we assume that if an attempt is made to direct use a stack entry then it is an error.

When adding to and removing from a stack, you need to watch global/local assignment. One approach you can take here is to use an auxiliary which works for both local and global forms, and pass the appropriate information as an argument from the main macros. I'm going to stick to just local assignments: see for example l3seq for how this can be generalised.

\newcommand{\stack@push}[2]{%
\edef#1{%
\unexpanded{\stack@item{#2}}%
\unexpanded\expandafter{#1}%
}%
}
\newcommand{\stack@pop}[2]{%
\ifx#1\@empty
\expandafter\stack@pop@error
\else
\expandafter\stack@pop@aux
\fi
#1#2%
}
\newcommand{\stack@pop@error}[2]{%
\PackageError{mystackpackage}
{Cannot pop from empty stack #1}
{Some more text!}%
}
\newcommand{\stack@pop@aux}[2]{%
\expandafter\stack@pop@aux@ii#1\q@stop#1#2%
}
\long\def\stack@pop@aux@ii\stack@item#1#2\q@stop#3#4{%
\def#3{#2}%
\def#4{#1}%
}


There are then a lot more functions you can imagine adding, for example mappings, expandable 'top' functions, selecting an item by number from the end of the stack and so on. These are all doable (again see l3seq for some ideas).

-
Joseph -- Thanks so still the best approach (in a way) for marking is \@elt lists? \item@marker{item1} seems very similar. –  Yiannis Lazarides Feb 27 '12 at 12:39
@YiannisLazarides Yes, that's a reasonable interpretation. –  Joseph Wright Feb 27 '12 at 13:20

Joseph already mentioned that in his answer, but I think it is worth pointing out prominentely, the solution within the LaTeX3 programming language expl3 is the seq module.

You can access its documentation by running

latex l3seq.dtx


or as part of the complete programming interface documentation interface3.tex.

It offers not just a set of stack operations (like get, push, pop) but also more general operations on sequences and stacks such as adding on the left or right, mapping code over the sequence to be applied to each item in turn, various conditionals including checking for data within the sequence, etc.

What it doesn't do though is managing verbatim material. In fact there is no proper solution for this anywhere if it comes down to catcode manipulations on the fly. If you want this then you need to completely separate the input layer, identify your verbatim material there, turn it into something that can be processed by the internals of the TeX engine safely and only then start assemling thing into arguments to be passed to functions like stack operations.

-
Provided verbatim material is tokenized by 'some grabber', it should be fine inside a sequence as we are not using any particular form of token as a delimiter. One for xparse ... –  Joseph Wright Feb 27 '12 at 19:56
@joseph this is what I meant with fully separating initial input processing before you start moving any input data into standard TeX type arguments in braces. Yes, of course, it is possible but it needs to be done all the way through and not just for individual commands (because those could themselves end up in arguments of others). –  Frank Mittelbach Feb 27 '12 at 21:18
@Frank: Do you have time to add more examples of code using l3seq for what Yiannis does in his question? Or should I edit your answer? (I'll post an "explain the implementation" answer soonish.) –  Bruno Le Floch Mar 2 '12 at 8:20

This answer focuses on the "verbatim" aspect, ignoring the details of stacks almost entirely. We only manipulate one stack, \l_foo_seq, using expl3. Of course, this could be generalized to more than one stack.

For verbatim to work, TeX must be told to ignore all category codes before it starts reading the material. The code below defines

• \push{...} to add ... to the stack, reading as a normal argument.
• \push|...| with any pair of identical delimiters to read ... as verbatim material and add it to the stack.
• \popto removes the top item and typesets it, using the category codes that were in effect when the item was captured.
• \popto[\result] stores the item in \result instead of typesetting it.
• \popto* typesets the item using current category codes (this uses \scantokens under the hood).
• \popto*[\result] stores the item in \result after changing category codes to the current ones.

Here goes the code.

\documentclass{article}
\usepackage{xparse}
\ExplSyntaxOn
\seq_new:N \l_foo_seq
\tl_new:N \l_foo_tl
\NewDocumentCommand { \push } { }
{
\peek_catcode:NTF \c_group_begin_token
{ \push_normal:n }
{ \push_verbatim:w }
}
\NewDocumentCommand { \push_verbatim:w } { +v } { \push_normal:n {#1} }
\cs_new_protected:Npn \push_normal:n #1 { \seq_push:Nn \l_foo_seq {#1} }
\NewDocumentCommand { \pop } { s o }
{
\seq_pop:NN \l_foo_seq \l_foo_tl
\IfBooleanTF{#1}
{
\IfNoValueTF {#2}
{ \exp_args:NV \etex_scantokens:D \l_foo_tl }
{ \tl_set_rescan:NnV #2 { } \l_foo_tl }
}
{
\IfNoValueTF {#2}
{ \tl_use:N \l_foo_tl }
{ \tl_set_eq:NN #2 \l_foo_tl }
}
}
\cs_generate_variant:Nn \tl_set_rescan:Nnn { NnV }
\ExplSyntaxOff
\begin{document}
\push|\verb+!@#$%^+| \push|\begin{verbatim}!@#$%$\end{verbatim}| \pop* \push|\TeX| \pop % Catcode other \push|\TeX| \pop* % Initially catcode other, but \pop* resets them. \push{\TeX} \pop % Normal catcodes { \push{\TeX} % Normal catcodes \catcode\\=9\pop* % Turn backslash into an ignored character. } \pop* \end{document}  - Thatnks --It works:) What does \cs_generate_variant:Nn \tl_set_rescan:Nnn { NnV } do? – Yiannis Lazarides Feb 28 '12 at 14:32 @Yiannis to explain that in detail would probably requiry a question with answering space, but in a nutshell "variants" do preprocessing of the argument (depending on the signature) "V" means "Value of some variable" so the base function will get the value and not the variable name passed to it. This way expl3 can easily avoid all type of complicated expansions on code-level. – Frank Mittelbach Feb 28 '12 at 16:23 @FrankMittelbach Thanks. I will look it up in the manual. – Yiannis Lazarides Feb 28 '12 at 16:25 @Yiannis it is one of the really powerfull concepts of expl3. – Frank Mittelbach Feb 28 '12 at 16:43 Edit (28 Feb. 2012) Thanks to the comments below, here is a version with the stack stored as a table. I added a basic idea to deal with verbatim material (that is parsing the content of an entry to see if a match with \begin{verbatim}...\end{verbatim} is positive. If true, when this entry is popped, the code takes care of the catcode régime. Note the space after \\begin and \\end in the lpeg patterns. They are introduced by the \directlua/\unexpanded couple (correct me if I'm wrong). As Bruno Le Floch pointed out in comments, the poor man's verbatim here will fail if the argument given to \pushstack contains a % or an unbalanced brace { or }. -- Save this as stack.lua stack = stack or {} local lpeg = require('lpeg') local space = lpeg.S(' \n\t') local bverb = lpeg.P('\\begin {verbatim}') local everb = lpeg.P('\\end {verbatim}') local verbatim = lpeg.P(bverb * lpeg.C((1 - everb)^0) * everb) / function (s) tex.sprint(-1,'\\begin{verbatim}') tex.sprint(0,s) tex.sprint(-1,'\\end{verbatim}') end function stack.push (t, s) texio.write_nl(s) t[#t+1] = s end function stack.pop (t) local s = t[#t] t[#t] = nil if lpeg.match(verbatim,s) == nil then return tex.sprint(-1,'\\beforepophook{}' .. s .. '\\afterpophook{}') else return lpeg.match(verbatim,s) end end function stack.print (t) tex.sprint(-1,'\\par\\begin{tabular}{l|l}') for i = #t,1,-1 do tex.sprint(-1,tostring(i) .. '&' .. '\\texttt{') tex.sprint(-2,t[i]) tex.sprint(-1,'}\\\\') end tex.sprint(-1,'\\end{tabular}\\par') end return stack  And here is the TeX wrapper and example file. \documentclass{article} \usepackage{lmodern} \directlua{dofile('stack.lua')} \def\beforepophook{} \def\afterpophook{} \def\newstack#1{% \directlua{#1 = {}}} \def\pushstack#1#2{% \directlua{% stack.push(#1,'\luatexluaescapestring{\unexpanded{#2}}')}} \def\popstack#1{\directlua{stack.pop(#1)}} \def\printstack#1{\directlua{stack.print(#1)}} \begin{document} \newstack{mystack} \pushstack{mystack}{\foo{This is a stack test}} \pushstack{mystack}{\def\foo#1{\textbf{#1}}} \pushstack{mystack}{\begin{tabular}{cc} Foo & Bar \end{tabular}} \pushstack{mystack}{\begin{verbatim}\TeX\end{verbatim}} \printstack{mystack} \popstack{mystack} \popstack{mystack} \printstack{mystack} \popstack{mystack}{} \printstack{mystack} \popstack{mystack}{} \printstack{mystack} \end{document}  Original answer A proof of concept using luaTeX. The idea is to store the stack in a lua string. The entries of the stack are separated by the SENTINEL word. The push operation put the entry at the beginning of the stack string, so the string looks like <entry n>SENTINEL<entry n-1>SENTINEL...SENTINEL<entry 1>. The pop entry looks for the fist match of SENTINEL, passes the entry back to TeX (via tex.sprint) with the "normal" catcode regime (this is the -1 first argument given to tex.sprint) and remove the entry from the string stack (the magic number 9 is the length of the string SENTINEL plus one). The -2 first argument givent to tex.sprint in \printstack macro "detokenizes" the stack so that it can be printed "verbatim". \documentclass{article} \usepackage{lmodern} \def\beforepophook{} \def\afterpophook{} \def\newstack#1{% \directlua{#1 = ''}} \def\pushstack#1#2{% \directlua{% #1 = '\luatexluaescapestring{\unexpanded{#2}}' .. 'SENTINEL' .. #1}} \def\popstack#1{% \directlua{% local i = string.find(#1,'SENTINEL') - 1 tex.sprint(-1,'\noexpand\\beforepophook{}' .. string.sub(#1,1,i) .. '\noexpand\\afterpophook{}') #1 = string.sub(#1,i + 9)}} \def\printstack#1{% \texttt{\directlua{tex.sprint(-2,#1)}}} \begin{document} \newstack{mystack} \pushstack{mystack}{\foo{This is a stack test}} \pushstack{mystack}{\def\foo#1{\textbf{#1}}} \pushstack{mystack}{\begin{tabular}{cc} Foo & Bar \end{tabular}} \printstack{mystack} \popstack{mystack} \printstack{mystack} \popstack{mystack}{} \printstack{mystack} \popstack{mystack}{} \printstack{mystack} \end{document}  - This is rather a {proof of concept|long comment} than a real answer to the question. I'm looking forward any comments or limitations. If this proves to be interesting, I'm willing to go forward and develop it. Please note that I'm neither a TeX wizard nor a lua expert. – cjorssen Feb 27 '12 at 13:34 Why don't you use an array? – topskip Feb 27 '12 at 14:42 what happens if an antry of your stack is another stack in itself? or more precisely the content of it? – Frank Mittelbach Feb 27 '12 at 14:56 @cjorssen For sure it looks interesting it is the only solution so far that can handle verbatim. One limitation the way I see it is detecting the presence of verbatim text. Same question here as Patrick why in a string? – Yiannis Lazarides Feb 27 '12 at 18:52 @PatrickGundlach I am currently obsessed by strings... But you're right. Tables are the right type of object for that matter. I have an edited version of my answer but no internet connection right now. – cjorssen Feb 27 '12 at 22:16 \documentclass{article} \makeatletter \protected\def\newstack#1{\@ifdefinable#1{\def#1{}}} \protected\def\stackitem{% \@latexerr{Calling stack entries without popping them} {You can't directly use a stack item without popping it.}% } % #1=stack keys, #2=stacker macro \protected\def\pushstack{\@testopt\pushstack@a{}} \def\pushstack@a[#1]#2{% \def\pushstack@rescan##1##2{% \begingroup \catcode\=\string=12 \catcode\,=12 \endlinechar-1 \newlinechar-1 \catcode\@=11 \everyeof{\noexpand}% \scantokens{\gdef##2{##1}}% \endgroup }% \ifx\relax#1\relax \def\pushstack@verbstart{|}% \def\pushstack@verbend{|}% \else \pushstack@rescan{#1}\temp@b \def\temp@a##1=##2=##3\@nil{% \ifx\relax##2\relax \@latexerr{No value for key '##1'}\@ehd \else \def\reserved@a{verbstart}\def\reserved@b{##1}% \ifx\reserved@a\reserved@b \def\pushstack@verbstart{##2}% \else \def\reserved@a{verbend}% \ifx\reserved@a\reserved@b \def\pushstack@verbend{##2}% \else \@latexerr{Unknown \noexpand\pushstack key '##1'}\@ehd \fi \fi \fi }% \def\do##1,{\ifnot@nil{##1}{\temp@a##1==\@nil\do}}% \expandafter\do\temp@b,\@nil,% \fi \ifx\pushstack@verbend\@undefined \ifx\pushstack@verbstart\@undefined % Not possible: defaults would have been set up above. \else \let\pushstack@verbend\pushstack@verbstart \fi \else \ifx\pushstack@verbstart\@undefined \let\pushstack@verbstart\pushstack@verbend \fi \fi \def\stackmacro{#2}% don't do \let here. \edef\reserved@a{% \long\def\noexpand\pushstack@verbatim@a ####1\unexpanded\expandafter{\pushstack@verbend}% }% \reserved@a{\endgroup \edef#2{\unexpanded{\stackitem{##1}}\unexpanded\expandafter{#2}}% \let\pushstack@verbstart\@undefined \let\pushstack@verbend\@undefined }% \expandafter\let\expandafter\pushstack@verbstart\pushstack@verbstart \futurelet\next\pushstack@b } \def\pushstack@b{% \csname pushstack@\ifx\next\pushstack@verbstart verbatim\else normal\fi\endcsname } \long\protected\def\pushstack@normal#1{% \expandafter\edef\stackmacro{\unexpanded{\stackitem{#1}}% \unexpanded\expandafter\expandafter\expandafter{\stackmacro}}% } \long\protected\def\pushstack@verbatim#1{% \begingroup\@sanitize\@makeother\{\@makeother\}% \pushstack@verbatim@a } % #1=stack macro \protected\def\popstack#1{% \csname @\ifx#1\@empty first\else second\fi oftwo\endcsname{% \@latexerr{Cannot pop from empty stack '\string#1'} {You've attempted to pop an empty stack '\string#1'.}% }{% \expandafter\popstack@a#1\stack@stop#1% }% } % #4=macro to hold popped item \long\protected\def\popstack@a\stackitem#1#2\stack@stop#3#4{% \edef#3{\unexpanded{#2}}\edef#4{\unexpanded{#1}}% } % Examples: \newstack\mystack \pushstack\mystack{stuff} % Default sentinel for verbatim material is | (vertical bar): \pushstack\mystack|^%&*}$_|
\pushstack\mystack|\def\x#1{#1stuff}|
%\show\mystack
\pushstack[verbstart=+,verbend=+]\mystack+|^%&*}$_|+ %\show\mystack % 'verbend' will be 'verbstart': \pushstack[verbstart=+]\mystack+a|^%&*}$_|b+

% Let us try active plus (+) as sentinel for verbatim material.
% Also, let us assume that the equality sign (=) is now active. Can the
% keys still be parsed? Yes.
\begingroup
\catcode\+=13
\catcode\==13
% If you feared that + will be undefined, you could assign it \empty here.
\pushstack[verbstart=+,verbend=+]\mystack+|^^??^%&*}$^^|+ %\show\mystack \global\let\mystack\mystack \endgroup \popstack\mystack\topitem \show\topitem % should give |^^??^%&*}$^^|

\makeatother
\begin{document}
x
\end{document}


I have one practical request here: I need suggestions on optimal schemes for selecting an item by number from the (1) start and (2) end of the stack. I have my own idea but, of course, it isn't the best possible.

-