Использование стека для вычисления выражений


Download 0.82 Mb.
bet1/2
Sana30.04.2023
Hajmi0.82 Mb.
#1411899
TuriРешение
  1   2
Bog'liq
Си Стек Выражения

Использование стека для вычисления выражений

  • Стеки и постфиксная нотация
  • Стек
  • Стек – это линейная структура данных, в которой добавление и удаление элементов возможно только с одного конца (вершины стека). Stack = кипа, куча, стопка (англ.)
  • LIFO = Last In – First Out
  • Операции со стеком:
    • добавить элемент на вершину (Push = втолкнуть);
    • снять элемент с вершины (Pop = вылететь со звуком).
  • Пример задачи
  • Задача: вводится символьная строка, в которой записано выражение со скобками трех типов: [], {} и (). Определить, верно ли расставлены скобки (не обращая внимания на остальные символы). Примеры:
  • [()]{} ][ [({)]}
  • Упрощенная задача: то же самое, но с одним видом скобок.
  • Можно ли решить исходную задачу так же, но с тремя счетчиками?
  • ?
  • [ ( { ) ] }
  • (: 0 1 0
  • [: 0 1 0
  • {: 0 1 0
  • [ ( { ) ] }
  • ( ( ) ) ( )
  • 1 2 1 0 1 0
  • ( ( ) ) ( )
  • ( ( ) ) ) (
  • 1 2 1 0 -1 0
  • ( ( ) ) ) (
  • ( ( ) ) (
  • 1 2 1 0 1
  • ( ( ) ) (
  1   2




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling