有著名的调车码算法可用于将中缀表达式（例如1 + 2 * 3）转换为后缀表达式（例如1 2 2 * +）。调车场算法需要一个堆栈来存储即将被移动的元素。
是否可以预先估计在线性时间和恒定内存中将特定输入转换为其后缀形式所需的堆栈长度？
问问题
167 次
2 回答
3
当然。分流场算法仅将运算符（包括括号）压入堆栈，因此一阶近似值是表达式中运算符的数量。有了更多的智能，您可以扫描表达式并寻找关联性和分组。但是当你完成时，你可能已经编写了一个基于堆栈的算法来确定表达式所需的堆栈大小的最佳估计，并且会使你的执行成本翻倍。
于 2013-03-12T21:41:14.160 回答
0
在旧的 HP-45 计算器上，我们总是扫描嵌套最深的括号，然后从那里开始计算。这应该是输入中 N 个标记的快速 O(N) 算法。
在实践中，要创建一个能够炸毁 HP-45 的 4 高堆栈的表达式是一项挑战。
于 2013-03-12T21:52:42.647 回答