Стек - абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (last in — first out, «последним пришёл — первым вышел»). Это значит что если мы положим сначала элемент "1", а затем элемент "2", то мы не сможем получить доступ к элементу "1" до тех пор пока не извлечем элемент "2".
Глубина стека - количество элементов в стеке.
Вершина стека - "последний вставленный в стек элемент"
Требуется написать программу которая, получив на вход строку с математическим выражением, вывела бы на экран его результат или сообщение об ошибке в случае некорректности выражения. Метематичкое выражение может содержать цифры, знаки математических операций, знаки пробела, скобки.
- Вычитание - "-"
- Сложение - "+"
- Деление - "/"
- Умножение - "*"
- Возведение в степеь - "^"
Обход по строке с математическим выражением можно осуществить лишь один раз
Рассмотрим простое выражение 2 + 2 * 2. Еще со школы мы знаем, что умножение должно быть выполнено до сложения, и нам говорили что нам надо так делать по тому что операция умножения "старше" операции сложения. Чтобы объяснить эти простые истины машине нам нужно дать определение того что одна операция "старше" другой.
Как раньше так и сейчас машины умеют работать только с числами и естественно они могут их различать и говорить что одно число больше или меньше другого. Поэтому самым простым решением было сказать компьютеру что у каждой операции есть своя "важность" или, более употребимый термин, приоритет (Precedence). Например, мы можем сказать что у сложения приоритет 1, а у умножения приоритет равен 2 (ведь умножениея "старше"). Поэтому компьютер сравнит 2 и 1 и поймёт что 2 больше, а следовательно операцию умножения нужно произвести раньше.
| Операция | Знак | Приоритет | Количество операндов |
|---|---|---|---|
| "скобка" | ( и ) | 1 | 0 |
| Сложение | + | 2 | 2 |
| Вычитание | - | 2 | 2 |
| Умножение | * | 3 | 2 |
| Деление | / | 3 | 2 |
| Возведение в степень | ^ | 4 | 2 |
Имея знания о приоритетах операций, перейдём к рассмотрению принципов работы синтаксического анализатора простейших математических выражений.
Все символы из которых состоит математическое выражение можно условно поделить на 2 группы: цифры и символы операций. Для каждой из этих групп нам потребуется стек для их хранения, поэтому будем считать что у нас есть стек чисел и стек операций. Разобрать данный алгоритм лучше всего рассмотрев любой пример, например такой: 2*3+2.
Шаг 1
Читаем первый символ, это 2. Мы видим что это цифра, но еще не знаем кончилось число или нет, поэтому сохраняем 2 в память и читаем следующий символ.
Стек чисел: пуст
Стек операций: пуст
Шаг 2
Мы получили символ *. Видя что полученный символ не цифра, делеам вывод что 2, сохраненная в памяти ранее, число. Поэтому кладём его в стек чисел, чтобы воспользоваться позже. Положив 2 в стек, нам нужно понять а что же делать с операцией. Стек чисел у нас не пуст значит мы можем сказать что перед операцией шло число, а т.к умножение - это бинарная операция, то нам нужно ещё одно число. Поэтому положим символ операции в стек и считаем следуещий символ.
Стек чисел: 2
Стек операций: *
Шаг 3
Мы считали 3. Повторяем всю логику с Шага 1.
Стек чисел: 2
Стек операций: *
Шаг 4
Мы считали +. Понимаем что сохранённая в памяти 2 продолжаться не будет и кладём её в стек чисел.
Стек чисел: 2 | 3
Стек операций: *
Операция сложения бинарная, поэтому мы проверяем глубину стека чисел в предположении что нам хватит чисел чтобы её выполнить.
И действительно, в стеке уже есть два числа. Но мы не знаем были ли у нас операции чей приоритет выше чем у операции сложения, ведь если они были, мы должны выполнить их раньше. Для этого нам надо проверить стек операций.
Берём верхний элемент из стека операций и видим что это умножение. Приоритет умножения 2 а сложение всего 1 поэтому первым должно выполнится умножение. Умножению надо 2 числа и они у нас есть. Поэтому нам надо достать их.
Все элементы из стека берутся по одному и извлекаются с конца. Поэтому мы точно можем сказать, что чем ближе элемент к вершине стека, тем позже по времени он был туда вставлен, и следовательно тем позже в записи метематического выражения он встречается. А значит число извлеченное первым будет выступать правым операндом, второе левым. После извлечения чисел и применения операции умножения мы получили результат 6. Он нам еще пригодится для последующих операций, поэтому положим его назад в стек чисел.
Стек чисел: 6
Стек операций: пуст
Теперь вернёмся к прочитанному ранее +. Мы снова смотрим в стек операций и видим что он пуст. Поэтому пробуем применить саму операцию сложения. Проверив глубину стека чисел мы снова замечаем, что нам недостаточно чисел, поэтому просто кладём символ опарации в соответствующмй стек и читаем следующий символ.
Стек чисел: 6
Стек операций: +
Шаг 5
Мы считали 2. Повторяем всю логику с Шага 1.
Стек чисел: 6 | 2
Стек операций: +
Шаг 6
Мы заметили что строка кончилась. Значит выражение мы считали полностью. Осталось проверить, что мы применили все операции которые считали ранее.
Видим что стек операций не пуст и считываем элемент. Получаем +. Проверяем глубину стека чисел. Видим что там есть 2 числа, извлекаем их и применяем операцию. Получаем результат 8 и кладём его назад в стек чисел.
Стек чисел: 8
Стек операций: пуст
Проверяем массив операция дальше и видим что он пуст. Тогда смотрим количество элементов оставшихся в массиве чесел. Там сейчас одно число. Следовательно это и есть результат вычисления. Конец.
В качастве стека лучше использовать массив или SplStack (http://php.net/manual/ru/class.splstack.php). Также рекомендую ознакомится с функциями для работы с массивами в PHP (http://php.net/manual/ru/ref.array.php) для адекватной работы с извлечением и вставкой элемента в стек.
Работу рекомендую разбить на две части. Первая: усвоение принципов работы стека, а также написание / нахождение функций для работы с ним. Вторая: Реализация основной логики программы. Для облегчения разработки операции можно добавлять по одной, после тщательного тестирования добавленных ранее.
После выполнения первой части рекумендую удостоверится в правильном понимании и правильном выборе функций для работы со стеком.