Postfix-Notation zum Ausdrucksbaum

Question

Es gibt genügend Informationen darüber, wie man einen Ausdrucksbaum in die Postfix-Notation umwandelt, und es ist gar nicht so schwer.

Aber ich muss einen Postfix-Ausdruck in einen Ausdrucksbaum parsen.

Der Ausdruck lautet:

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

Ich habe nicht wirklich eine Ahnung, wie ich den Ausdruck interpretieren soll. Hat jemand eine Idee, wie man das verarbeiten kann?

Answer 1

Erstellen eines Stapels mit Knoten, die Teil eines Baumes sein könnten

1. Operanden auf einen Stapel schieben (A, 2, B, usw. sind Operanden) als Blattknoten, die in keiner Richtung an einen Baum gebunden sind
2. Bei Operatoren werden die erforderlichen Operanden vom Stapel genommen, ein Knoten mit dem Operator an der Spitze und den darunter hängenden Operanden erstellt und der neue Knoten auf den Stapel geschoben.

Für Ihre Daten:

1. A auf den Stapel schieben
2. 2 auf den Stapel schieben
3. 2 und A einblenden, ^-Knoten erzeugen (mit A und 2 darunter), auf den Stapel schieben
4. 2 auf den Stapel schieben
5. A auf den Stapel schieben
6. Pop A und 2 und verbinden sich zu einem *-Knoten
7. usw.
8. usw.

Hier ist ein LINQPad Programm, mit dem experimentiert werden kann:

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

Ausgabe:

Answer 2

Sieht das richtig aus:

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

Wenn Sie dies für Ihr Statement ausführen, sollte sich ein Stack ergeben, der sich wie folgt entwickelt:

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