Существуют алгоритмы, короткие и простые по формулировке, но не очень лёгкие для понимания. Один из них - алгоритм преобразования выражения в инфиксной форме в постфиксную (она же обратная польская нотация), (он же алгоритм сортировочной станции).
Приведенные рассуждения помогут понять алгоритм и, при необходимости, восстановить по памяти и реализовать самостоятельно.
Суть обратной польской нотации
Напомню. Это важно для понимания алгоритма.
Это форма записи математических выражений, в которой операнды расположены перед знаками операций. Её преимущество в том, что выражение записанное таким образом можно вычислить за один проход по следующему алгоритму:
Заводим стек. Идем по выражению слева направо. Если встретили операнд, кладём в стек, если встретили операцию, достаём из стека операнд - это правый, достаём из стека операнд - это левый (да, в стеке выше находится правый операнд!) выполняем с ними операцию, результат кладём в стек, когда пройдём всё выражение в стеке будет лежать результат.
Пример:
Выражение в инфиксной форме "2 + 3 * 5 - 4"
Эквивалентное выражение в постфиксной форме "2 3 5 * + 4 -"
Вычисление выражения в постфиксной форме па шагам:
выражение: "2 3 5 * + 4 -" стек: []
выражение: "3 5 * + 4 -" стек: [2]
выражение: "5 * + 4 -" стек: [2, 3]
выражение: "* + 4 -" стек: [2, 3, 5]
выражение: "+ 4 -" стек: [2, 15]
выражение: "4 -" стек: [17]
выражение: "-" стек: [17, 4]
выражение: "" стек: [13]
ответ 13
Описание алгоритма
Я рассматриваю алгоритм для выражений с левоассоциативными бинарными операторами (последовательность одинаковых операторов вычисляется слева направо. т.е. 1+2+3 вычисляется как (1+2) + 3), скобками.
Алгоритм преобразования из инфиксной формы в постфиксную:
Заводим стек, проходим по выражению слева направо.
если встретили операнд, записываем в ответ.
если встретили оператор - достаём из стека и записываем в ответ все операторы из стека пока они больше или равны текущему по приоритету или пока стек не опустеет или пока не встретили открывающую скобку в стеке; Кладём оператор в стек.
если встретили открывающую скобку кладём в стек.
если встретили закрывающую скобку записываем в ответ все операторы из стека пока не достанем из стека открывающую скобку.
Когда выражение закончилось, всё что осталось в стеке записываем в ответ.
Сам алгоритм довольно прост, но понять почему он работает не просто.
Объяснение
Попробуем придумать этот алгоритм по шагам начав с простых выражений постепенно усложняя их и модифицируя алгоритм. Начнём с простого примера.
"a + b" должно быть преобразовано в "a b +"
Операнды в ответе идут в том же порядке что и в исходной записи, переместился только оператор +. Придумываем такой алгоритм:
Записываем первый операнд в ответ, запоминаем куда-то оператор, записываем второй операнд, записываем оператор в ответ.
Усложняем пример.
"a + b - c" должно быть преобразовано в "a b + c -"
Мы работаем с левоассоциативными операторами поэтому мы хотим чтобы вначале выполняется +. Попробуем применить наш алгоритм. Действуем так: записываем a, + запоминаем, записываем b, записываем +, запоминаем -, записываем с, записываем -.
Пока работает. В общем виде:
если встретили операнд, то записываем в ответ.
если встретили оператор, то запоминаем, записываем в ответ после того как записали следующий операнд в ответ.
Добавим оператор с другим приоритетом.
"a + b * c" должно быть преобразовано в "a b c * +"
Для этого примера наш алгоритм не будет работать. После b рано записывать +, мы хотим, чтобы сначала выполнилось *, а значит нужно его раньше записать в ответ. Записывать + нужно когда далее будет равная по приоритету операция (т.к. мы хотим чтобы одинаковые по приоритету выполнялось слева направо: сначала то, что уже сохранено, потом то что позже встретили). В общем случае записывать запомненный оператор надо не после следующего операнда, а когда следующий оператор равен или меньше по приоритету. Или когда мы дошли до конца выражения. В итоге алгоритм принимает следующий вид:
если встретили операнд, то записываем с ответ.
если встретили оператор, то запоминаем, предварительно удалив запомненный ранее, если он есть и больше либо равен по приоритету.
Когда дошли до конца строки оператор записываем в ответ.
Так как мы теперь не записываем в ответ оператор сразу после следующего операнда, запоминать придётся более одного оператора. Также отметим, что добавлять операторы в ответ нужно в в порядке противоположном их запоминанию, поэтому хранить удобно в стеке.
Например
"a + b * c - d" должно быть преобразовано в "a b c * + d -"
После того как мы прошли с в стеке находятся +, * которые оба надо записать в ответ (вытолкнуть из стека) перед тем как добавить туда -. Получаем следующий алгоритм:
- если встретили операнд, то записываем в ответ.
- если встретили оператор, то сохраняем в стек, предварительно вытолкнув операторы из стека в ответ пока стек не пуст и оператор на вершине стека больше либо равен текущему по приоритету.
Когда дошли до конца строки все операторы из стека записываем в ответ.
Добавим скобки.
Выражение в скобках - это полноценное выражение которое после вычисления становится операндом, поэтому, когда мы встречаем открывающую скобку мы не должны выталкивать операторы из стека, сначала мы должны записать в ответ “операнд”, т.е. все операторы и операнды в скобках.
Нам нужно запомнить место с которого начинается выражение в скобках - по сути отдельное выражение, для того, чтобы когда оно закончится (закрывающая скобка), знать какие операторы в стеке относятся к выражению в скобках, а какие были еще до скобок. Т.о. когда мы встречаем открывающую скобку то мы сохраняем её в стек как признак начала выражения в скобках.
При окончании выражения в скобках действуют правила окончания всего выражения: если встретили закрывающую скобку, то вытолкнуть все операторы до открывающей скобки (первой встретившейся, т.к. скобки могут быть вложенными).
В итоге получаем оригинальный алгоритм:
если встретили операнд, то записываем в ответ
если встретили оператор, то сохраняем в стек, предварительно вытолкнув операторы из стека в ответ пока стек не пуст и оператор на вершине стека больше либо равен текущему по приоритету или пока не встретим открывающую скобку
если встретили открывающую скобку, заносим её в стек
если встретили закрывающую скобку, операторы из стека записываем в ответ до открывающей скобки, открывающую удаляем из стека.
Когда дошли до конца строки все операторы из стека записываем в ответ.
Комментарии (15)
Refridgerator
11.07.2023 02:02А также в математических выражениях ещё есть степени и функции.
Radisto
11.07.2023 02:02степени и функции (одной переменной) - это унарные операторы. думаю, в такой записи бинарные и унарные операторы надо четко различать. Вот что делать с унарным минусом, чтобы его н путать с бинарным? лучше наверное переименовать, чтобы "-" был только бинарным (ну или отказаться от унарного минуса вовсе, заменив его на "0 -" )
libroten
11.07.2023 02:02+1Как вариант, можно усложнить алгоритм парсинга выражения, написав грамматику с учетом унарных, бинарных операторов, их приоритетов.
При правильной грамматике, унарный и бинарный минусы в процессе разбора по грамматике, будут различаться автоматически.
aavezel
11.07.2023 02:02-1степень это оператор выше умножения.
а функции надо выделять на этапе разбора лексем первоначального выражения и выписывать их как унарный оператор на самом высоком уровне. Т.е. у нас есть выражение:
exp(1+x)*-2
Его надо распарсить на 2 массива
f1 = exp . [1, +, x]
[f1, *, -2]далее преобразуем оба массива в обратную польскую
f1 = exp . [1, x, +] = 1 x + exp
f1 -2 *И во втором выражении подменяем f1
1 x + exp -2 *
18741878
Как будут обработаны унарный минус или плюс?
aavezel
Унарный минус эо признак числа, а не оператор. Такие вещи должны быть выявлены на этапе разбиения на лексемы исходного выражения
18741878
Да? А как насчет "-(2 + 3 - 4*5)" или в общем виде "-(a + b - c*d)" и ему подобных? Конечно, это нарочно придуманный пример, но алгоритм должен справляться с любым допустимым арифметическим выражением.
Далее, есть и другие унарные операторы, например: !, ~. Это именно операторы, а не признаки числа. С точки зрения математики - это именно операция (или оператор в терминологии языков программирования), но никак не признак. См. https://ru.wikipedia.org/wiki/Унарная_операция
gdt
Короче нужен рекурсивный спуск или взрослые табличные парсеры
belch84
Язык древний, но работает
KindCat
Можно использовать 0 - (2 + 3 - 4*5) в инфиксной записи. В постфиксной записи:
0 2 3 + 4 5 * - -
18741878
Можно, но это означает, что программист должен выполнить часть работы компилятора и помнить о том, что унарный минус обрабатывается особенным образом. Это немножко странно :)
funny_falcon
Легко: если встретился минус, а перед ним не было операндов (т.е. начало выражения или перед этим была скобка) то пушим ноль в качестве операнда.
Альтернатива: заводим (внутреннюю) операцию «унарный минус» с соответствующим приоритетом (выше умножения), и пушим её, если не было операнда и был минус.
Конечно, тут приходится новую яйчейку памяти заводить под «не было операндов». А всё потому, что один знак «минус» использован для разных операций. Логически они одинаковые, но имеют разное число аргументов.
С унарными операциями, имеющими свой собственный знак, такой проблемы нет. Правда, нас спасает то, что математические унарные операции - префиксные и имеют высокий приоритет. Благодаря этим свойствам, они вписываются в алгоритм.
idemko
Учитывайте, что при нормализации вашего выражения, мы получаем -1 * (a + b - c*d), где - становится признаком числа.
GravityTwoG
Я, кстати, делал программу для вычисления математических выражений. Если в начале выражения встречается знак минуса, то в ответ записывается 0, а минус кладется в стэк, т.е. происходит преобразование унарного минуса в бинарный.