title: Prefix to Postfix conversion with parentheses
body: <p>I am really stuck in make conversion of special prefix to postfix operation on our task, let me describe the task similarly :</p>
  
  <p>We have such operation to use as operations in our prefixes, here is the method that i am checking them :</p>
  
  <pre><code>bool isOperator(string c)
  {
      if (c == "log" || c == "exp" || c == "sum" || c == "div" || c == "abs" || c == "sqrt" || c == "sub" || c == "product" || c == "max" || c== "min" || c == "mod" )     // you may add operator here
          return true;
      return false;
  }
  </code></pre>
  
  <p>Anyway example prefix instructions can have parentheses to make operation precedence, this is what I am stuck at. I know, I need to implement such a recursion, but i can't find a way.</p>
  
  <pre><code>div ( sqrt 5 ) 3
  </code></pre>
  
  <p>Output should be </p>
  
  <pre><code>5 sqrt 3 div
  </code></pre>
  
  <p>Another example :</p>
  
  <pre><code>div ( sum ( exp 2 3 ) ( sqrt 5 ) ) 3
  </code></pre>
  
  <p>Output </p>
  
  <pre><code>2 3 exp 5 sqrt sum 3 div
  </code></pre>
  
  <p>Every operation, parentheses or number should have space between elements in assumed condition.</p>
  
  <p>My stack implementation</p>
  
  <p>Stack.h</p>
  
  <pre><code>#include&lt;iostream&gt;
  using namespace std;
  
  struct node {
      string op ;
      node *next;
  };
  
  struct Stack {
      node * head;
      void create();
      void close();
      void push (node *);
      node* pop();
      node* top();
      bool isEmpty();
  
  };
  </code></pre>
  
  <p>Stack.cpp</p>
  
  <pre><code>#define _CRT_SECURE_NO_WARNINGS
  #include "stack.h"
  #include &lt;iostream&gt;
  #include &lt;stdlib.h&gt;
  
  void Stack::create() {
      head = NULL;
  }
  
  void Stack::close() {
      node *p;
      while (head) {
          p = head;
          head = head-&gt;next;
          //delete [] p-&gt;data;
          delete p;
      }
  }
  
  void Stack::push(node *newdata) {
      node *newnode = new node;
      newnode = newdata;
      newnode-&gt;op = newdata-&gt;op;
      newnode-&gt;next = head;
      head = newnode;
  }
  
  node *Stack::pop() {
      if (isEmpty())
          return NULL;
      node *topnode = head;
      head = head-&gt;next;
      //delete topnode;
      return topnode;
  }
  
  node *Stack::top() {
      if (isEmpty())
          return NULL;
      node *topnode = head;
      //delete topnode;
      return topnode;
  }
  bool Stack::isEmpty() {
      return (head == NULL);
  }
  </code></pre>
  
  <p>as @PaulMcKenzie mentioned, i've tried an implementation below, sub_array string array contains the word list without spaces.</p>
  
  <pre><code>bool isLeftParanthesis(string c)
  {
      if (c == "(" )   // you may add operator here
          return true;
      return false;
  }
  bool isRightParanthesis(string c)
  {
      if (c == ")")    // you may add operator here
          return true;
      return false;
  }
  int main()
  {
  string prefix;
  getline(cin, prefix);
  istringstream iss(prefix);
  istringstream iss2(prefix);
  int count1 = 0, count2 = 0;
  string postfix = "";
  Stack *st = new Stack;
  string t1, t2;
  
  string sub;
  string *sub_array;
  while (iss &gt;&gt; sub) {
      count1++;
  }
  sub_array = new string[count1];
  while (iss2 &gt;&gt; sub) {
      sub_array[count2] = sub;
      count2++;
  }
  int l = count1;
  
  int right_p_count = 0;
  for (int i = 0; i &lt; count1; i++)
  {
      if (isRightParanthesis(sub_array[i]))
      {
          right_p_count++;
      }
  }
  string *postfixes = new string[right_p_count];
  int index_right_p = 0;
  for (int i = 0; i &lt; count1; i++) {
      while (!isRightParanthesis(sub_array[i]))
      {
          node *n = new node;
          n-&gt;op = sub_array[i];
          st-&gt;push(n);
          i++;
          if (i == count1)
          {
              break;
          }
      }
      if( i != count1){
      if (isRightParanthesis(sub_array[i])) {
          postfix = "";
          while (!isLeftParanthesis(st-&gt;top()-&gt;op))
          {
              string t = st-&gt;pop();
              if (!isOperator(t) &amp;&amp; !isLeftParanthesis(t) &amp;&amp; !isRightParanthesis(t)) {
                  postfix = t + " " + postfix;
              }
              else if (isOperator(t)) {
                  postfix = postfix + " " + t;
              }
          }
          st-&gt;pop();
          postfixes[index_right_p] = postfix;
          index_right_p++;
      }
      }
      postfix = "";
      while ( !st-&gt;isEmpty() &amp;&amp; index_right_p == right_p_count &amp;&amp; i == count1)
      {
          string t = st-&gt;pop();
          if (!isOperator(t) &amp;&amp; !isLeftParanthesis(t) &amp;&amp; !isRightParanthesis(t)) {
              postfix = t+" "+postfix;
          }
          else if (isOperator(t)) {
              postfix = postfix+""+t;
          }
          else {
              break;
          }
      }
  }
  
  string result = "";
  for (int i = 0; i &lt; right_p_count; i++)
  {
      result = result + "" + postfixes[i];
  }
  result = result + " " + postfix;
  cout &lt;&lt; result &lt;&lt; endl;
  }
  </code></pre>
  
  <p>Variable postfix refers to output postfix, but my output is not wrong for some of the operations such as :</p>
  
  <pre><code>div ( sqrt 5 ) 3
  </code></pre>
  
  <p>When i saw a parantheses i am checking if it is left or right, using right one for trigger.</p>
  
  <pre><code>abs ( product -2 -4 -8 )
  </code></pre>
  
  <p>Expected output is :</p>
  
  <pre><code>-2 -4 -8 product abs
  </code></pre>
  
  <p>UPDATE : I solved stack problem myself, but found out that, algorithm calculates some expressions wrongly...</p>
  
  <p>Example expression :</p>
  
  <pre><code>3 2 3 exp sum
  </code></pre>
  
  <p>Expected output :</p>
  
  <pre><code>sum 3 ( exp 2 3 )
  </code></pre>
  
  <p>My output :</p>
  
  <pre><code>2 3 exp 3 sum
  </code></pre>
  
  <p>My algorithm which is using right parentheses as triggers calculates it wrongly and I don't know how to implement this control into that, are there any suggestions ?</p>