表達式樹的後綴表示法

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]