Click here to Skip to main content
Click here to Skip to main content

Tagged as

Another Postfix (RPN) to Infix convertor

, 1 May 2013 CPOL
Rate this:
Please Sign up or sign in to vote.
Convert infix to RPN with Latex names for operators

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)

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Michael Jenck
Instructor / Trainer
United States United States
I am a Mathematics Instructor at a 2-year community college.

Comments and Discussions

 
-- There are no messages in this forum --
| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.141223.1 | Last Updated 1 May 2013
Article Copyright 2013 by Michael Jenck
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid