Notación de Postfix en el árbol de expresiones

Hay suficientes recursos sobre cómo convertir un árbol de expresiones en notación postfija, y no es tan difícil.

Pero tengo que analizar una expresión postfijo en un árbol de expresiones.

La expresión es:

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

Realmente no tengo ni idea de cómo interpretar la expresión. ¿Alguien tiene una pista sobre cómo procesar esto?

Crea una stack que contenga nodos que podrían ser parte de un árbol

  1. Empujar operandos en una stack (A, 2, B, etc. son operandos) como nodos hoja, no vinculados a ningún árbol en ninguna dirección
  2. Para los operadores, extraiga los operandos necesarios de la stack, cree un nodo con el operador en la parte superior y los operandos que cuelgan debajo de él, empuje el nuevo nodo hacia la stack

Para sus datos:

  1. Presione A en la stack
  2. Presione 2 en la stack
  3. Pop 2 y A, crea ^ -node (con A y 2 abajo), empújalo en la stack
  4. Empuje 2 en la stack
  5. Presione A en la stack
  6. Pop A y 2 y combinados para formar el nodo *
  7. etc.
  8. etc.

estructura de árbol

Aquí hay un progtwig LINQPad con el que se puede experimentar:

// 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 ^ + AB - / 2 ^"; var elements = elementsAsString.Split(' '); var stack = new Stack(); 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; } } 

Salida:

Salida LINQPad

¿Esto se ve correcto?

 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 ^ + AB - / 

Ejecutar esto en tu statement debería generar una stack que evolucione así:

 [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, AB] [A^2-2*A*B+B^2/AB]