Can a string in infix notation be converted to prefix notation using only queues ? (consider the case where the only operations are + and -)
-
11-02-2021 - |
Question
public class Convert{
/* the algorithm works as follows after inserting all elements of infix string
into an empty Queue iterate over queue for infix.length() number of times and
check if element at front of queue is an operator if yes enque the element to
back of the queue else deque the operand and concatenate it with the empty
prefix string here is an example then finally deque the queue elements with
the prefix string*/
public static String Pre(String in){
int i = 0;
Queue Q = new Queue(in.length()); //assuming a Queue of characters
while(i<in.length()){
Q.enque(in.charAt(i));
}
i = in.length()-1;
String pre = "";
while(i>=0){ //move operators to end of queue
if(Q.peek()=='+'||'-'){ //if character is oper enque at end
Q.enque(Q.deque);}
else{
pre = pre + Q.deque;
} // concatenate operands with prefix
}
while(!Q.isEmpty) { //concatenate the operators
pre = Q.deque + pre;
}
return pre; // end of method
}
}
Solution
A "Post" Production System uses only queues. It has equivalent power to a Turing Machine.
OTHER TIPS
Given the very limited grammar you specified, to me it appears that you could convert infix to prefix using a double-ended queue. Were the grammar more complex I doubt that this approach would work.
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow