Another Postfix (RPN) to Infix convertor

Introduction 

I wanted a general infix to RPN convertor so I could use with \psplot in latex. I am using the Shunting yard algorithm.

Using the code  

The fist thing I did was to modify the input string with. This removes all spaces then inserts multiplications between parentheses. 

private string FixInputstring(string InfixNotation)
{           
    InfixNotation = InfixNotation.ToLower().Replace(" ", 
           "").Replace(")(", ")*(");

Next I needed to insert multiplication symbols between any digit and any letter.

For example: 3x^2y needs to bo 3*x^2*y

for (int i = 0; i < list.Length; i++)
{
    for (int j = 0; j < 10; j++)
    {
        string find = j.ToString() + r[i];
        string replace = j.ToString() + "*" + r[i];
        InfixNotation = InfixNotation.Replace(find, replace);
    }
}

I use the modified string to create the tokens for the RPN algorithm. 

The  flow goes like this:

1. Is the character a number - yes -extract it
2. Is the character an Operation or reserved function
3. Is the character a variable? if yes was the previous one a variable?

Step 1

if ((System.Char.IsNumber(ModifiedInfixNotation[CurrentPosition]))||
    (ModifiedInfixNotation[CurrentPosition]=='.'))
{
    int NumberStart = CurrentPosition;
    while ((System.Char.IsNumber(ModifiedInfixNotation[CurrentPosition])) || 
       (ModifiedInfixNotation[CurrentPosition] == '.'))
    {
        CurrentPosition++;
        if (CurrentPosition == ModifiedInfixNotation.Length) { break; }
    }
    string Number = ModifiedInfixNotation.Substring(
                       NumberStart, CurrentPosition - NumberStart);
    TokenList[TokenLength++] = new Token(Number, 
      new Latex("", Number), false, true, false, O.Clone());
}

Step 2:

else 
{
    bool Found = false;  //flag for an operator was found
    int CharLeft = ModifiedInfixNotation.Length - CurrentPosition;
    for (int i = 0; i < Operations.Length; i++)
    {
        Token T = Operations[i];

        if (CharLeft >= T.QueueItem.Length)
        {
            if (ModifiedInfixNotation.Substring(
                  CurrentPosition, T.QueueItem.Length) == T.QueueItem)
            {
                TokenList[TokenLength] = T.Clone();
                // If the is a "-" then it's a minus sign,
                // check to see if it's a negative sign
                if (TokenLength == 0)
                {
                    if (TokenList[TokenLength].QueueItem == "-")
                    {
                        TokenList[TokenLength] = Negative;
                    }
                }
                else
                {
                    if ((TokenList[TokenLength].QueueItem == "-") && 
                        (TokenList[TokenLength-1].QueueItem == "("))
                    {
                        TokenList[TokenLength] = Negative;
                    }
                }
                TokenLength++;
                CurrentPosition += T.QueueItem.Length;
                Found = true;
                break;
            }
        }
    }

Step 3

if (!Found)
{
    // make sure we are not at the end and don't add a space
    if ((ModifiedInfixNotation[CurrentPosition].ToString() != " ") && 
        (CurrentPosition < ModifiedInfixNotation.Length))
    {
        Latex L = new Latex( "", ModifiedInfixNotation[CurrentPosition].ToString());
        
        if ((TokenLength >0)&&(TokenList[TokenLength - 1].IsOther))
        {
            // if the previous token was a variable and the current one is also a variable,
            // then I need to add a * Token.
            ModifiedInfixNotation = ModifiedInfixNotation.Substring(0, CurrentPosition) + 
              "*" + ModifiedInfixNotation.Substring(CurrentPosition, 
              ModifiedInfixNotation.Length - CurrentPosition);
            CurrentPosition++; // for the * that was added
            retval.InfixNotationCorrected = ModifiedInfixNotation;
            TokenList[TokenLength++] = Multiply;
        }
        TokenList[TokenLength++] = 
          new Token(ModifiedInfixNotation[CurrentPosition].ToString(), 
          L, false, false, true, O.Clone());
        CurrentPosition++;
    }
}  

Using the Tokens from above I convert to RPN format and than return the RPNReturnValues.  Which can then be used to display the RPN string.

public RPNReturnValues Convert(string InfixNotationToConvert, bool ReturnLatex)
{
    RPNReturnValues retval = new RPNReturnValues();
    retval.Error = "";
    retval.Latex = "";
    retval.RPN = "";
    retval.InfixNotation = InfixNotationToConvert;

    string Latex = "";
    string RPN = "";
                
    Token T = null;                           // Temp Token variable

    // Is the string empty - return
    if (InfixNotationToConvert == "") { return retval; }

    Token[] TokenList = CreateTokens(retval);

    for (int c = 0; c < TokenList.Length; c++)
    {
        T = TokenList[c];
        if (T.IsNumber)
        {
            // add to output queues
            RPN += T.QueueItem + " ";
            Latex += T.Latex.Value + " ";
        }
        else if (T.IsOther)
        {
            // add to output queues
            RPN += T.QueueItem + " ";
            Latex += T.Latex.Value + " ";
        }
        else if (T.IsFunction)
        {
            // push onto stack
            TokenStack.Push(T);
        }
        else if (T.QueueItem == ",")
        {
            // function argument separator
            Token StackToken = (Token)TokenStack.Peek();
            while (StackToken.QueueItem != "(")
            {
                StackToken = (Token)TokenStack.Pop();
                RPN += T.QueueItem + " ";
                Latex += T.Latex.Value + " ";

                if (TokenStack.Count == 0)
                {
                    retval.RPN = RPN;
                    retval.Latex = Latex;
                    retval.Error = "Error on stack - unmatched parenthesis";
                    return retval;
                }
                else
                {
                    // look at next token
                    StackToken = (Token)TokenStack.Peek();
                }
            }
        }
        else if (T.Operator.IsOperator)
        {
            if (TokenStack.Count > 0)
            {
                Token T2 = (Token)TokenStack.Peek();
                while (T2.Operator.IsOperator)
                {
                    if ((T.Operator.direction == Associative.Left) && 
                          (T.Operator.Precedence <= T2.Operator.Precedence))
                    {
                        T2 = (Token)TokenStack.Pop();
                        RPN += T2.QueueItem + " ";
                        Latex += T2.Latex.Value + " ";
                    }
                    else if (T.Operator.Precedence < T2.Operator.Precedence)
                    {
                        T2 = (Token)TokenStack.Pop();
                        RPN += T2.QueueItem + " ";
                        Latex += T2.Latex.Value + " ";
                    }
                    else
                    {
                        break;
                    }

                    if (TokenStack.Count == 0)
                    {
                        break;
                    }
                    else
                    {
                        // look at next token
                        T2 = (Token)TokenStack.Peek();
                    }
                }
            }
            TokenStack.Push(T);
        }
        else if (T.QueueItem == "(")
        {
            TokenStack.Push(T);
        }
        else if (T.QueueItem == ")")
        {
            Token T2 = (Token)TokenStack.Pop();
            while (T2.QueueItem != "(")
            {
                RPN += T2.QueueItem + " ";
                Latex += T2.Latex.Value + " ";
                if (TokenStack.Count == 0)
                {
                    retval.RPN = RPN;
                    retval.Latex = Latex;
                    retval.Error = "Error on stack - unmatched parenthesis";
                    return retval;
                }
                else
                {
                    // get next token
                    T2 = (Token)TokenStack.Pop();
                }
            }
        }
    }

    T = (Token)TokenStack.Peek();
    if ((T.QueueItem == "(") || (T.QueueItem == ")"))
    {
        retval.RPN = RPN;
        retval.Latex = Latex;
        retval.Error = "Error on stack - unmatched parenthesis";
        return retval;
    }
    
    while (TokenStack.Count > 0)
    {
        T = (Token)TokenStack.Pop();
        if (T.Operator.IsOperator || T.IsFunction)
        {
            RPN += T.QueueItem + " ";
            Latex += T.Latex.Value + " ";
        }
        else
        {
            retval.RPN = RPN;
            retval.Latex = Latex;
            retval.Error = "Unexpected error on stack\r\n\r\n" + 
                           T.VariableValues();
            return retval;
        }
    }

       retval.RPN = RPN;
       retval.Latex = Latex;
    return retval;
}  

History

• 2013-05-01 Corrected some typo's in the text and modified the description to convey the idea better.
• 2013-04-30: Initial release.  (edited for better readability)