infix to postfix converter

CasperT picture CasperT · Sep 17, 2009 · Viewed 14.9k times · Source

I have been working on this infix to postfix/polis notation converter. Although, I do not feel the solution is adequate. Specifically the j (EDIT: Now called index) variable is bugging me.

Do you guys have any suggestions? Or perhaps there is a much better way to accomplish it? Or do I just worry too much?

public static string[] InfixToPostfix(string[] infixArray)
{
    var stack = new Stack<string>();
    var postfix = new string[infixArray.Length];

    int index = 0;
    string st;
    for (int i = 0; i < infixArray.Length; i++)
    {
        if (!(MyMath.MathOperators.Contains(infixArray[i])))
        {
            postfix[index] = infixArray[i];
            index++;
        }
        else
        {
            if (infixArray[i].Equals("("))
            {
                stack.Push("(");
            }
            else if (infixArray[i].Equals(")"))
            {
                st = stack.Pop();
                while (!(st.Equals("(")))
                {
                    postfix[index] = st;
                    index++;
                    st = stack.Pop();
                }
            }
            else
            {
                while (stack.Count > 0)
                {
                    st = stack.Pop();
                    if (RegnePrioritet(st) >= RegnePrioritet(infixArray[i]))
                    {
                        postfix[index] = st;
                        index++;
                    }
                    else
                    {
                        stack.Push(st);
                        break;
                    }
                }
                stack.Push(infixArray[i]);
            }
        }
    }
    while (stack.Count > 0)
    {
        postfix[index] = stack.Pop();
        index++;
    }

    return postfix.TakeWhile(item => item != null).ToArray();
}

Answer

Eric Minkes picture Eric Minkes · Sep 17, 2009

If you replace array by a Stack<string>, you don't have to keep track where you are with the index variable.

You can then return your result with postfixStack.ToArray()

My implementation:

public static string[] InfixToPostfix( string[] infixArray )
{
    var stack = new Stack<string>();
    var postfix = new Stack<string>();

    string st;
    for ( int i = 0 ; i < infixArray.Length ; i++ )
    {
        if ( !( "()*/+-".Contains( infixArray[ i ] ) ) )
        {
            postfix.Push(infixArray[i]);
        }
        else
        {
            if ( infixArray[ i ].Equals( "(" ) )
            {
                stack.Push( "(" );
            }
            else if ( infixArray[ i ].Equals( ")" ) )
            {
                st = stack.Pop();
                while ( !( st.Equals( "(" ) ) )
                {
                    postfix.Push( st );
                    st = stack.Pop();
                }
            }
            else
            {
                while ( stack.Count > 0 )
                {
                    st = stack.Pop();
                    if ( RegnePrioritet( st ) >= RegnePrioritet( infixArray[ i ] ) )
                    {
                        postfix.Push(st);
                    }
                    else
                    {
                        stack.Push( st );
                        break;
                    }
                }
                stack.Push( infixArray[ i ] );
            }
        }
    }
    while ( stack.Count > 0 )
    {
        postfix.Push(stack.Pop());
    }

    return postfix.Reverse().ToArray();
}