Можно ли преобразовать строку в инфиксной нотации в префиксную нотацию, используя только очереди?(рассмотрим случай, когда единственными операциями являются + и -)

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
    }
}

Answer 1

A " Post " Production System использует только очереди.Он имеет эквивалентную мощность для машины Тьюринга.

Answer 2

Учитывая очень ограниченную грамматику, которую вы указали, мне кажется, что вы можете конвертировать инфикс в префикс, используя двустороннюю очередь. Если бы грамматика была более сложной, я сомневаюсь, что этот подход сработает.