使用队列和堆栈将中缀转换为后缀的运行时间是多少？ [英] What is the running time of the translation of infix to postfix using queue and stack?
问题描述
在c ++中...
我知道队列和堆栈的各个功能的时间复杂度，但是我不知道同时使用队列和堆栈的infixToPostfix函数的时间复杂度是多少。 ..我当然是一名初学者程序员，我非常困惑。
In c++... I know the time complexities for the individual functions of queue and stack, but I don't know what the time complexity for an infixToPostfix function would be, using both queue and stack....I am a beginner programmer of course, and I am very confused.
推荐答案
使用堆栈和我认为队列是 Dijkstra的调车场算法。衡量复杂性的一种方法是考虑完成了多少次推送和弹出：
Converting from infix to postfix using a stack and a queue is, I assume, Dijkstra's shunting-yard algorithm. One way to measure the complexity is to think about how many pushes and pops are done:
- 每个数字只被推送一次并被弹出一次。
- 每个运算符只被推一次并恰好弹出一次。
- 每个令牌都只从令牌队列中出队一次。
- 每个中间结果仅被推送一次，并被弹出一次。
- Every number is pushed exactly once and popped exactly once.
- Every operator is pushed exactly once and popped exactly once.
- Every token is dequeued from the queue of tokens exactly once.
- Every intermediate result is pushed exactly once and popped exactly once.
如果您的字符串长度为n，则它具有O（n）个数字和O（n）个运算符，因此，这三个组中前三个组的总工作量为O（n）。要分析最后一组，请注意，每个中间值都来自两个早期值的组合。如果原始输入中总共有O（n）个数字，则意味着可以作为中介产生O（n）个值。因此，总运行时间为O（n）。
If your string has length n, then it has O(n) numbers and O(n) operators, so the amount of work done by the first three of these groups in total would be O(n). To analyze the last group, note that each intermediate value comes from combining together two earlier values. If there are a total of O(n) numbers in the original input, this means that there can be O(n) values produced as intermediaries. Therefore, the total runtime would be O(n).
使用类似一个参数，可以类似地显示从后缀转换为中缀可以在O（n）时间运行
Converting from postfix to infix can similarly be shown to run in O(n) time using a argument like the one above.
希望这会有所帮助！
这篇关于使用队列和堆栈将中缀转换为后缀的运行时间是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
