ФЭНДОМ


Польская запись - это альтернативный способ записи арифметических выражений, преимущество которого состоит в отсутствии скобок. Существует два типа польской записи: прямая и обратная, также известные как префиксная и постфиксная. Отличие их от классического, инфиксного способа заключается в том, что знаки операций пишутся не между, а, соответственно, до или после аргументов.

Прямая польская записьПравить

Сразу приведём примеры выражений, записанных таким образом:

* + 3 5 7   ((3 + 5) * 7)
+ * 3 5 7   ((3 * 5) + 7)
+ 3 * 5 7   (3 + (5 * 7))
* 3 + 5 7   (3 * (5 + 7))

Хотя код для разбора прямой записи получается существенно короче, но, тем не менее, понять его несколько сложнее.

 let count_str s =
  let int_of_ascii x = int_of_char x - 48
  and s = s ^ ";"
  and i = ref 0 in
  let parse_num () =
   let rec pn acc =
     match s.[!i] with
       '0'..'9' as x -> incr i; pn (10 * acc + (int_of_ascii x))
      |_ -> acc in pn 0 in
  let rec parse () =
   match s.[!i] with
     '0'..'9' -> parse_num ()
    |' ' -> incr i; parse ()
    |'+' -> incr i; let fst = parse () in fst + parse ()
    |'-' -> incr i; let fst = parse () in fst - parse ()
    |'*' -> incr i; let fst = parse () in fst * parse ()
    |'/' -> incr i; let fst = parse () in fst / parse ()
    |';' -> failwith "End of line reached unexpectedly"
    | _  -> failwith "Unexpected symbol" in
  let result = parse () in if s.[!i] <> ';' then failwith "?!!" else result

Итак, функция parse () пытается разобрать наименьший корректный кусок строки. Полагаю, дальнейшие комментарии излишни: в коде не так уж сложно разобраться.

Обратная польская запись Править

Несколько примеров:

3 5 + 7 *   ((3 + 5) * 7)
3 5 * 7 +   ((3 * 5) + 7)
3 5 7 * +   (3 + (5 * 7))
3 5 7 + *   (3 * (5 + 7))

Обратная польская запись представляется более простой для понимания, но более сложной для реализации, нежели прямая.

 let count_rev s =
  let stack = ref [] in
  let push x = stack := x::!stack
  and pop () =
   match !stack with
    | l1::ls -> stack := ls; l1
    | [] -> failwith "Stack underflow"
  and int_of_ascii x = int_of_char x - 48
  and s = s ^ ";"
  and i = ref 0 in
  let parse_num () =
   let rec pn acc =
     match s.[!i] with
       '0'..'9' as x -> incr i; pn (10 * acc + (int_of_ascii x))
      |_ -> acc in pn 0 in
  let rec parse () =
   match s.[!i] with
     '0'..'9' -> push (parse_num ()); parse ()
    |' ' -> incr i; parse ()
    |'+' -> push (pop () + pop ()); incr i; parse ()
    |'-' -> let snd = pop () in
            push (pop () - snd); incr i; parse ()
    |'*' -> push (pop () * pop ()); incr i; parse ()
    |'/' -> let snd = pop () in
            push (pop () / snd); incr i; parse ()
    | _  -> pop () in
  parse ()

Следует обратить внимание, что ключевым моментом в реализации разбора обратной польской записи является использование стека.

Преобразование инфиксной записи в постфиксную Править

Существует также алгоритм преобразования инфиксной записи в постфиксную с использованием стека и приоритета операций. Он весьма нетривиален, поэтому объяснять, что это такое, я буду сразу на примерах с кодом.

 let priority = function
  | "(" -> 0
  | "+" | "-" -> 1
  | "*" | "/" -> 2
  |  _  -> failwith "Undeclared identifier"

Как нетрудно заметить, эта функция сопоставляет знакам различных операций приоритеты этих операций. Назначение приоритета скобки будет объяснено позднее.


Для работы понадобится стек, а его проще всего представить списком:

 let stack = ref []

А теперь начинается самое интересное. Введём некоторые специальные функции для работы со стеком:

 let rec push x = (* эта функция кладёт новый элемент в стек очень хитрым образом *)
  match !stack with
   | [] -> stack := [x]; "" (* если стек пуст, просто запихать в него элемент *)
   | l1::ls -> if (priority x) > (priority l1) then
                (stack := x::!stack; "") (* то же самое, если новый элемент обладает более *)
               else                      (* высоким приоритетом, чем уже лежащий в стеке *)
                (stack := ls; l1 ^ " " ^ (push x)) (* а иначе - поиск места, где приоритет 
                                нового элемента превысит приоритет уже находящихся в стеке *)
 
 let pop_all () =
  let u = List.fold_left (fun x y -> x ^ y ^ " ") "" !stack in
  stack := []; u (* свёртка и очистка стека *)
 
 let add_bracket () =
  stack := "("::!stack (* просто добавление скобки методом заталкивания*)
 
 let rec rem_bracket () =
  match !stack with
   | [] -> failwith "unmatched closing bracket detected"
   | l1::ls -> stack := ls; if l1 = "(" then "" else (l1 ^ " " ^ (rem_bracket ()))
  (* что-то вроде pop_all (), но только до ближайшей скобки *)

Фактически, код выше - это основная часть проблемы; теперь осталось совсем немного.

 let postfix_of_infix s =
  let s = s ^ ";"
  and i = ref 0
  and int_of_ascii x = int_of_char x - 48 in
  let parse_num () =
   let rec pn acc =
     match s.[!i] with
       '0'..'9' as x -> incr i; pn (10 * acc + (int_of_ascii x))
      |_ -> acc in pn 0 in
  let rec parse () =
   match s.[!i] with
     '0'..'9' -> let u = (string_of_int (parse_num ())) in u ^ " " ^ parse ()
    |' ' -> incr i; parse ()
    |'+' -> incr i; let u = (push "+") in u ^ parse ()
    |'-' -> incr i; let u = (push "-") in u ^ parse ()
    |'*' -> incr i; let u = (push "*") in u ^ parse ()
    |'/' -> incr i; let u = (push "/") in u ^ parse ()
    |'(' -> incr i; add_bracket (); parse ()
    |')' -> incr i; let u = (rem_bracket ()) in u ^ parse ()
    | _  -> pop_all () in
  parse ()

Вот эта штука преобразует инфиксную запись в постфиксную. К сожалению, времени на более подробное объяснение уже не остаётся.