Time complexity of prefix to postfix conversion?

Question

I think it should be quadratic i.e O(n^2). I am reading from this source prefix to postfix . I assume that appending two string takes linear time (O(sum of size of the two strings which we are appending)) and maximum number of times we need to append can go upto O(n) and thus overall complexity is O(n^2). Can some one tell if i am wrong and can some one provide better proof of this ?

Answer 1

Yes, you're right that it's O(n²), and I think your proof is OK, but that depends who you have to prove it to. Maybe show explicitly how to construct a string that would result in O(n) appends of O(n) size.

Here's a simple recursive version that does the job in O(n):

static String preToPost(String src)
{
    StringBuilder dest = new StringBuilder(src.length());
    for(int pos=0; pos < src.length(); pos = preToPost(dest, src, pos));
    return dest.toString();
}
// Convert one prefix expression to postfix.  Returns
// end position
static int preToPost(StringBuilder dest, String src, int pos)
{
    if (pos >= src.length())
    {
        //no expression
        return pos;
    }
    char c = src.charAt(pos++);
    if ("+-/*".indexOf(c)>=0)
    {
        //operator. Convert both operands first
        pos = preToPost(dest, src, pos);
        pos = preToPost(dest, src, pos);
    }
    dest.append(c);
    return pos;
}

The iterative version is not much more complicated:

static String preToPost2(String src)
{
    StringBuilder dest = new StringBuilder(src.length());
    int pos=0;

    Stack<Character> stk = new Stack<>();
    while(pos < src.length())
    {
        char c = src.charAt(pos++);
        if ("+-/*".indexOf(c)>=0)
        {
            //operator.  After the next 2 expressions, put c
            stk.push(c);
            //after the next expression, just do another one
            stk.push('\0');
            continue;
        }
        dest.append(c);
        // done expression.  check the todo stack
        while(!stk.empty())
        {
            c = stk.pop();
            if (c=='\0')
            {
                break;
            }
            dest.append(c);
            // the append completed another expression, so loop
            // to check the todo stack again
        }
    }
    return dest.toString();
}

This is a direct conversion of the recursive one.