title: Shunting-yard algorithm in c++
body: <p>I need a function that takes an infix string (like "3 + 4 * 9"), and convert it to postfix (like "4 9 * 3 +").</p>
  
  <p>I got it working until you throw in parentheses within parentheses. I've been working on it all day and can't figure out what I'm doing wrong- can someone with a fresh mind see it, maybe? I feel like I'm really close!</p>
  
  <p>Thanks! Here's the code:</p>
  
  <pre><code>    string ExpressionManager::infixToPostfix(string infixExpression)
      {
  cout &lt;&lt; "itop Testing : " &lt;&lt; infixExpression &lt;&lt; endl;
  string posnums = "0123456789";
  string posops = "+-*/%(){}[]";
  string onlyops = "+-/%*";
  string space = " ";
  string openbra = "([{";
  string closebra = ")]}";
  stack &lt;string&gt; nums;
  stack &lt;string&gt; ops;
  string output = "";
  
  //check to make sure expression is valid
  
  if (!(isBalanced(infixExpression)))
  {
      cout &lt;&lt; "Infix Expression isn't balanced!" &lt;&lt; endl;
      return "invalid";
  }
  
  
  for (int i=0; i&lt;infixExpression.size(); i++)
  {
      if ((posnums.find(infixExpression[i])!=string::npos) || (posops.find(infixExpression[i])!=string::npos) || (space.find(infixExpression[i])!=string::npos))
      {}
  
      else
      {
          cout &lt;&lt; "Invalid character " &lt;&lt; infixExpression[i] &lt;&lt; " found." &lt;&lt; endl;
          return "invalid";
      }
  }
  
  
  int numcount = 0;
  int opcount = 0;
  //Numbers vs. Operators
  for (int i = 0; i &lt; infixExpression.size(); i++)
  {
      if (posnums.find(infixExpression[i]) != -1)
      {
  
          while(infixExpression[i] != ' ')
          {
              if (i == (infixExpression.size()-1))
                  break;
              i++;
          }
          numcount++;
      }
  
      if (onlyops.find(infixExpression[i]) != -1)
      {
          opcount++;
      }
  }
  
  
  if (opcount == (numcount - 1))
  {
  }
  else
  {
      cout &lt;&lt; "Bad operators to numbers ratio!" &lt;&lt; endl;
      return "invalid";
  }
  
  //Get rid of proceeding whitespaces.
  int safety = 0;
  int net = infixExpression.size();
  
  while (infixExpression[0] == ' ')
  {
      infixExpression.erase(0,1);
      safety++;
  
      if (safety&gt;=net)
          break;
  }
  
  //cout &lt;&lt; "At this point, it is " &lt;&lt; postfixExpression &lt;&lt; endl;
  
  //the fun part! Set up stacks
  
  for (int i =0; i&lt; infixExpression.size(); i++)
  {
      cout &lt;&lt; "It gets hung up on character " &lt;&lt; infixExpression[i] &lt;&lt; endl;
      if(openbra.find(infixExpression[i]) != -1)
      {
  
          string word = "";
          word += infixExpression[i];
          ops.push(word);
  
          cout &lt;&lt; "Pushing onto stack: " &lt;&lt; word &lt;&lt; endl;
      }
      else if(closebra.find(infixExpression[i]) != -1)
      {
              cout &lt;&lt; "contents of remaining ops stack: "&lt;&lt; endl;
              stack &lt;string&gt; temp;
              temp = ops;
                  for (int j = 0; j &lt; temp.size(); j++)
                  {
                      cout &lt;&lt; "\t" &lt;&lt; temp.top() &lt;&lt; endl;
                      temp.pop();
                  }
  
          while (openbra.find(ops.top()) == -1)
          {
  
  
              output += " " + ops.top();
              cout &lt;&lt; "Pushing from stack: " &lt;&lt; ops.top() &lt;&lt; endl;
              ops.pop();
          }
  
          cout &lt;&lt; "Pushing from stack: " &lt;&lt; ops.top() &lt;&lt; endl;
          ops.pop();
  
      }
  
      else if (posnums.find(infixExpression[i]) != -1)
      {
  
          string word = "";
          while (infixExpression[i] != ' ')
          {
              word += infixExpression[i];
              i++;
              if (i== infixExpression.size())
                  break;
          }
          output += " " + word;
  
      }
  
      else if (onlyops.find(infixExpression[i]) != -1)
      {
  
          if (ops.size() == 0)
          {
              string word = "";
          word += infixExpression[i];
          ops.push(word);
          }
          else
          {
          int o1p = 0;
          int o2p = 0;
  
          if ((infixExpression[i] == '+') || (infixExpression[i] == '-'))
              o1p = 0;
          else
              o1p = 1;
  
          if ((ops.top() == "+") || (ops.top() == "-"))
              o2p = 0;
          else
              o2p = 1;
  
          while ((ops.size() &gt; 0) &amp;&amp; (o1p &lt;= o2p))
          {
              output += " " + ops.top();
              cout &lt;&lt; "(odd) Pushing from stack: " &lt;&lt; ops.top() &lt;&lt; endl;
  
          if ((ops.top() == "+") || (ops.top() == "-"))
              o2p = 0;
          else
              o2p = 1;
  
          if (ops.size() &gt; 0)
          {
              ops.pop();
          }
          else
          {
              break;
          }
          }
  
          string word = "";
          word += infixExpression[i];
          ops.push(word);
          }
      }
  
  }
  
  while (output[0] == ' ')
  {
      output.erase(0,1);
  }
  
  return output;
      }
  </code></pre>