Stack datastructure using LaTeX

Question

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
\newcommand{\add@element}[2]{%
  \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}
\add@element{\stack}{english}
\add@element{\stack}{polish}
\add@element{\stack}{australian}
\add@element{\stack}{german}
\add@element{\stack}{\elt@start greek \elt@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}
\add@element{\tempstack}{\popped@element}
\parbox{3cm}{\popped@element@}


\def\X{german}
\def\Y{\popped@element}
\ifx\X\Y \add@element{\stack}{\popped@element}\fi

In temp stack \tempstack

\def\before@pop@hook{}
\def\after@pop@hook{}
\add@element\stack{\lorem}

\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.

Answer 1

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{\newstack}[1]{\newcommand*{#1}{}}
\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).

Answer 2

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.

Answer 3

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}

Answer 4

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}

Answer 5

\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.