栈式状态模拟

栈、单调栈与单调队列 · HTML

数学 / 逻辑形态

从左到右读取 token。每个 token 触发 push、pop、reduce 或修改栈顶；栈内容是处理当前前缀后仍会影响未来的最小上下文集合。

识别信号

• 结构具有嵌套、最近开启先关闭的 LIFO 关系。
• 操作语义包含 undo、back、return 或 collapse。
• 递归调用可用显式 frame 模拟。
• 读取新 token 时只需查看最近未完成上下文。

容易误判的相似信号

核心不变量

处理完输入前缀后，栈自底向上按开启顺序保存所有尚未完成的上下文；栈顶是下一 token 唯一可直接影响的最近上下文。

状态、转移与处理顺序

Python 骨架

def normalize_path(parts):
    stack = []
    for part in parts:
        if part in ('', '.'):
            continue
        if part == '..':
            if stack:
                stack.pop()
        else:
            stack.append(part)
    return '/' + '/'.join(stack)

正确性思路

1. 普通片段被追加为当前最深上下文，保持原顺序。
2. 父级操作只撤销最近一个仍有效片段，LIFO 正好匹配语义。
3. 归纳处理所有 token 后，栈恰含未被撤销的规范路径片段。

复杂度

边界条件

• 空输入产生基础状态。
• 在根级继续 pop 必须按语义忽略或报错。
• 连续多个开启/关闭会达到最大深度。
• 结束时栈非空可能是合法未归约结果，也可能表示输入不完整，取决于协议。

错误模式

选择与排除规则

• 最近开启必须最先结束：栈。
• 只是匹配定界符：用专用 balanced 模板。
• 需要优先弹出最大/最小候选：不是普通状态栈，考虑堆或单调结构。

相关模板

原创微型例子

Recall prompts

• 栈中应保存历史全部数据还是未来所需摘要？
• 为什么最近开启的上下文必须先关闭？
• 如何从递归函数参数设计显式 frame？

我的补充