Tuesday, July 14, 2009

C++ Shunting_yard_algorithm?

The only prog. i can find is for c but i need the code for C++ i know c code will work on c++ but i dont understand c





The objective is to implement an infix to


postfix RPN notation converter using a stack. There is a good description of the shunting yard


algorithm described by Edsgar Dijkstra at http://en.wikipedia.org/wiki/Shunting_ya...


There is an example of the algorithm in the link. The infix notation string should be entered through standard input and the


postfix notation conversion displayed on standard output.


The stack used in this project should be written as a class and using a linked list to implement the


stack data structure.

C++ Shunting_yard_algorithm?
I have written this program in Java, it is not that different from C or C++, there is an algorithm for converting:


Scan the Infix string from left to right.


1- Initialise an empty stack.


2- If the scannned character is an operand, add it to the Postfix string. If the scanned character is an operator and if the stack is empty Push the character to stack.





3- If the scanned character is an Operand and the stack is not empty, compare the precedence of the character with the element on top of the stack (topStack). If topStack has higher precedence over the scanned character Pop the stack else Push the scanned character to stack. Repeat this step as long as stack is not empty and topStack has precedence over the character.


Repeat this step till all the characters are scanned.





4- (After all characters are scanned, we have to add any character that the stack may have to the Postfix string.) If stack is not empty add topStack to Postfix string and Pop the stack. Repeat this step as long as stack is not empty.





5- Return the Postfix string.





Check out:


http://scriptasylum.com/tutorials/infix_...


for more details, i copied and pasted the algorithm from this site, there are also some examples there.





The Java code is too long to send it here, if u want it, e-mail me and i will send it.





Good luck


Bye

plum

No comments:

Post a Comment