我把这个作为面试问题。
堆栈上可以包含的最大元素数是多少 从中缀形式转换为反转形式的特定时刻 后缀波兰语形式？
我知道原则是，在堆栈上，在优先级较小的元素（+ 和 -）下不能有优先级较高的元素（通常是 * 和/）。我尝试制作一种跟踪全局和本地最大数量的算法，但我没有发现某个规则。
例如，如果我有infix: 2 - 3 * 4 * 5 / 1 + 10
堆栈 1：- * * / => maxLocal = 4 maxGlobal = 4
堆栈 2：（在消除/、* 和 * 之后，因为 + 的优先级较低）- +
=> maxLocal = 2 maxGlobal = 4
你能帮帮我吗？
我认为没有限制。例如，采用以下中缀表达式：
(1 + (1 + (1 + (1 + (1 + (1 + (1 + …
每次将另一个元素推送到堆栈时，它都非常深。当然，解析器接受的括号数量通常有一些限制，但这种限制纯粹是实用的（以防止堆栈溢出），而不是理论上的。