Сортировка массива?

Question

[Chvanikoff]

Приветствую!


Прошу помощи у уважаемого Хабрасообщества с решением такой задачки:


В процессе написания простенького интерпретатора математических выражений (пока что даже без скобок, банальные выражения типа 5+15*2/10+2^3) just 4 fun, как говорится, столкнулся с проблемой…


Я получаю массив операций в выражении вида позиция=>операция, который для приведенного выше примера будет таким:

array(
    1   => '+',
    4   => '*',
    6   => '/'
    9   => '+',
    11 => '^',
)

Также у меня есть массив приоритетов операций вида

array(
    '+' => 1,
    '-' => 1,
    '*' => 2,
    '/' => 2,
    '^' => 3,
)

Сейчас бы отсортировать операции по приоритету, да вот что-то торможу все утро, не могу придумать реализации…


В итоге нужно получить (для данного примера) следующий массив:

array(
    11 => '^',
    4 => '*',
    6 => '/',
    1 => '+',
    9 => '+',
)

Буду благодарен за помощь в виде алгоритма.

Answer 1

[Ogra]

У вас неправильная позиция изначально. Вам нужно не линейный массив собирать, а дерево из аргументов и операторов.

Comments

[Chvanikoff]

Вас не затруднит чуть подробнее объяснить свой ответ?

[Ogra]

Попробую. На самом деле то ответ дан еще в первом посте — Обратная польская запись).
Так вот, эта запись — лишь результат обхода дерева выражения.
Вот пример дерева, нашел в сети, почитайте, вдруг и текст по теме, может и поможет :)

[Arsen]

в дополнение к предыдущему комменту. вот ваше выражение представленное в виде дерева

     (+)
     /  \
  (+)    (^)
  / \    / \
 5  (/) 2   3
    / \
  15   2

[Chvanikoff]

Спасибо.

Answer 2

[deeperton]

При просмотре выражения формировать массив, записей где значением будет структура Приоритет и Операция. Далее, средствами языка отсортировать по полю приоритета не должно стать проблемой (обычный проход функцией по массиву).

А вообще, идеальный вариант Обратная польская запись.

Comments

[Chvanikoff]

но мне ведь нужна и позиция выражения :)
Я думал про такой вариант, как создать временный массив, где ключом была бы позиция, а значением — приоритет операции, отсортировать его по приоритету, а потом заменить обратно приоритет на опирацию, основываясь на ключе в виде позиции. Но как-то это слишком некрасиво получается… :(

Про польскую запись спасибо — было дело, читал, но не смог вчера, начав писать, вспомнить название :)

Answer 3

[bit]

Писал аналогичный калькулятор, но со скобками. Сам себе задал такой тест для практикума при изучении C. По-моему проще велосипеда, чем обратная польская запись (она-же постфиксная) для такой арифметики еще не придумали. Все остальное — усложнения, дающие больше путаницы, чем результативности.
For fun — посмотрите в сторону языка Fort. Там вся арифметика постфиксная :)

Answer 4

[deeperton]

Кто мешает в структуру [Приоритет, Операция] впилить и Позицию? Хотя зачем она вам?
Вам нужно распарсить введенное выражение в удобную для обработки рекурсией или циклом форму.
Я бы стремился к такой записи (для 5+15*2/10+2^3):

array(
  0 => '2^3',
  1 => '2/10',
  2 => '15*{1}',
  3 => '5+{2}',
  4 => '{3}+{0},
);

Такой массив проходится одним циклом с простым switch. Но да, вопрос заключался в алгоритме такого разбора =).

Comments

[deeperton]

чот потерялся в гуйе комментирования…

[Chvanikoff]

Да, я еще перечитываю статьи по приведению выражения к ОПЗ :)

Answer 5

[Иван]

Сделать массив операций с заранее известными ключами:

array(
    '^' => array(),
    '*' => array(),
    '/' => array(),
    '+' => array(),
    '-' => array(),
);

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

Comments

[Иван]

Естественно, массив операций уже отсортирован по приоритетам. Позже еще скобки добавите

[Chvanikoff]

я для каждого оператора планирую искать левый и правый аргументы, выполнять действие и заменять «левый_арг-т, действие, правый_арг-т» на рез-т

Answer 6

[bagyr]

Сформировать
array(
1 => 1,
4 => 2,
6 => 2,
9 => 1,
11 => 3,
)
и сортировать его?
Вообще, лучше Dragon Book почитать, там про это есть.

Comments

[Chvanikoff]

Не поверите — только вчера прислали «книгу дракона»)))

про Ваш вариант я отписался в комменте к первому ответу

Answer 7

[Ilnur123]

Можно попробовать использовать приоритетную очередь (в народе ее именуют еще «куча»). На с++ она называется priority_queue, на java — PriorityQueue. Можно организовать каждый элемент вашего массива в виде структуры (или класса) с двумя полями: позиция, операция. И перегрузить оператор сравнения (<) для данного класса. Затем уже при разборе выражения вы будете вставлять элементы в эту очередь и они там будут находиться в отсортированном виде. Сложность эквивалентна сложности сортировки (вставка каждого элемента будет производиться за O(log N), где N — количество элементов, уже имеющихся в очереди).