title: Infix to Prefix Conversion using Recursion
body: <p>I am struggling to find the infix to prefix translation scheme.</p>
  
  <p><strong>I have figured the infix to postfix translation sceme :</strong></p>
  
  <pre><code>expr -&gt; Term, Rest
  Rest -&gt; +Term, { print('+') } , Rest | -Term, { print('-') }, Rest | epsilon
  Term -&gt; Factor, Rest_
  Rest_ -&gt; *Factor, { print('*') }, Rest_ | /Factor, { print('/') }, Rest_ | epsilon
  Factor -&gt; Digit | (expr)
  Digit -&gt; 0,1,2,3,4,5,6,7,8,9
  </code></pre>
  
  <p><strong>And my infix to postfix conversion code according to the above translation scheme :</strong></p>
  
  <pre><code>#include&lt;iostream&gt;
  
  using namespace std;
  
  const char input[] = "9-5*2";
  int index = 0;
  char LookAhead = input[index];
  
  void Match(char newChar);
  void Factor();
  void Rest_();
  void Rest();
  void Term();
  void Expression();
  
  
  int main(){
      Expression();
      return 0;
  }
  
  void Match(char newChar){
      if(newChar == LookAhead){
          index++;
          LookAhead = input[index];
      }
  }
  
  void Expression(){
      Term();
      Rest();
  }
  
  void Term(){
      Factor();
      Rest_();
  }
  
  void Rest(){
      if(LookAhead == '+'){
          Match('+');
          Term();
          cout &lt;&lt; '+';
          Rest();
      }else if(LookAhead == '-'){
          Match('-');
          Term();
          cout &lt;&lt; '-';
          Rest();
      }else{
  
      }
  }
  
  void Rest_(){
      if(LookAhead == '*'){
          Match('*');
          Factor();
          cout &lt;&lt; '*';
          Rest_();
      }else if(LookAhead == '/'){
          Match('/');
          Factor();
          cout &lt;&lt; '/';
          Rest_();
      }else{
  
      }
  }
  
  void Factor(){
      if(isdigit(LookAhead)){
          cout &lt;&lt; LookAhead;
          Match(LookAhead);
      }
  }
  </code></pre>
  
  <p>So now is there any experts who can help me to understand with the infix to prefix conversion translation scheme, it will be appreciated.</p>
  
  <p>We can test through parse tree. If we can generate something like <strong>-9+52</strong> prefix string from example string <strong>9-5+2</strong> .</p>
  
  <p><em>Tell me if i need to explain more about my infix to postfix conversion translation scheme and code to get better understanding.</em></p>
  
  <p>Thanks in Advance !</p>
  
  <p><strong>Edited :</strong>
  simply I am having a problem finding out the infix to prefix expression conversion translation scheme. As an example,
  My input :</p>
  
  <pre><code>9-5+2
  </code></pre>
  
  <p>Expected Output :</p>
  
  <pre><code>-9+52
  </code></pre>
  
  <p>And I want to achieve this with the same structure I have shown above with infix to postfix conversion.
  That is all !</p>