15,040,729 members
Articles / General Programming / Algorithms
Alternative
Article
Posted 20 Jun 2012

15.3K views
3 bookmarked

# Converting Postfix Expressions to Infix

Rate me:
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.

## Share

 Founder eXternSoft GmbH 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).

 First Prev Next
 Parentheses Clifford Vaughn27-Dec-13 11:28 Clifford Vaughn 27-Dec-13 11:28
 UnaryExpr Enrique1415-Mar-13 4:37 Enrique14 15-Mar-13 4:37
 Re: UnaryExpr Andreas Gieriet15-Mar-13 4:55 Andreas Gieriet 15-Mar-13 4:55
 Re: UnaryExpr Enrique1415-Mar-13 5:05 Enrique14 15-Mar-13 5:05
 Re: UnaryExpr Andreas Gieriet15-Mar-13 5:16 Andreas Gieriet 15-Mar-13 5:16
 My vote of 5 Kanasz Robert6-Nov-12 0:06 Kanasz Robert 6-Nov-12 0:06
 Re: My vote of 5 Andreas Gieriet6-Nov-12 1:21 Andreas Gieriet 6-Nov-12 1:21
 Last Visit: 31-Dec-99 18:00     Last Update: 27-Sep-21 2:43 Refresh 1