需要创建缀以后缀算法

Question

我需要实现缀到后缀转换算法来计算表达式a + b *的CD/E

我还需要做到这一点使用队列（我相信2个不同的队列堆栈是需要）

我使用DoubleLinkList创建了队列类，现在只需要创建这个问题的算法。尽管如此，但我对于如何解决这个问题却很失落。任何帮助，将不胜感激！

至今（我知道这是非常错误的），我有：

string infix = "a+b*c-d/e"; 
    Queue *holder = new Queue(); 
    Queue *newstring = new Queue(); 
    int length = infix.length(); 
    char temp; 
    char prev; 
    for(int i=0; i<length; i++) 
    { 
     temp = infix[i]; 
     if((temp == '+') || (temp == '-') || (temp == '*') || (temp == '/')) 
     { 
      if (holder->isEmpty()) 
      { 
       holder->queue(temp); 
      } 
      if(temp<holder.enqueue()) 
      { 

      } 
     } 
     holder->queue(temp); 

    } 

Answer 1

我想这是一个家庭作业，让你找出你自己的编程细节是非常重要的。该算法的大纲如下：

Define a stack 
Go through each character in the string 
If it is between 0 to 9, append it to output string. 
If it is left brace push to stack 
If it is operator *+-/ then 
      If the stack is empty push it to the stack 
      If the stack is not empty then start a loop: 
          If the top of the stack has higher precedence 
          Then pop and append to output string 
          Else break 
        Push to the stack 

If it is right brace then 
      While stack not empty and top not equal to left brace 
      Pop from stack and append to output string 
      Finally pop out the left brace. 

If there is any input in the stack pop and append to the output string. 

Answer 2

我认为你应该创建一个操作符和值的树。
您可以根据树的遍历顺序从中缀转换为前缀。
你的导师可能会给你三个之间的转换任务。

这里有一些文章：
University of Texas
YouTube video
Wikipedia - Expression trees