Infix to postfix conversion I have written a C++ program to convert an infix expression to postfix expression using recursion. I would like to know if it can be improved if possible. Can we improve it by not using a stack? I am using a vector&lt;char&gt; as a stack here.

#include &lt;iostream&gt;
#include &lt;vector&gt;
std::string inp;
int i, len;


std::vector&lt;char&gt; ops;
void convert()
{
    char ch = inp[i];
    if (i &gt; len)
        return;
    else if (ch == '(')
    {
        i++;
        convert();
    }
    else if (ch == ')')
    {
        std::cout &lt;&lt; ops[ops.size()-1];
        ops.pop_back();
        i++;
        convert();
    }
    else if (isdigit(ch))
    {
        i++;
        std::cout &lt;&lt; ch;
        convert();
    }
    else if ((ch == '+') || (ch == '*'))
    {
        i++;
        ops.push_back(ch);
        convert();
    }
}


int main()
{
    std::cout &lt;&lt; "Infix to postfix conversion using recursion" &lt;&lt; std::endl;
    i = 0;
    inp = "(5+5)";
    len = inp.length();
    convert();
    std::cout &lt;&lt; "\n";
    ops.clear(); i = 0;
    inp = "((5+5)*(6+6))";
    len = inp.length();
    convert();
    std::cout &lt;&lt; "\n";
    ops.clear(); i = 0;
    inp = "((4+8)*((5+5)*(6+6)))";
    len = inp.length();
    convert();
    std::cout &lt;&lt; "\n";
    return 0;
}
Don't use global variables

All your function parameters are global variables that introduce hard to track side effects. 

If you want to use the function in multiple threads in parallel it will fail.

Just pass parameters and the code becomes much more readable as well, because you clearly see which variables are needed for the function to execute.

An interface that I'd like to have would be:

std::string convertInfixExpressionToPostfix(std::string infixExpression);


All the user of this function has to care about is to give the required input and retrieve the result.

This would make your calling code much more readable as well:

std::cout &lt;&lt; convertInfixExpressionToPostfix("((5+5)*(6+6))") &lt;&lt; "\n";


Not returning the result but printing it out is another such side effect which also hinders reuse. Instead of printing the result you would accumulate it in a string and return it (as given in my proposed interface).

Of course this interface does not fit your internal needs for the recursion so you would need another implementation function which does the actual calculation and has some more parameters.

Use specialized code were advisable

You state yourself that you use the std::vector as a stack. Why not use the std::stack, which has a much clearer interface for that.

Readability

Don't put two commands on one line like this:

ops.clear(); i = 0;


It makes it too easy to overlook one of them.

Know when to use switches

Your cascading ifs would be easier to handle with a switch:

switch(ch) {
case '(': /*...*/ break;
case ')': /*...*/ break;
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9': /*...*/ break;
case '+':
case '-': /*...*/ break;
}


Eventually you would retain the if(isDigit(ch)) and leave out the digit cases.

Unnecessary variable

Your len variable just duplicates the length of the inp string. The length() method has constant time complexity so don't be afraid to use it.