Converting from a prefix record to an infix record

How to convert prefix notation (Polish notation) to infix notation. The record may contain: '(', ')', '+', '-', '*', '/', '0..9', 'a..z'. Tell me the algorithm for solving this problem (description, Pascal, C#), which data structures should be used?

Author: A K, 2015-12-14
Source

2 answers

The obvious honest algorithm is to parse the Polish entry into a tree. With a tree, you can recursively build any form of writing (as well as optimize, compile, and execute anything).

To write

− 5 * 6 7

You do the following steps:

  1. If you see a minus sign, you allocate a node of a binary operation with two operands.
  2. Read the first operand.
    • see 5, this is the first operand, allocate a leaf node for it with the constant
  3. Read the second operand.
    • see *, allocate a binary operation node with two operands for it
    • reading the first operand
      • see 6, allocate a leaf node for it with the constant
      • see 7, allocate a leaf node for it with the constant

For a specific task, you can simplify the result, and not build a tree, but immediately output the data. The algorithm it will be like this:

  • Read one token
  • If it is a constant, it is the result of
  • If this is a binary operation, remember its type, recursively get the value of the operands, output the expression, enclosing it in parentheses, so as not to think about the priority of the operators.
  • add rules for other node types to your liking
 4
Author: VladD, 2015-12-14 13:31:58

If the extra parentheses in the result are not a problem, then you can convert it with normal recursion:

class Program
{
    static void Main(string[] args)
    {
        string source = "- * / 15 - 7 + 1 1 3 + 2 + 1 1";

        var tokens = new Queue<string>(source.Split());

        Console.WriteLine(DoConvert(tokens));
    }

    private static string[] operators = new string[] { "+", "-", "*", "/" };

    private static string DoConvert(Queue<string> tokens)
    {
        var token = tokens.Dequeue();

        if (operators.Contains(token))
        {
            return String.Format("({0} {1} {2})", DoConvert(tokens), token, DoConvert(tokens));
        }
        else
        {
            return token;
        }
    }
}
 2
Author: PashaPash, 2015-12-14 13:31:01