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.