将后缀表达式转换为中缀表达式

引言

这是原始文章 将后缀表达式转换为中缀表达式[^] 的替代方案。

此替代方案采用的方法是在编写最终的中缀表达式（或任何其他形式）之前构建一个 AST（抽象语法树）。

构建 AST

AST 由 Expr 元素组成。 这种表达式元素具有两种功能：表达式的优先级以及它可以将自身写入字符串构建器。 优先级定义了是否需要将表达式转换为嵌套表达式，以尊重中缀表示法中的求值顺序。

• Expr：基类
• Number：数字字面量，例如 1
• NestedExpr：（Expr），例如 (1 + 2)
• UnaryExpr：一元表达式，例如 -1
• BinExpr：二元表达式，例如 1 + 2

下面显示了处理表达式的完整代码。 请注意，为了示例的需要，一元负号被编码为 "#"。 这是必要的，因为 RPN 无法区分一元负号和二元负号运算（如果它们是相同的符号）。

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();
    }
}

注意：为了避免连续的两个 "-"（例如 --1），我决定嵌套一元表达式，例如 (-(-1))。 我本可以添加一个空格在负号前面，例如 - -1，这看起来有点奇怪，但仍然是正确的。

用法

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

输出

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

历史

V1.0，2012-06-19，初始版本。