Notacja Postfix do drzewa wyrażeń

Question

Istnieje wystarczająca ilość zasobów, aby przekonwertować drzewo wyrażeń na notację postfiksową i nie jest to takie trudne.

Ale muszę parsować wyrażenie postfiksowe w drzewie wyrażeń.

Wyrażenie to:

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

tak naprawdę nie mają pojęcia o tym, jak interpretować wyrażenie . Czy ktoś ma pojęcia, jak to zrobić?

Answer 1

Tworzenie stosu zawierającego węzły, które mogą być częścią drzewa

1. push argumentów na stosie (A, 2, B, itd są operandy) jako liści węzłów, nie wiąże się z żadnym drzewie dowolny kierunek
2. Dla operatorów, pop koniecznych argumentów ze stosu, należy utworzyć węzeł z operatorem na górze, a argumenty wiszące pod nią wcisnąć nowy węzeł na stosie

dla danych:

1. wypychanie na stos
2. wypychania 2 na stos
3. pop 2 i A, tworzenie^-node (z i 2 poniżej) przesunąć na stosie
4. Naciśnij 2 w stosie
5. naciskać na stosie
6. pop i 2 i łączą się * -node
7. itp
8. itp

Oto program LINQPad że można eksperymentować z:

// 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; 
    } 
} 

wyjściowa:

Answer 2

Czy to wygląda poprawne:

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 -/

Running to na statment powinna przynieść stos, który ewoluuje tak:

[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]