☰

使用 LaTeX 的堆栈数据结构

tag-icon • tag-icon programming
使用 LaTeX 的堆栈数据结构

一种非常常见的编程数据结构是堆栈。堆栈只是一个一维数组。堆栈元素以 LIFO（后进先出）的方式一次一个地推入或弹出堆栈。

在此处输入图片描述

我正在尝试使用 LaTeX2e 构建一个通用例程来表示此类堆栈。堆栈有两个操作：弹出和推送。

弹出的元素存储在宏中\popped@element，以便在必要时将它们推入另一个堆栈或排版材料。此时我提供了一个\before@pop@hook和一个\after@pop@hook，以便可以添加周围的材料。不确定从设计角度来看这是否正确。为了在构造中获取材料，fbox变得非常奇怪（参见第 71-72 行）：

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

我正在寻找代码的改进/修正，使其更加健壮并接受任何类型的输入，例如逐字文本，插入表格的能力，即代码的哪些部分需要变成outer等等。

到目前为止我已经想出了这个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 和 Lua 解决方案，只要它们附有详细的解释。

更新

遗憾的是，我不能接受所有的答案，因为它们都很棒，从各个方面审视了问题。我对 Frank 和 Joseph 的答案及其解释印象特别深刻。如果有人想进一步解析内容，cjorssen 的 Lua 解决方案非常有前途，而且非常有用。我接受了 Bruno 的答案，因为它带有 MWE，并且清楚地展示了在列表中使用逐字文本。

答案1

这个问题允许我们在答案中使用 TeX 宏或 Lua：我将坚持使用宏，并将 Lua 答案留给专家！我将在这里讨论的很多内容都是在 LaTeX3 模块中实现的l3seq，该模块使用“序列”进行堆栈操作。这个 LaTeX3 模块经过了多次内部修订，反映了我将尝试涵盖的一些问题。

对于真正通用的堆栈，您希望能够处理作为输入给出的任何标记。这导致两个结论：

  • 使用 e-TeX 时，使用宏进行存储是可以的，但如果解决方案只能使用 TeX 基元，则应使用 toks 作为底层存储。使用 e-TeX，我们可以使用

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

    将#标记安全地放入宏中的方法。

  • 使用“特殊”标记来划分项目

    \marker item1\marker item2\marker

    不好，因为我们不能在\marker没有括号的情况下放入任何项目。这种方法还存在在项目周围丢失括号的风险，因此不同的输入{item}和item弹出时可能会相同。相反，应该使用带有参数的宏来处理结构

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

    这在映射到堆栈时也很有用，因为您可以重新定义标记宏，使其作用于项目，而不是简单地标记其位置。（这类似于例如的\dospecials工作方式：\do是分隔符还是函数，取决于我们想要什么。）

因此，考虑到上述情况，堆栈的基本结构可以用类似的东西来实现

\newcommand{\newstack}[1]{\newcommand*{#1}{}}
\newcommand{\stack@item}[1]{\ERROR}

我们假设如果尝试直接使用堆栈条目那么就会出现错误。

在向堆栈中添加和从堆栈中删除时，您需要观察全局/本地分配。您可以采取的一种方法是使用适用于本地和全局形式的辅助函数，并将适当的信息作为参数从主宏传递。我将坚持只进行本地分配：例如，请参阅l3seq如何将其概括为本地分配。

\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}%
}

然后，您可以想象添加更多功能，例如映射、可扩展的“顶部”功能、从堆栈末尾按数字选择项目等等。这些都是可行的（再次查看l3seq一些想法）。

答案2

Joseph 已经在他的回答中提到了这一点，但我认为值得突出指出的是，LaTeX3 编程语言中的解决方案expl3是seq模块。

您可以通过运行来访问其文档

latex l3seq.dtx

或作为完整编程接口文档的一部分interface3.tex。

它不仅提供一组堆栈操作（如获取、推送、弹出），还提供对序列和堆栈的更一般的操作，例如在左侧或右侧添加、在序列上映射代码以依次应用于每个项目、各种条件（包括检查序列内的数据）等。

但它无法管理逐字材料。事实上，如果要动态地进行 catcode 操作，那么任何地方都没有合适的解决方案。如果您想要这样做，那么您需要完全分离输入层，在那里识别您的逐字材料，将其转换为 TeX 引擎内部可以安全处理的内容，然后才开始将其组装成要传递给堆栈操作等函数的参数。

答案3

这个答案侧重于“逐字”方面，几乎完全忽略了堆栈的细节。我们只\l_foo_seq使用 来操作一个堆栈expl3。当然，这可以推广到多个堆栈。

为了使逐字翻译能够正常工作，必须在 TeX 开始读取材料之前告知它忽略所有类别代码。下面的代码定义了

  • \push{...}添加...到堆栈中，作为正常参数读取。
  • \push|...|使用任意一对相同的分隔符来读取...逐字材料并将其添加到堆栈中。
  • \popto删除顶部项目并对其进行排版，使用捕获该项目时有效的类别代码。
  • \popto[\result]存储该项目\result而不是排版它。
  • \popto*\scantokens使用当前类别代码（在后台使用）排版项目。
  • \popto*[\result]\result将类别代码更改为当前代码后将项目存储在。

代码如下。

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

答案4

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

我这里有一个实际请求：我需要一些关于从 (1) 堆栈的开头和 (2) 末尾按数字选择项目的最佳方案的建议。我有自己的想法，但当然，这不是最好的。

相关内容