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 classNumber
: number literal, e.g. 1NestedExpr
: ( Expr ), e.g. (1 + 2)UnaryExpr
: unary expression, e.g. -1BinExpr
: 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
{
private enum Rank { Primary, Unary, Mul, Sum, }
private static Dictionary<string, Rank> _rank = new Dictionary<string, Rank>()
{
{ "#", Rank.Unary },
{ "*", Rank.Mul }, { "/", Rank.Mul },
{ "+", Rank.Sum }, { "-", Rank.Sum },
};
private abstract class Expr
{
internal Rank Rank { get; set; }
internal abstract void Write(StringBuilder sb);
}
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); }
}
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); }
}
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(")"); }
}
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; }
}
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); }
private Stack<Expr> Stack { get; set; }
private IEnumerable<string> Tokens { get; set; }
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>();
}
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 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.