Темы
- базовые вопросы о синтаксисе языка
- возможности языка
- принципы управления памятью
- как вращать красно-черное дерево?
- как устроены контейнеры языка?
- планировании архитектуры системы
- подходы к разработке
- управление проектами
- std::auto_ptr
- абстрактное синтаксическое дерево (АСД)
- gzip
- сложность алгоритмов
- компонентам платформы Android
- алгоритмы разбора: shunting yard algorithm, Recursive descent parser, LR-парсер
Статьи
en.wikipedia.org/wiki/Data_structures- en.wikipedia.org/wiki/Dynamic_array
- en.wikipedia.org/wiki/Hash_table
- en.wikipedia.org/wiki/B-tree
- en.wikipedia.org/wiki/Rb-tree
- en.wikipedia.org/wiki/Self-balancing_binary_search_tree
- en.wikipedia.org/wiki/Heap_(data_structure)
- en.wikipedia.org/wiki/Trie
- en.wikipedia.org/wiki/Skip_list
- en.wikipedia.org/wiki/Graph_(abstract_data_type)
en.wikipedia.org/wiki/Sorting_algorithm
Книги
- Вирт, «Алгоритмы + структуры данных = программы»
- Кормен, Ривест, и другие «Алгоритмы: построение и анализ»
- Липпман «Основы программирования на С++»
- Scott Meyers. Effective C++. More Effective C++. Effective STL
- Herb Sutter «Exceptional C++» «More Exceptional C++»
- Тома де Марко и Тимоти Листера «Человеческий фактор»
- Кнут
- Книга дракона
Специальности
- Разработчик систем компьютерного зрения
- Лингвист
- Эксперт по машинному обучению
Задача среднего уровня сложности
Условие
По условию задачи у вас есть формула с цифрами, операциями +-*/ и скобками. Нужно написать программу, которая ее вычисляет. Формула может быть большой. Хочется, чтобы программу можно было легко дорабатывать, вводя функции, параметры и т.д.
Решение
Итак, мы парсим формулу. В результате хотим получить синтаксическое
дерево, где в узлах будут операции, а в листьях – константы. Если бы
скобок не было, дерево было бы очень простым. У нас есть два приоритета
операций, соответственно, дерево получается двухуровневым: сверху стоит +
и -, снизу * и /.
Но так как скобки присутствуют, дерево может иметь неограниченную вложенность. Наивное решение задачи выглядит следующим образом: находим скобки и полностью выкусываем их из получившейся строки и заменяем, например, на имена переменных a1, a2, a3, a4… После разбора получаем двухуровневое дерево. Затем в каждом узле дерева, где осталась переменная, проводим разбор того, что было в скобках, и вставляем результаты вместо соответствующих кусков поддерева.
Однако у нас получился алгоритм с квадратичной временной сложностью в худшем случае, т.к. если у нас будет, например, 100 миллионов вложенных скобок, то на каждом шаге придется искать закрывающую скобку, а потом еще раз парсить эту строку, пройдя ее целиком без правого и левого символов. По большому счету, это уже можно посчитать за верное решение, работать такая программа будет.
Но большинство программистов отметет этот подход как слишком лобовой и неэффективный, сразу перейдя к поиску линейного алгоритма. Для этого, очевидно, начиная рекурсию со скобками не нужно сразу искать закрывающую. Оба наших тестовых кандидата пошли именно по этому пути. Действующий программист знал, как именно это сделать, а потому справился с задачей гораздо быстрей, а менеджеру пришлось с этим повозиться. В результате у обоих получилось нечто похожее на recursive descent parser (подвид LL-парсера).
Но так как скобки присутствуют, дерево может иметь неограниченную вложенность. Наивное решение задачи выглядит следующим образом: находим скобки и полностью выкусываем их из получившейся строки и заменяем, например, на имена переменных a1, a2, a3, a4… После разбора получаем двухуровневое дерево. Затем в каждом узле дерева, где осталась переменная, проводим разбор того, что было в скобках, и вставляем результаты вместо соответствующих кусков поддерева.
Однако у нас получился алгоритм с квадратичной временной сложностью в худшем случае, т.к. если у нас будет, например, 100 миллионов вложенных скобок, то на каждом шаге придется искать закрывающую скобку, а потом еще раз парсить эту строку, пройдя ее целиком без правого и левого символов. По большому счету, это уже можно посчитать за верное решение, работать такая программа будет.
Но большинство программистов отметет этот подход как слишком лобовой и неэффективный, сразу перейдя к поиску линейного алгоритма. Для этого, очевидно, начиная рекурсию со скобками не нужно сразу искать закрывающую. Оба наших тестовых кандидата пошли именно по этому пути. Действующий программист знал, как именно это сделать, а потому справился с задачей гораздо быстрей, а менеджеру пришлось с этим повозиться. В результате у обоих получилось нечто похожее на recursive descent parser (подвид LL-парсера).
