Click here to Skip to main content
15,867,834 members
Articles / General Programming / Algorithms
Alternative
Article

Converting Postfix Expressions to Infix

Rate me:
Please Sign up or sign in to vote.
5.00/5 (5 votes)
20 Jun 2012CPOL1 min read 18.6K   4   7
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.

C#
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:

C#
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)


Written By
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).

Comments and Discussions

 
QuestionParentheses Pin
Clifford Vaughn27-Dec-13 11:28
Clifford Vaughn27-Dec-13 11:28 
QuestionUnaryExpr Pin
Enrique1415-Mar-13 4:37
Enrique1415-Mar-13 4:37 
AnswerRe: UnaryExpr Pin
Andreas Gieriet15-Mar-13 4:55
professionalAndreas Gieriet15-Mar-13 4:55 
GeneralRe: UnaryExpr Pin
Enrique1415-Mar-13 5:05
Enrique1415-Mar-13 5:05 
GeneralRe: UnaryExpr Pin
Andreas Gieriet15-Mar-13 5:16
professionalAndreas Gieriet15-Mar-13 5:16 
GeneralMy vote of 5 Pin
Kanasz Robert6-Nov-12 0:06
professionalKanasz Robert6-Nov-12 0:06 
good code Smile | :) a couple of years ago when I was at college I had to solve this kind of problem Smile | :) well done
GeneralRe: My vote of 5 Pin
Andreas Gieriet6-Nov-12 1:21
professionalAndreas Gieriet6-Nov-12 1:21 

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

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