表达式树的后缀符号

问题描述 投票:26回答:3

有足够的资源来将表达式树转换为后缀表示法,这并不难。

但是我必须将后缀表达式解析为表达式树。

表达式是:

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

我对如何解释该表达方式一无所知。有人对如何进行此操作有任何线索吗?

algorithm language-agnostic
3个回答
57
投票

创建一个包含可能属于树的节点的堆栈

  1. 将堆栈上的操作数(A,2,B等是操作数)作为叶节点,不以任何方向绑定到任何树
  2. 对于运算符,将必要的操作数从堆栈中弹出,创建一个运算符在顶部的节点,并将该操作数挂在其下方,将新节点压入堆栈

为您提供数据:

  1. 将A推入堆栈
  2. 将2推送到堆栈上
  3. Pop 2和A,创建^节点(下面带有A和2),将其压入堆栈
  4. 将2推送到堆栈上
  5. 将A推入堆栈
  6. Pop A和2并合并形成*节点

“树结构”

这里是一个可以尝试的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;
    }
}

输出:

“


5
投票

看起来正确吗:

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]

0
投票

如何在不使用堆栈的情况下执行此操作?

© www.soinside.com 2019 - 2024. All rights reserved.