表达式树的后缀表示法

Question

关于如何将表达式树转换为后缀表示法，并没有足够的资源。我不得不将后缀表达式解析到表达式树中。

表达式为：

A 2^2 A * B * - B 2^+ AB -/

我真的没有对如何解释表达的线索。有人对如何处理这个问题有线索吗？

Answer 1

堆（A，2，B等是操作数）为叶节点，不绑定到任何树

1. 推送操作数上创建包含节点这可能是一个树的一部分的堆叠任何方向
2. 对于运营商而言，POP必要的操作数出栈，建立在顶部的运营商的节点，并且挂在它下面的操作数，推新节点压入堆栈

为您的数据：

1. 推阿到堆栈
2. 推2压入堆栈
3. 流行2和A，创建^ -node（以A和表2），将其推到堆栈
4. 推2上堆叠
上堆叠
5. 流行A和2并结合
6. 推A来形成* -node
7. 等
8. 等

这里是一个LINQPad程序，它可以被试验：

// Add the following two using-directives to LINQPad: 
// System.Drawing 
// System.Drawing.Imaging 

static Bitmap _Dummy = new Bitmap(16, 16, PixelFormat.Format24bppRgb); 
static Font _Font = new Font("Arial", 12); 

void Main() 
{ 
    var elementsAsString = "A 2^2 A * B * - B 2^+ A B -/2 ^"; 
    var elements = elementsAsString.Split(' '); 

    var stack = new Stack<Node>(); 
    foreach (var element in elements) 
     if (IsOperator(element)) 
     { 
      Node rightOperand = stack.Pop(); 
      Node leftOperand = stack.Pop(); 
      stack.Push(new Node(element, leftOperand, rightOperand)); 
     } 
     else 
      stack.Push(new Node(element)); 

    Visualize(stack.Pop()); 
} 

void Visualize(Node node) 
{ 
    node.ToBitmap().Dump(); 
} 

class Node 
{ 
    public Node(string value) 
     : this(value, null, null) 
    { 
    } 

    public Node(string value, Node left, Node right) 
    { 
     Value = value; 
     Left = left; 
     Right = right; 
    } 

    public string Value; 
    public Node Left; 
    public Node Right; 

    public Bitmap ToBitmap() 
    { 
     Size valueSize; 
     using (Graphics g = Graphics.FromImage(_Dummy)) 
     { 
      var tempSize = g.MeasureString(Value, _Font); 
      valueSize = new Size((int)tempSize.Width + 4, (int)tempSize.Height + 4); 
     } 

     Bitmap bitmap; 
     Color valueColor = Color.LightPink; 
     if (Left == null && Right == null) 
     { 
      bitmap = new Bitmap(valueSize.Width, valueSize.Height); 
      valueColor = Color.LightGreen; 
     } 
     else 
     { 
      using (var leftBitmap = Left.ToBitmap()) 
      using (var rightBitmap = Right.ToBitmap()) 
      { 
       int subNodeHeight = Math.Max(leftBitmap.Height, rightBitmap.Height); 
       bitmap = new Bitmap(
        leftBitmap.Width + rightBitmap.Width + valueSize.Width, 
        valueSize.Height + 32 + subNodeHeight); 

       using (var g = Graphics.FromImage(bitmap)) 
       { 
        int baseY = valueSize.Height + 32; 

        int leftTop = baseY; // + (subNodeHeight - leftBitmap.Height)/2; 
        g.DrawImage(leftBitmap, 0, leftTop); 

        int rightTop = baseY; // + (subNodeHeight - rightBitmap.Height)/2; 
        g.DrawImage(rightBitmap, bitmap.Width - rightBitmap.Width, rightTop); 

        g.DrawLine(Pens.Black, bitmap.Width/2 - 4, valueSize.Height, leftBitmap.Width/2, leftTop); 
        g.DrawLine(Pens.Black, bitmap.Width/2 + 4, valueSize.Height, bitmap.Width - rightBitmap.Width/2, rightTop); 
       } 
      } 
     } 

     using (var g = Graphics.FromImage(bitmap)) 
     { 
      float x = (bitmap.Width - valueSize.Width)/2; 
      using (var b = new SolidBrush(valueColor)) 
       g.FillRectangle(b, x, 0, valueSize.Width - 1, valueSize.Height - 1); 
      g.DrawRectangle(Pens.Black, x, 0, valueSize.Width - 1, valueSize.Height - 1); 
      g.DrawString(Value, _Font, Brushes.Black, x + 1, 2); 
     } 

     return bitmap; 
    } 
} 

bool IsOperator(string s) 
{ 
    switch (s) 
    { 
     case "*": 
     case "/": 
     case "^": 
     case "+": 
     case "-": 
      return true; 

     default: 
      return false; 
    } 
} 

输出：

Answer 2

这是否看起来是正确的：

for n in items: 
    if n is argument: 
     push n 
    if n is operator: 
     b = pop  // first pop shall yield second operand 
     a = pop  // second pop shall yield first operand 
     push a+n+b 
answer = pop 



A 2^2 A * B * - B 2^+ A B -/

在你的陈述中运行这个应该会产生一个如此演变的栈：

[A] 
[A, 2] 
[A^2] 
[A^2, 2] 
[A^2, 2, A] 
[A^2, 2*A] 
[A^2, 2*A, B] 
[A^2, 2*A*B] 
[A^2-2*A*B] 
[A^2-2*A*B, B] 
[A^2-2*A*B, B, 2] 
[A^2-2*A*B, B^2] 
[A^2-2*A*B+B^2] 
[A^2-2*A*B+B^2, A] 
[A^2-2*A*B+B^2, A, B] 
[A^2-2*A*B+B^2, A-B] 
[A^2-2*A*B+B^2/A-B]