Shunting Yard in C++

Stacks and Queues are data structures that organize the storage and retrieval of items. A stack is a Last-In-First-Out (LIFO) data structure, like a stack of plates on a table, while a queue is First-In-First-Out (FIFO), like a line at a movie theater. Both of these structures are used extensively in many contexts. This assignment will give you some experience working with these two data structures.

Related HackerRank Problems

C++ -> Introduction -> variable-sized-arrays

Data Structures -> Stacks -> Balanced Brackets

Data Structures -> Queues -> Truck Tour

Problem 6a : Shunting Yard Algorithm

The "Shunting yard" algorithm (https://en.wikipedia.org/wiki/Shunting-yard_algorithm) is a stack-based method to convert an in-fix expression such as ( 3 + 4 ) * 12 + 2 to postfix 3 4 + 12 * 2 +. The algorithm relies on a stack of operators (+ - * / %) to work. A simplified version of the algorithm can be stated as follows:

 Start with an empty stack of operators For each symbol S from the infix expression (read left to right) If S is an operand, add it to the output Else If S is ( push it on the stack Else If S is ) Pop until (, adding popped operators to the output Discard ( and ) Else If S is an operator While top of stack is an operator with priority >= S Pop operator from stack and add it to the output Push S Pop everything off stack, adding operators to the output 

Write a program that uses the shunting yard algorithm to convert an infix expression typed in by the user to postfix. You may assume that the expression can have numbers, parentheses, and operators (+ - * / %), separated by at least one space. Note that you are not rquired to evaluate the expression, just convert them to postfix. Use an STL stack to store the stack of operators.

Sample program run

 Enter an infix expression: ( 3 + 4 ) / ( 2 - 3 ) Postfix expression: 3 4 + 2 3 - /