56021

What is the running time of the translation of infix to postfix using queue and stack?

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.

Answer1:

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:

    <li>Every number is pushed exactly once and popped exactly once.</li> <li>Every operator is pushed exactly once and popped exactly once.</li> <li>Every token is dequeued from the queue of tokens exactly once.</li> <li>Every intermediate result is pushed exactly once and popped exactly once.</li> </ul>

    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!

Recommend

  • Computing estimated times of file copies / movements?
  • C# how to pass unknown value variable ( user input ) to return method
  • Oracle AQ dequeue order
  • UIButton image for normal state in collectionview cell repeats itself every four cells
  • Use of \\b Boundary Matcher In Java
  • sed statement to change/modify CSV separators and delimiters
  • Finding the shortest path with possibility of ignoring 1(the longest) edge
  • Is there better way than a Dijkstra algorithm for finding fastest path that do not exceed specified
  • Find the shortest path between a given source and a set of destinations
  • Lua userdata: Unable to have simultaneous array access and methods
  • Custom Title View not Centered in iOS 10
  • Google Maps API v3 javascript Markers don't always load
  • Way to represent unknown file size in FTP LIST?
  • How can I migrate my WP8 application to universal when it uses a local linq to sql db?
  • pthread_create memory leak
  • Using RegEx in View
  • All shortest paths for weighted graphs with networkx?
  • How to enumerate Azure subscriptions and tenants programmatically?
  • Property 'catch' does not exist on type 'PromiseLike
  • Overflow: hidden but i still want to have the empty scrollbar
  • AntiForgery Token implementation in Angular 2 and Web Api using Aps.Net Core
  • Task.IsCancelled doesn't work
  • Success handler not working after Symfony2 login
  • Migration tool for ANTLR grammar
  • Converting raw frames into webm live stream
  • Time taken for Hadoop job to execute
  • IDX10503: Signature validation failed
  • oauth2client.client.HttpAccessTokenRefreshError: invalid_grant: Invalid JWT
  • Syntax error near unexpected token 'elif'
  • Regex for nested values
  • How gzip file gets stored in HDFS
  • read values from form post in jquery or javascript
  • cordova is not defined - cordova.js has already been loaded :: Ionic
  • jQuery: add elements until a particular height is reached
  • Combining two different ActiveRecord collections into one
  • How to use carriage return with multiple line?
  • Time complexity of a program which involves multiple variables
  • one Local Olampyad Questions on Informatic in 2011
  • Python: how to group similar lists together in a list of lists?
  • Django query for large number of relationships