Click here to Skip to main content
Click here to Skip to main content
Alternative Article

Converting Postfix Expressions to Infix

, 20 Jun 2012
Rate this:
Please Sign up or sign in to vote.
This is an alternative for "Converting Postfix Expressions to Infix"

Introduction

This is an alternative to the original post Converting Postfix Expressions to Infix[^].

The approach shown in this alternative tip is to build an AST (abstract Syntax Tree) before writing the resulting infix (or any other form).

Building the AST

The AST consists of Expr elements. Such an expression element has two capabilities: the rank of the expression and it can write itself to a string builder. The rank defines if an expression needs to be converted to a nested expression to respect order of evaluation in infix notation.

  • Expr: base class
  • Number: number literal, e.g. 1
  • NestedExpr: ( Expr ), e.g. (1 + 2)
  • UnaryExpr: unary expression, e.g. -1
  • BinExpr: binary expression, e.g. 1 + 2

The complete code to handles expressions is shown below. Please note that for the sake of the example, the unary minus is encoded as "#". This is needed since the RPN can not distinguish between unary minus and binary minus operation if it is the same symbol.

public class RPN2Infix
{
    // operator ranking
    private enum Rank { Primary, Unary, Mul, Sum, }
    private static Dictionary<string, Rank> _rank = new Dictionary<string, Rank>()
    {
        { "#", Rank.Unary }, // unary minus is coded as "#", unary plus is left out
        { "*", Rank.Mul }, { "/", Rank.Mul },
        { "+", Rank.Sum }, { "-", Rank.Sum }, // binary op
    };
    // base class
    private abstract class Expr
    {
        internal Rank Rank { get; set; }
        internal abstract void Write(StringBuilder sb);
    }
    // literal number
    private class Number : Expr
    {
        private string Value { get; set; }
        internal Number(string value) { Value = value; Rank = Rank.Primary; }
        internal override void Write(StringBuilder sb) { sb.Append(Value); }
    }
    // binary operations
    private class BinExpr : Expr
    {
        private Expr Left { get;  set; }
        private Expr Right { get;  set; }
        private string Op { get; set; }
        private BinExpr(Expr left, Expr right, string op)
        { Left = left; Right = right; Op = op; Rank = _rank[op]; }
        static internal Expr Create(Stack<Expr> stack, string op)
        {
            Expr right = NestedExpr.NestedIfNeeded(stack.Pop(), op);
            Expr left = NestedExpr.NestedIfNeeded(stack.Pop(), op);
            return new BinExpr(left, right, op);
        }
        internal override void Write(StringBuilder sb) { Left.Write(sb); sb.Append(Op); Right.Write(sb); }
    }
    // unary operations
    private class UnaryExpr : Expr
    {
        private string Op { get; set; }
        private Expr Expr { get; set; }
        private UnaryExpr(Expr expr, string op) { Expr=expr; Op=op; Rank=_rank[op]; }
        static internal Expr Create(Stack<Expr> stack, string op)
        {
            Expr expr = NestedExpr.NestedIfNeeded(stack.Pop(), op);
            return new UnaryExpr(expr, op);
        }
        internal override void Write(StringBuilder sb)
        { sb.Append("("); sb.Append(Op == "#" ? "-" : Op); Expr.Write(sb); sb.Append(")");  }
    }
    // nested expression
    private class NestedExpr : Expr
    {
        internal Expr Expr { get; private set; }
        private NestedExpr(Expr expr) { Expr = expr; Rank = Rank.Primary; }
        internal override void Write(StringBuilder sb) { sb.Append("("); Expr.Write(sb); sb.Append(")"); }
        internal static Expr NestedIfNeeded(Expr expr, string op)
        { return expr.Rank > _rank[op] ? new NestedExpr(expr) : expr; }

    }
    // scanner
    private static string _tokenizer = @"\s*(\d+|\S)\s*";
    private static string[] _unary = new string[] { "#" };
    private static bool IsNumber(string token)
    { return string.IsNullOrEmpty(token) || token.Length < 1 ? false : char.IsNumber(token[0]); }
    private static bool IsUnary(string token) { return _unary.Contains(token); }
    // parser
    private Stack<Expr> Stack { get; set; }
    private IEnumerable<string> Tokens { get; set; }
    // initialize
    private RPN2Infix(string input)
    {
        Tokens = Regex.Matches(input, _tokenizer, RegexOptions.Compiled|RegexOptions.Singleline)
                 .Cast<Match>().Select(m=>m.Groups[1].Value);
        Stack = new Stack<Expr>();
    }
    // parse
    private string Parse()
    {
        foreach (string token in Tokens)
        {
            if (IsNumber(token)) Stack.Push(new Number(token));
            else if (IsUnary(token)) Stack.Push(UnaryExpr.Create(Stack, token));
            else Stack.Push(BinExpr.Create(Stack, token));
        }
        StringBuilder sb = new StringBuilder();
        Stack.Pop().Write(sb);
        return sb.ToString();
    }
    // public access
    public static string Parse(string input)
    {
        return new RPN2Infix(input).Parse();
    }
}

Note: to avoid double "-" in sequence (e.g. --1), I decided to nest unary expressions, e.g. (-(-1)). I could have added a space in front of the unary minus, e.g. - -1, which looks a bit odd to me, but would nonetheless be correct.

The usage:

string s = "1 # 2 * 3 4 * 5 6 * + 99 + * # 5 *";
Console.WriteLine("{0} = {1}", s, RPN2Infix.Parse(s));

The output:

1 # 2 * 3 4 * 5 6 * + 99 + * # 5 * = (-((-1)*2*(3*4+5*6+99)))*5

History

V1.0, 2012-06-19, Initial version.

License

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

About the Author

Andreas Gieriet
Founder eXternSoft GmbH
Switzerland Switzerland
I feel comfortable on a variety of systems (UNIX, Windows, cross-compiled embedded systems, etc.) in a variety of languages, environments, and tools.
I have a particular affinity to computer language analysis, testing, as well as quality management.
 
More information about what I do for a living can be found at my LinkedIn Profile and on my company's web page (German only).
Follow on   LinkedIn

Comments and Discussions

 
QuestionParentheses PinmemberClifford Vaughn27-Dec-13 11:28 
QuestionUnaryExpr PinmemberEnrique1415-Mar-13 4:37 
I'm trying to implement this code but I have a doubt. When you write in UnaryExpr you have as follows:
internal override void Write(StringBuilder sb)
{ sb.Append("("); sb.Append(Op == "#" ? "-" : Op); Expr.Write(sb); sb.Append(")"); }
 
Why is it necessary to add parentheses there? What if I just put:
internal override void Write(StringBuilder sb)
{ sb.Append(Op == "#" ? "-" : Op); Expr.Write(sb); }
 
For instance, if "~" is my only unary operator, and I have "~(5+2)", which in prefix notation would be "52+~", with your code the resulting infix would be "(~(5+2))", and with the changes I mentioned, the result would be the same as the input: "~(5+2)".
 
What do you think? Probably I'm missing something, I just don't know what.
 
Btw, thank you for this code, it has helped me a lot.
AnswerRe: UnaryExpr PinmemberAndreas Gieriet15-Mar-13 4:55 
GeneralRe: UnaryExpr PinmemberEnrique1415-Mar-13 5:05 
GeneralRe: UnaryExpr PinmemberAndreas Gieriet15-Mar-13 5:16 
GeneralMy vote of 5 PinmvpKanasz Robert6-Nov-12 0:06 
GeneralRe: My vote of 5 PinmemberAndreas Gieriet6-Nov-12 1:21 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web03 | 2.8.140709.1 | Last Updated 20 Jun 2012
Article Copyright 2012 by Andreas Gieriet
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid