Notation de la notation Postfix à l'arbre d'expression

Question

Il y a suffisamment de ressources sur la façon de convertir un arbre d'expression en notation postfixée, et ce n'est pas si difficile.

Mais je dois analyser une expression postfix dans un arbre d'expression.

L'expression est:

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

Je n'ai pas la moindre idée sur la façon d'interpréter l'expression . Est-ce que quelqu'un a une idée sur la façon de traiter cela?

Answer 1

créer une pile contenant des noeuds qui pourraient faire partie d'un arbre

1. poussoirs opérandes sur une pile (A, 2, B, etc. sont des opérandes) en tant que noeuds de feuille, ne sont pas liés à un arbre toute direction
2. Pour les opérateurs, pop les opérandes nécessaires de la pile, créez un nœud avec l'opérateur en haut, et les opérandes suspendus au-dessous, pousser le nouveau nœud sur la pile

Pour vos données:

1. poussoir A sur la pile
2. poussoir 2 dans la pile
3. Pop 2 et A, créer^-node (avec A et 2 ci-dessous), appuyer sur la pile
4. poussoir 2 sur la pile
5. Poussez A sur pile
6. Pop A et 2 et se combinent pour former le * -node
7. etc.
8. etc.

Voici un programme LINQPad qui peut être expérimenté:

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

Sortie:

Answer 2

Est-ce que ce regard correct:

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

Exécution de ce sur votre déclaration devrait donner une pile qui évolue comme ceci:

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