有著名的shunting-yard algorithm可用于将中缀表达式(例如 1 + 2 * 3)转换为后缀表达式(例如 1 2 2 * +)。调车场算法需要一个栈来存储即将移动的元素。
是否可以预先估计在线性时间和常量内存中将特定输入转换为其后缀形式所需的堆栈长度？
最佳答案
当然。 shunting-yard algorithm仅将运算符(包括括号)压入堆栈，因此一阶近似值是表达式中运算符的数量。有了更多的智能，您可以扫描表达式并寻找关联性和分组。但是当你完成时，你可能已经编写了一个基于堆栈的算法来确定表达式所需堆栈大小的最佳估计，并且会使你的执行成本翻倍。
关于algorithm - 如何估计将中缀表达式转换为后缀表达式所需的堆栈空间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15372432/