Спустя долгое время я собираюсь работать над оценкой экспрессии, поэтому я пишу это сообщение в блоге, чтобы вернуться к нему и объяснить его самому себе.
Выражения, которые мы (люди) пишем, называются инфиксными выражениями, поскольку операторы помещаются между операндами, чтобы обозначить поток выполнения выражения.
Рассмотрим следующее выражение.
A + B, это инфиксное выражение, потому что оператор «+» стоит между операндами «A» и «B».
Для оценки выражений вручную полезно использовать инфиксную нотацию, поскольку она легко понимается человеческим мозгом.
Но инфиксные выражения трудно анализировать в компьютерной программе, поэтому будет сложно оценивать выражения, используя инфиксную нотацию. Для уменьшения сложности вычисления выражений в компьютерных программах используются префиксные или постфиксные выражения.
Давайте посмотрим, что такое выражения Postfix:
В выражениях Postfix операторы идут после операндов. Ниже приведены инфиксные и соответствующие выражения Postfix.
A + B → A B +
Как упоминалось в приведенном выше примере, в выражении Postfix оператор стоит после операндов.
Чтобы начать преобразование выражения Infix в Postfix, во-первых, мы должны знать о приоритете операторов.
Приоритет оператора:
При оценке выражений решающее значение имеет приоритет операторов.
Верхний оператор в таблице имеет наивысший приоритет. В соответствии с приоритетом операторы будут помещены в стек.
Давайте посмотрим на пример преобразования инфикса в Postfix, мы начнем с простого,
Инфиксное выражение: A + B
Если мы встретим операнд, мы запишем его в строку выражения, если мы встретим оператор, мы поместим его в стек операторов.
Итак, у нас есть два элемента,
- Пустая строка выражения
- Пустой стек операторов
Сначала в выражении мы встречаем «A», поскольку это операнд, который мы добавим в строку выражения. Итак, теперь два элемента выглядят так, как показано ниже,
- Строка выражения: A
- Стек операторов:
Второй токен, с которым мы сталкиваемся, - это оператор «+», поэтому мы поместим его в стек операторов.
- Строка выражения: A
- Стек операторов: +
Третий токен - это операнд «B», поэтому мы добавим его в строку выражения.
- Строка выражения: A B
- Стек операторов: +
Таким образом, мы обработали все токены в данном выражении, теперь нам нужно извлечь оставшиеся токены из стека и добавить их в строку выражения.
Извлеките из стека оператор «+» и добавьте его в строку выражения, в которой уже есть «A B».
Итак, теперь вывод становится «A B +», который является нотацией Postfix для данного инфиксного выражения «A + B».
Второй пример:
Давайте преобразуем небольшое сложное выражение в круглые скобки. Ниже приведено данное инфиксное выражение,
( ( A + B ) — C * ( D / E ) ) + F
Данное выражение заключено в круглые скобки для обозначения приоритета. Итак, давайте начнем с преобразования с двумя пустыми элементами соответственно,
- Пустая строка выражения
- Пустой стек операторов
Первый обнаруженный токен - открытая скобка, добавьте ее в стек операторов.
- Строка выражения:
- Стек операторов: (
- Оставшееся выражение: (A + B) - C * (D / E)) + F
Второй встреченный токен - снова открытая скобка, добавьте ее в стек.
- Строка выражения:
- Стек операторов: ((
- Оставшееся выражение: A + B) - C * (D / E)) + F
Следующим токеном выражения является операнд «A», поэтому добавьте его в строку выражения.
- Строка выражения: A
- Стек операторов: ((
- Оставшееся выражение: + B) - C * (D / E)) + F
После этого у нас есть оператор «+», поэтому добавляем его в стек.
- Строка выражения: A
- Стек операторов: ((+
- Оставшееся выражение: B) - C * (D / E)) + F
Затем у нас есть операнд, поэтому добавьте его в строку выражения.
- Строка выражения: A B
- Стек операторов: ((+
- Оставшееся выражение: ) - C * (D / E)) + F
Следующим токеном в данном инфиксном выражении является закрывающая скобка, поскольку мы столкнулись с закрывающей скобкой, мы должны извлечь выражения из стека и добавить их в строку выражения, пока открытая скобка не выскочит из стека.
- Строка выражения: A B +
- Стек операторов: (
- Оставшееся выражение: - C * (D / E)) + F
Обратите внимание, что здесь мы не поместили закрывающую скобку в стек, вместо этого мы извлекли оператор «+» и добавили его в строку выражения, а также вытащили одну открывающую скобку из стека.
Далее мы сталкиваемся с оператором «-», поэтому помещаем его в стек.
- Строка выражения: A B +
- Стек операторов: (-
- Оставшееся выражение: C * (D / E)) + F
Далее идет операнд «C», поэтому добавьте его в строку выражения,
- Строка выражения: A B + C
- Стек операторов: (-
- Оставшееся выражение: * (D / E)) + F
Далее следует оператор «*», поэтому поместите его в стек.
- Строка выражения: A B + C
- Стек операторов: (- *
- Оставшееся выражение: (D / E)) + F
Далее следует открывающая скобка, поэтому добавьте ее в стек.
- Строка выражения: A B + C
- Стек операторов: (- * (
- Оставшееся выражение: D / E)) + F.
Далее идет операнд «D», поэтому добавьте его в строку выражения.
- Строка выражения: A B + C D.
- Стек операторов: (- * (
- Оставшееся выражение: / E)) + F
Затем мы сталкиваемся с оператором «/», поэтому помещаем его в стек.
- Строка выражения: A B + C D.
- Стек операторов: (- * (/
- Оставшееся выражение: E)) + F.
Затем нажмите «E», добавьте его в строку выражения.
- Строка выражения: A B + C D E
- Стек операторов: (- * (/
- Оставшееся выражение: )) + F
Затем закрывающая скобка, как мы видели ранее, мы не должны помещать ее в стек, вместо этого мы должны вытащить все операторы из стека и добавить их в строку выражения, пока мы не встретим открытую скобку. Затем вытолкните открывающую скобку из стека, но не добавляйте ее в строку выражения.
- Строка выражения: A B + C D E /
- Стек операторов: (- *
- Оставшееся выражение: ) + F
Следующий токен - это снова закрывающая скобка, поэтому мы вытолкнем все операторы и добавим их в строку выражения, пока не дойдем до открытой круглой скобки, и мы также вытолкнем открытую скобку из стека операторов.
- Строка выражения: A B + C D E / * -
- Стек операторов:
- Оставшееся выражение: + F
Следующий токен - это оператор «+», поэтому поместите его в стек.
- Строка выражения: A B + C D E / * -
- Стек операторов: +
- Оставшееся выражение: F
Следующий токен - это операнд «F». Добавьте его в строку выражения.
- Строка выражения: A B + C D E / * - F
- Стек операторов: +
- Оставшееся выражение:
Поскольку мы обработали все инфиксное выражение, теперь нужно очистить стек операторов, вытащив все оставшиеся операторы и добавив их в строку выражения.
Здесь у нас есть оператор «+» в стеке, поэтому мы извлечем оператор «+» из стека и добавим его в строку выражения. Таким образом, результирующее выражение Postfix будет выглядеть так, как показано ниже,
Окончательное выражение Postfix: A B + C D E / * - F +
Надеюсь, вы поймете, если нет, дайте мне знать в комментариях.
✉️ Подпишитесь на рассылку еженедельно Email Blast 🐦 Подпишитесь на CodeBurst на Twitter , просмотрите 🗺️ Дорожная карта веб-разработчиков на 2018 год и 🕸️ Изучите веб-разработку с полным стеком .