What is the running time of the translation of inf

问题:

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.

回答1:

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.

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).

Converting from postfix to infix can similarly be shown to run in O(n) time using a argument like the one above.

Hope this helps!