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

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


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


В процессе написания простенького интерпретатора математических выражений (пока что даже без скобок, банальные выражения типа 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 => '+',
)


Буду благодарен за помощь в виде алгоритма.
  • Вопрос задан
  • 2910 просмотров
Пригласить эксперта
Ответы на вопрос 7
Ogra
@Ogra
У вас неправильная позиция изначально. Вам нужно не линейный массив собирать, а дерево из аргументов и операторов.
Ответ написан
@deeperton
При просмотре выражения формировать массив, записей где значением будет структура Приоритет и Операция. Далее, средствами языка отсортировать по полю приоритета не должно стать проблемой (обычный проход функцией по массиву).

А вообще, идеальный вариант Обратная польская запись.
Ответ написан
bit
@bit
Писал аналогичный калькулятор, но со скобками. Сам себе задал такой тест для практикума при изучении C. По-моему проще велосипеда, чем обратная польская запись (она-же постфиксная) для такой арифметики еще не придумали. Все остальное — усложнения, дающие больше путаницы, чем результативности.
For fun — посмотрите в сторону языка Fort. Там вся арифметика постфиксная :)
Ответ написан
Комментировать
@deeperton
Кто мешает в структуру [Приоритет, Операция] впилить и Позицию? Хотя зачем она вам?
Вам нужно распарсить введенное выражение в удобную для обработки рекурсией или циклом форму.
Я бы стремился к такой записи (для 5+15*2/10+2^3):
array(
  0 => '2^3',
  1 => '2/10',
  2 => '15*{1}',
  3 => '5+{2}',
  4 => '{3}+{0},
);

Такой массив проходится одним циклом с простым switch. Но да, вопрос заключался в алгоритме такого разбора =).
Ответ написан
dohlik
@dohlik
Сделать массив операций с заранее известными ключами:
array(
    '^' => array(),
    '*' => array(),
    '/' => array(),
    '+' => array(),
    '-' => array(),
);

А дальше его заполнять найденными позициями. Потом просто в цикле проходить по нему сверху вниз. Другое дело, что позиции тоже как-то несерьезно. Может лучше собрать элементы выражения в стек и использовать не позицию в выражении, а номер элемента в стеке.
Ответ написан
bagyr
@bagyr
Сформировать
array(
1 => 1,
4 => 2,
6 => 2,
9 => 1,
11 => 3,
)
и сортировать его?
Вообще, лучше Dragon Book почитать, там про это есть.
Ответ написан
@Ilnur123
Можно попробовать использовать приоритетную очередь (в народе ее именуют еще «куча»). На с++ она называется priority_queue, на java — PriorityQueue. Можно организовать каждый элемент вашего массива в виде структуры (или класса) с двумя полями: позиция, операция. И перегрузить оператор сравнения (<) для данного класса. Затем уже при разборе выражения вы будете вставлять элементы в эту очередь и они там будут находиться в отсортированном виде. Сложность эквивалентна сложности сортировки (вставка каждого элемента будет производиться за O(log N), где N — количество элементов, уже имеющихся в очереди).
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы