How to convert a 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 #), what data structures should I use?

  • "If the operator has a fixed arity, then such an entry will not have parentheses and it can be interpreted without ambiguity." - user190794
  • @PashaPash: In theory, no, it seems to be called non-scrap. - VladD
  • @VladD non-partial is a postfix - reverse Polish notation. direct - maybe if there are operators of different arities - -a and - ab - PashaPash ♦
  • Hm And how in the writeback to interpret this: 5 7 - ? Is it unary minus or binary? And if so: 5 7 - * ? - VladD

2 answers 2

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

To record

 − 5 * 6 7

you take the following steps:

  1. You see a minus, allocate the node of a binary operation with two operands.
  2. Read the first operand.
    • see 5 , this is the first operand, allocating for it a leaf node with a constant
  3. Read the second operand.
    • see * , allocate for it a binary operation node with two operands
    • read the first operand
      • see 6 , blocking for him a leaf node with a constant
      • see 7 , allocate for it a leaf node with a constant

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

  • Read one token
  • If it is a constant, it is the result.
  • If this is a binary operation, remember its type, recursively obtain the value of the operands, output the expression, enclose it in brackets, so as not to think about the priority of operators.
  • add rules for other types of knots to taste

    If the extra parentheses as a result is not a problem, then you can convert it with ordinary 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; } } }