在 C++ 中... 我知道队列和堆栈的各个函数的时间复杂度，但我不知道同时使用队列和堆栈的 infixToPostfix 函数的时间复杂度是多少......我当然是一名初学者程序员，而且我我很困惑。
最佳答案
我认为使用堆栈和队列从中缀转换为后缀是 Dijkstra's shunting-yard algorithm 。衡量复杂性的一种方法是考虑完成了多少次推送和弹出操作:
- 每个数字都只推送一次并弹出一次。
- 每个运算符都只推送一次并弹出一次。
- 每个 token 仅从 token 队列中出队一次。
- 每个中间结果都只推送一次并弹出一次。
如果字符串长度为 n，则它有 O(n) 个数字和 O(n) 个运算符，因此前三组完成的工作量总共为 O(n)。要分析最后一组，请注意每个中间值都来自将两个较早的值组合在一起。如果原始输入中总共有 O(n) 个数字，这意味着可以产生 O(n) 个值作为中介。因此，总运行时间将为 O(n)。
使用像上面这样的参数，从后缀到中缀的转换可以类似地在 O(n) 时间内运行。
希望这有帮助!
关于c++ - 使用队列和堆栈将中缀转换为后缀的运行时间是多少？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5305215/