Infix to postfix conversion

Question

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<char> as a stack here.

#include <iostream>
#include <vector>
std::string inp;
int i, len;


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


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

Answer 1

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 << convertInfixExpressionToPostfix("((5+5)*(6+6))") << "\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.

Answer 2

The answer from @Nobody covers most of the important things, but there are a few others that may be useful to you. First, I'd absolutely agree that the global variables must go. There are two obvious ways to do so. One would be to create an object which would both contain the variables that are now global and have the associated behavior. The other way to do it would be to pass in the needed variables. That approach might look like this:

void convert(const std::string &inp, unsigned i, std::vector<char> &ops, std::string &out)
{
    if (i > inp.length())
        return;
    char ch = inp[i];
    if (ch == '(')
    {
        convert(inp, ++i, ops, out);
    }
    else if (ch == ')')
    {
        out.push_back(ops.back());
        ops.pop_back();
        convert(inp, ++i, ops, out);
    }
    else if (isdigit(ch))
    {
        out.push_back(ch);
        convert(inp, ++i, ops, out);
    }
    else if ((ch == '+') || (ch == '*'))
    {
        ops.push_back(ch);
        convert(inp, ++i, ops, out);
    }
}

std::string convert(const std::string inp)
{
    std::vector<char> ops;
    std::string result;
    convert(inp, 0, ops, result);
    return result;
}

Note a few other changes. First, there are now two convert routines. One which is the recursive version takes four arguments. The other is the "top level" version that takes a single argument, which is the string to be converted. The top-level convert also returns a string which contains the converted result.

This code also uses ops.back() to refer to the last element of ops rather than using ops[ops.size()-1] which is a little less obvious. It increments i within each call to convert to make the consistency easier to see, and uses a std::string out for the output rather than printing directly to std::cout.

A more subtle rewrite is that the original code had this:

char ch = inp[i];
if (i > len) 

But if i > len, ch will just have accessed beyond the end of the string. That's not good and easily avoided by simply checking the range first and then using it.

Finally, you may want to think about how one might add additional operators and multi-digit numbers. Both of these changes would require some changes to how the code currently operates. More fundamentally, consider changing the code to be able to handle expressions without parentheses, and to account for operator precedence. As two examples that are not handled by the code right now, consider:

4+8       ==>  48+
4+8*3     ==>  483*+