PythonPython · Chapterبەش 11 · Lectureوانە 11.1

Stacks: Last In, First Outستاکەکان: دوایین هاتوو، یەکەم دەرچوو

Data structures and the stack: push, pop and peek, overflow and underflow, a Python list as a stack, reversing text, matching brackets, infix, prefix and postfix notation, converting infix to postfix and evaluating postfix with a stack.

و : push، pop و peek، و ، وەک ، پێچەوانەکردنەوەی دەق، یەکگرتنەوەی کەوانەکان، ، و ، گۆڕینی بۆ و ژماردنی بە .

24 min read23 خولەک خوێندنەوە · 20 stepsهەنگاو

What you will learnچی فێر دەبیت

Explain what a data structure is and what makes a stack LIFO.
Use push, pop, peek, is_empty and size, and recognise overflow and underflow.
Build a stack from a Python list and wrap it in functions with a size limit.
Use a stack to reverse text and to check brackets.
Write expressions in infix, prefix and postfix, convert infix to postfix and evaluate postfix, by hand and in Python.

ڕوون بکەیتەوە چییە و چی دەکات بە LIFO.
push، pop، peek، ⁦is_empty⁩ و size بەکار بهێنیت و و بناسیتەوە.
لە دروست بکەیت و لە سنووردار بیپێچیتەوە.
بەکار بهێنیت بۆ پێچەوانەکردنەوەی دەق و پشکنینی کەوانەکان.
بە ، و بنووسیت، بگۆڕیت بۆ و بژمێریت، بە دەست و بە .

What is a data structure?پێکهاتەی دراوە چییە؟

This chapter is about data structures. A data structure is a way to keep many data items together in an organised form, together with the operations you can do on them: add an item, remove one, find one, look at the first or the last. You already know several: a string keeps characters in order and lets you index and slice them; a list keeps any values and adds append(), pop() and sort().

ئەم بەشە دەربارەی . ڕێگایەکە بۆ هەڵگرتنی زۆر پێکەوە بە شێوەیەکی ڕێکخراو، لەگەڵ ئەو کارانەی دەتوانیت لەسەریان بیکەیت: زیادکردنی ، لابردنی یەکێک، دۆزینەوەی یەکێک، سەیرکردنی یەکەم یان دوایین. چەندانێکیان پێشتر دەناسیت. بە ڕیز هەڵدەگرێت و ڕێگەت پێ دەدات بە بیانگریت، لەتیان بکەیت و بە دوایاندا بگەڕێیت؛ هەر هەڵدەگرێت و append()، pop()، sort() و زیاتری لەسەر زیاد دەکات.

Definitionپێناسە

A way of organising data in memory so that a program can use it efficiently, for example a list, stack, queue, tree, heap or dictionary.

شێوازێکی ڕێکخستنی لە بۆ ئەوەی بە کارایی بەکاری بهێنێت، بۆ نموونە ، ، ، ، یان .

Data structure	Where you meet itلە کوێ دەیبینیت
string, list, tuple, set, dictionary، ، ، ،	earlier lessons: Which one should I use?وانەکانی پێشوو: کامیان بەکار بهێنم؟
stack	this lessonئەم وانەیە
queue and deque و	the next lesson, Queues and dequesوانەی داهاتوو، کیووەکان و کیووە دووسەرەکان
heap (for a priority queue) (بۆ )	Why a priority queue?بۆچی کیووی پێشینەیی؟
tree and graph و	search problems in AIکێشەکانی گەڕان لە زیرەکیی دەستکرددا
array, linked list, sparse matrix، linked list و کەمدانە (sparse matrix)	named here only; other languages and later coursesتەنها لێرە ناویان دەهێنرێت؛ زمانەکانی تر و کۆرسەکانی دواتر

A linear data structure keeps its items in a sequence, one after another: a string, a list, a stack, a queue. A non-linear one lets an item branch to several others, like a tree or a graph. Python has no separate stack or queue type: a list works as a stack, and collections.deque as a queue. Many languages use these two structures, so it pays to know them well.

هێڵی بە ڕیزبەندی هەڵدەگرێت، یەک لە دوای یەک: ، ، ، . جۆری ناهێڵی ڕێگە دەدات لق ببێتەوە بۆ چەند تر، وەک یان . جۆرێکی جیای بۆ یان نییە: وەک کار دەکات و collections.deque وەک . زۆر زمان ئەم دوو پێکهاتەیە بەکار دەهێنن، بۆیە باشە بە باشی بیانناسیت.

The chapter has four lessons: stacks (this one), queues and deques, then two lessons on algorithms: sorting and searching.

ئەم بەشە چوار وانەی هەیە: (ئەم وانەیە)، کیووەکان و کیووە دووسەرەکان، پاشان دوو وانە دەربارەی : ڕیزکردن و گەڕان.

The stack: last in, first outستاک: دوایین هاتوو، یەکەم دەرچوو

A stack is a linear data structure with only one open end, called the top. New items are put on the top, and items are taken off the top. So the item that went in last comes out first: LIFO, Last In, First Out.

هێڵییە کە تەنها یەک سەری کراوەی هەیە، پێی دەوترێت سەر. نوێ دەخرێنە سەرەوە و لە سەرەوەش لادەبرێن. کەواتە ئەو دوایین جار چووە ژوورەوە یەکەم جار دێتە دەرەوە: LIFO، ⁦Last In, First Out⁩، واتە دوایین هاتوو، یەکەم دەرچوو.

Definitionپێناسە

A data structure in which the last item added is the first one taken out (LIFO), like a pile of books. Depth-first search keeps its frontier in a stack.

کە تێیدا دوایین دانە کە دەخرێتە سەری یەکەم دانەیە کە دەردەهێنرێت ⁦(LIFO)⁩، وەک کۆمەڵێک کتێب کە لەسەر یەک دانراون. لە هەڵدەگرێت.

Tea glasses at the tea houseپەرداخی چا لە چایخانەدا

At a tea house the clean tea glasses are stacked on a tray. The boy who serves tea puts each washed glass on top of the pile and always takes the top one. The first glass he put down is at the bottom and will be used last. Folded mattresses in a cupboard, plastic chairs stacked after a wedding and bangles on a wrist work the same way.

لە چایخانەدا پەرداخە پاکەکانی چا لەسەر سینییەک لەسەر یەک کەڵەکە دەکرێن. ئەو کوڕەی چا دەگێڕێت هەر پەرداخێکی شوشتراو دەخاتە سەر کەڵەکەکە و هەمیشە ئەوەی سەرەوە هەڵدەگرێت. یەکەم پەرداخ کە داینا لە خوارەوەیە و دوایین جار بەکار دێت. دۆشەکی قەدکراو لە دۆڵابدا، کورسیی پلاستیکی لەسەر یەک دوای ئاهەنگێک و بازن لە مەچەکدا بە هەمان شێوە کار دەکەن.

Where the analogy stops workingسنووری ئەم نموونەیە

Real piles allow cheating: you can pull a glass from the middle. A stack in a program cannot: only the top is ever reachable.

کەڵەکەی ڕاستەقینە ڕێگە بە فێڵ دەدات: دەتوانیت پەرداخێک لە ناوەڕاستەوە دەربهێنیت. لە ناتوانێت: هەمیشە تەنها سەرەوەکەی دەگاتێ.

Push puts a glass on the top; pop takes the top one off. The last glass in is the first one out.push پەرداخێک دەخاتە سەرەوە؛ pop ئەوەی سەرەوە هەڵدەگرێت. دوایین پەرداخ کە هات یەکەمیان دەردەچێت.CêIT

کۆرسی داتا سترەکچەر و ئالگۆریتم 3 - StacksAmeers Code Complex · Kurdish (Sorani)کوردی (سۆرانی) · 577 viewsبینین · 41 likesلایک · Partبەشی 0:00–3:27 (ofلە 16:50)
A Kurdish (Sorani) explanation of the stack: one open end, last in first out, push and pop.
ڕوونکردنەوەیەکی کوردی (سۆرانی) بۆ : تەنها یەک سەری کراوەی هەیە، دوایین هاتوو یەکەم دەڕوات، push و pop.
Kurdish (Sorani), watch 0:00–3:27: the basics of the stack. The rest of the video writes it in C++.
ڤیدیۆیەکی کوردی (سۆرانی)، لە ⁦0:00⁩ تا ⁦3:27⁩ سەیر بکە: بنەماکانی . باقیی ڤیدیۆکە بە ⁦C++⁩ دەینووسێت.

Where computers use stacksکۆمپیوتەر لە کوێ ستاک بەکار دەهێنێت

Whenever the newest thing must be handled first, a stack is the right tool:

هەر کاتێک نوێترین شت دەبێت یەکەم جار چارەسەر بکرێت، ئامرازی گونجاوە:

Undo and redo in a text or picture editor: every change is pushed; Undo pops the most recent one (and pushes it onto a second stack, so that Redo can bring it back).
The browser's Back button: you visit page P1, then P2, then P3. Back takes you to P2, and Back again to P1, the opposite order of your visits.
Reversing a text: push every character, then pop them all.
Checking brackets: a compiler or interpreter makes sure every ( has its ), properly nested.
Function calls: Python keeps the frames of unfinished calls on the call stack; a traceback, also called a stack trace, prints that stack (Reading a traceback).
Depth-first search in AI keeps the places still to visit on a stack: you will meet it in Depth-first search.

و لە یان : هەموو گۆڕانکارییەک دەخرێتە سەر ؛ Undo نوێترینیان هەڵدەگرێت (و دەیخاتە سەر دووەم، بۆ ئەوەی Redo بیگەڕێنێتەوە).
دوگمەی Backـی : سەردانی لاپەڕەی ⁦P1⁩، پاشان ⁦P2⁩، پاشان ⁦P3⁩ دەکەیت. Back دەتباتەوە بۆ ⁦P2⁩ و دیسان Back بۆ ⁦P1⁩، پێچەوانەی ڕیزبەندیی سەردانەکانت.
پێچەوانەکردنەوەی دەقێک: هەموو بخەرە سەر، پاشان هەموویان هەڵبگرە.
پشکنینی کەوانەکان: یان دڵنیا دەبێتەوە کە هەموو (ـێک )ـی خۆی هەیە و بە دروستی لەناو یەکدان.
بانگکردنی : چوارچێوەی بانگکردنە تەواونەبووەکان لەسەر ستاکی بانگکردن هەڵدەگرێت؛ کە پێی دەوترێت ⁦stack trace⁩، ئەو چاپ دەکات (خوێندنەوەی ڕێچکەیەکی هەڵە).
لە زیرەکیی دەستکرددا ئەو شوێنانەی هێشتا سەردانیان نەکراوە لەسەر هەڵدەگرێت: لە گەڕانی قووڵایی دەیبینیت.

Tipئامۆژگاری

Think about it. How does a compiler or an interpreter handle function calls? With the call stack: each call pushes a frame and each return pops one. How can an operating system keep track of free memory? One simple way keeps the free blocks on a stack: a freed block is pushed and the next request pops one ("last freed, first reused"). Real systems combine several structures.

بیری لێ بکەرەوە. یان چۆن مامەڵە لەگەڵ بانگکردنی دەکات؟ بە : هەر بانگکردنێک چوارچێوەیەک دەخاتە سەر و هەر returnـێک یەکێک هەڵدەگرێت. چۆن ئاگای لە بەتاڵ دەبێت؟ ڕێگایەکی سادە بلۆکە بەتاڵەکان لەسەر هەڵدەگرێت: بلۆکێکی ئازادکراو دەخرێتە سەر و داواکاریی داهاتوو یەکێک هەڵدەگرێت («دوایین ئازادکراو، یەکەم بەکارهاتوو»). سیستەمە ڕاستەقینەکان چەند پێکهاتەیەک تێکەڵ دەکەن.

Stack operations: push, pop, peekکارەکانی ستاک: push، pop، peek

A stack needs only a few operations. The two main ones are push (put an item on the top) and pop (take the top item off and give it back). The helpers look without changing anything.

تەنها پێویستی بە چەند کارێکی کەمە. دوو سەرەکییەکەیان pushـن (دانانی لە سەرەوە) و pop (هەڵگرتنی سەرەوە و گەڕاندنەوەی). یارمەتیدەرەکان تەنها سەیر دەکەن بەبێ ئەوەی هیچ بگۆڕن.

Operationکار	What it doesچی دەکات
`push(x)`	puts `x` on the top`x` دەخاتە سەرەوە
`pop()`	removes the top item and returns it سەرەوە لادەبات و دەیگەڕێنێتەوە
`peek()`	returns the top item without removing it (also called top) سەرەوە دەگەڕێنێتەوە بەبێ لابردنی (پێشی دەوترێت top)
`is_empty()`	`True` when there is no itemکاتێک هیچ نییە `True`ـە
`size()`	the number of itemsژمارەی
`is_full()`	only for a stack with a fixed size: `True` when no item fits any moreتەنها بۆ بە قەبارەی جێگیر: کاتێک هیچ جێی نابێتەوە `True`ـە

Two things can go wrong. Pushing onto a full stack is an overflow; popping from an empty stack is an underflow. A stack in a real machine or in many languages has a fixed size, so it can be full. A Python list grows as long as there is memory, so a list-based stack overflows only if we give it a limit ourselves, as the next screens do.

دوو شت دەکرێت هەڵە بچن. push بۆ سەر پڕ ؛ pop لە بەتاڵ . لە ئامێرێکی ڕاستەقینەدا یان لە زۆر زماندا قەبارەیەکی جێگیری هەیە، بۆیە دەکرێت پڕ ببێت. تا هەبێت گەورە دەبێت، بۆیە کە لەسەر دروستکراوە تەنها کاتێک دەبێت کە خۆمان سنوورێکی بۆ دابنێین، وەک پەڕەکانی داهاتوو دەیکەن.

Definitionپێناسە

Trying to add an item to a or that is already full, because the structure has a fixed size. Python lists and deques grow as needed, so a program meets overflow only when it sets a limit itself (an is_full() check).

هەوڵدان بۆ زیادکردنی دانەیەک بۆ یان کە پێشتر پڕ بووە، چونکە قەبارەی پێکهاتەکە جێگیرە. و بە پێی پێویست گەورە دەبن، بۆیە تەنها کاتێک تووشی ئەمە دەبێت کە خۆی سنوورێک دابنێت (پشکنینی is_full()).

Definitionپێناسە

Trying to remove or read an item from an empty or . In Python pop() on an empty list or deque raises IndexError, so a program checks is_empty() first.

هەوڵدان بۆ لابردن یان خوێندنەوەی دانەیەک لە یان بەتاڵ. لە pop() لەسەر یان بەتاڵ IndexError دروست دەکات، بۆیە سەرەتا is_empty() دەپشکنێت.

A Python list as a stackلیستێکی Python وەک ستاک

A Python list already has what a stack needs, if you use its end as the top: append() pushes, pop() with no index pops, and stack[-1] peeks. len(stack) is the size and not stack is True when it is empty. Both append() and pop() work at the end of the list, where nothing else has to move, so they are fast.

پێشتر ئەوەی هەیە کە پێویستی پێیەتی، ئەگەر کۆتاییەکەی وەک سەر بەکار بهێنیت: append() push دەکات، pop() بەبێ pop دەکات و stack[-1] peek دەکات. len(stack) قەبارەکەیەتی و not stack کاتێک بەتاڵە Trueـە. هەردوو append() و pop() لە کۆتایی کار دەکەن، کە هیچ شتێکی تر پێویست ناکات بجووڵێت، بۆیە خێران.

push, peek and pop with a listpush، peek و pop بە لیستێکlist_stack.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

glasses = []                  # an empty stack: the end of the list is the top
glasses.append("glass 1")     # push
glasses.append("glass 2")     # push
glasses.append("glass 3")     # push
print(glasses)
print("top:", glasses[-1])    # peek: look, do not remove
print("popped:", glasses.pop())   # pop: remove the top
print(glasses)

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 1

The end of the list is the top. Python's own tutorial uses lists this way.

کۆتایی سەرەکەیە. فێرکاریی خودی بەم شێوەیە بەکار دەهێنێت.

Lineدێڕی 6

[-1] is the last element: the top.

[-1] دوایین : سەرەکە.

Lineدێڕی 7

pop() with no index removes the last element and returns it.

pop() بەبێ دوایین لادەبات و دەیگەڕێنێتەوە.

A plain pop() on an empty list stops the program with an exception:

pop()ـی سادە لەسەر بەتاڵ بە دەوەستێنێت:

Popping an empty listpop لە لیستێکی بەتاڵempty_pop.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

stack = []
stack.pop()                   # nothing to take

Python Stacks - Python Tutorial for Absolute Beginners | MoshProgramming with Mosh · Englishئینگلیزی · 200K viewsبینین · 3.3K likesلایک · Partبەشی 0:00–4:12 (ofلە 4:51)
A Python list used as a stack: append() pushes, pop() removes the last item, and [-1] looks at the top.
وەک : `append()` push دەکات، `pop()` دوایین لادەبات و `[-1]` سەیری سەرەوەی دەکات.
Watch 0:00–4:12: how stacks work and a browser-history example with a Python list (append, pop, [-1]). Stops before a slip in the code that follows.
لە ⁦0:00⁩ تا ⁦4:12⁩ سەیر بکە: چۆن کار دەکەن و نموونەی مێژووی بە (`append`، `pop`، `[-1]`). پێش بچووک لە کۆدی دواتردا ڕادەوەستێت.

A Python list as a stackلیستێکی Python وەک ستاک

Stack functions with overflow and underflowکردارەکانی ستاک لەگەڵ سەرڕێژبوون و ژێرڕێژبوون

Let us wrap the list in small functions, one for each operation, and give the stack a fixed size: a tray that holds only three glasses. push() refuses a fourth glass (overflow) and pop() reports an empty tray (underflow) instead of crashing. The main program prints the stack, top first, after each step:

با لەناو چەند بچووکدا دابنێین، بۆ هەر کارێک یەکێک و قەبارەیەکی جێگیر بە بدەین: سینییەک کە تەنها سێ پەرداخ دەگرێت. push() پەرداخی چوارەم ڕەت دەکاتەوە () و pop() لەبری کەوتن ڕادەگەیەنێت کە سینییەکە بەتاڵە (). سەرەکی دوای هەر هەنگاوێک چاپ دەکات، سەرەوە یەکەم:

A stack of tea glasses with a limitستاکێک لە پەرداخی چا بە سنوورstack_functions.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

LIMIT = 3                     # this tray holds at most 3 glasses

def is_empty(stack):
    return len(stack) == 0

def is_full(stack):
    return len(stack) == LIMIT

def push(stack, item):
    if is_full(stack):
        print("Overflow: the stack is full,", item, "was not added")
    else:
        stack.append(item)

def pop(stack):
    if is_empty(stack):
        print("Underflow: the stack is empty")
        return None
    return stack.pop()

def peek(stack):
    if is_empty(stack):
        return None
    return stack[-1]

def size(stack):
    return len(stack)

def show(stack):
    print("   top ->", ", ".join(reversed(stack)) if stack else "(empty)")

tray = []
push(tray, "glass 1"); show(tray)
push(tray, "glass 2"); show(tray)
print("size:", size(tray), " top:", peek(tray))
print("popped:", pop(tray)); show(tray)
push(tray, "glass 3"); show(tray)
push(tray, "glass 4"); show(tray)
push(tray, "glass 5")         # the fourth glass on a tray for three
while not is_empty(tray):
    print("popped:", pop(tray))
pop(tray)                     # one pop too many

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 1

The limit makes overflow possible.

سنوورەکە دەکاتە شتێکی ڕوودەر.

Lineدێڕی 9-13

push() checks is_full() first.

push() سەرەتا is_full() دەپشکنێت.

Lineدێڕی 15-19

pop() checks is_empty() first and returns None for an empty stack.

pop() سەرەتا is_empty() دەپشکنێت و بۆ بەتاڵ None دەگەڕێنێتەوە.

Lineدێڕی 29-30

reversed() shows the top first, as the stack looks from above.

reversed() سەرەوە یەکەم پیشان دەدات، وەک ئەوەی لە سەرەوە دەبینرێت.

Lineدێڕی 40-41

Pop until the tray is empty: the glasses come off in reverse order.

pop بکە تا سینییەکە بەتاڵ دەبێت: پەرداخەکان بە پێچەوانەوە هەڵدەگیرێن.

Quick checkپشکنینی خێراIn the program above, what does the call push(tray, "glass 5") do?لە سەرەوەدا بانگکردنی push(tray, "glass 5") چی دەکات؟It removes glass 1 to make roomپەرداخی 1 لادەبات بۆ ئەوەی جێ بکاتەوەIt prints an overflow message and leaves the tray as it wasپەیامی سەرڕێژبوون چاپ دەکات و سینییەکە وەک خۆی دەهێڵێتەوەIt adds glass 5 on topپەرداخی 5 دەخاتە سەرەوە

Use 1: reversing a textبەکارهێنانی یەکەم: پێچەوانەکردنەوەی دەق

Because a stack gives items back in the opposite order, reversing is easy: push every character from the first to the last, then pop until the stack is empty. The last character comes out first.

لەبەر ئەوەی بە پێچەوانەی ڕیزبەندییەکەیان دەگەڕێنێتەوە، پێچەوانەکردنەوە ئاسانە: هەموو لە یەکەمەوە تا دوایین push بکە، پاشان pop بکە تا بەتاڵ دەبێت. دوایین یەکەم جار دێتە دەرەوە.

Reverse a text with a stackپێچەوانەکردنەوەی دەق بە ستاکێکreverse_text.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def reverse(text):
    stack = []
    for ch in text:           # push every character
        stack.append(ch)
    result = ""
    while stack:              # pop until the stack is empty
        result += stack.pop()
    return result

print(reverse("Erbil"))
print(reverse("stressed"))
print(reverse("نان و چا"))

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 3-4

Push: E, r, b, i, l. The top is now l.

⁦push: E⁩، r، b، i، l. ئێستا سەرەکە lـە.

Lineدێڕی 6-7

Pop until empty: l, i, b, r, E.

pop تا بەتاڵ دەبێت: l، i، b، r، E.

The Kurdish phrase is reversed letter by letter too, so the words come out back to front. In real Python code text[::-1] reverses a string in one step (Slicing); the stack version shows the idea that compilers and editors use.

دەستەواژە کوردییەکەش پیت بە پیت پێچەوانە دەبێتەوە، بۆیە وشەکان بە پێچەوانەوە دەردەچن. لە کۆدی ڕاستەقینەی text[::-1] بە یەک هەنگاو پێچەوانە دەکاتەوە (لەتکردن)؛ وەشانی ئەو بیرۆکەیە پیشان دەدات کە و دەستکاریکەرەکان بەکاری دەهێنن.

Use 2: do the brackets match?بەکارهێنانی دووەم: ئایا کەوانەکان یەکدەگرنەوە؟

In ((2+3)*(4/2))+2 every opening bracket must have a closing one, and pairs must be nested properly. A stack checks this in one pass from left to right:

لە ((2+3)*(4/2))+2ـدا هەموو کەوانەیەکی کردنەوە دەبێت کەوانەیەکی داخستنی هەبێت و جووتەکان دەبێت بە دروستی لەناو یەکدا بن. ئەمە بە یەک جار تێپەڕین لە چەپەوە بۆ ڕاست دەپشکنێت:

The rulesیاساکان

Opening bracketکەوانەی کردنەوە
Push it: it waits for its partner.
pushـی بکە: چاوەڕێی هاوجووتەکەی دەکات.
Closing bracketکەوانەی داخستن
Pop. If the stack is empty, or the popped bracket is of another kind, the brackets do not match.
pop بکە. ئەگەر بەتاڵ بێت، یان کەوانە pop کراوەکە جۆرێکی تر بێت، کەوانەکان یەک ناگرنەوە.
Anything elseهەر شتێکی تر
Ignore numbers and operators.
ژمارە و پشتگوێ بخە.
At the endلە کۆتاییدا
The brackets match only if the stack is empty.
کەوانەکان تەنها کاتێک یەکدەگرنەوە کە بەتاڵ بێت.

Matching the brackets of `((2+3)*(4/2))+2`یەکگرتنەوەی کەوانەکانی `((2+3)*(4/2))+2`
Symbolهێما	Actionکار	Stack after it دوای ئەو
`(`	push`push`	`(`
`(`	push`push`	`((`
`2 + 3`	ignoreپشتگوێ	`((`
`)`	pop: `(` matches `)`pop: `(` لەگەڵ `)` یەکدەگرێتەوە	`(`
`*`	ignoreپشتگوێ	`(`
`(`	push`push`	`((`
`4 / 2`	ignoreپشتگوێ	`((`
`)`	pop: matchespop: یەکدەگرێتەوە	`(`
`)`	pop: matchespop: یەکدەگرێتەوە	emptyبەتاڵ
`+ 2`	ignoreپشتگوێ	emptyبەتاڵ
endکۆتایی	stack empty: balanced بەتاڵە: هاوسەنگ	✓

Bracket checking with a stackپشکنینی کەوانە بە ستاکێکbrackets.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

PAIRS = {")": "(", "]": "[", "}": "{"}

def is_balanced(expr, show=False):
    stack = []
    for ch in expr:
        if ch in "([{":
            stack.append(ch)                  # an opening bracket waits on the stack
        elif ch in ")]}":
            if not stack or stack.pop() != PAIRS[ch]:
                return False                  # nothing to close, or the wrong kind
        else:
            continue                          # numbers and operators do not matter
        if show:
            print(f"  {ch}   stack: {''.join(stack) or '(empty)'}")
    return len(stack) == 0                    # every bracket must be closed

print(is_balanced("((2+3)*(4/2))+2", show=True))
for e in ["[(5+1)*2]", "(5+2]*3", "(4+(3*2)", "2+3)*(4"]:
    print(f"{e:12} {is_balanced(e)}")

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 1

For each closing bracket, the opening bracket it needs.

بۆ هەر کەوانەیەکی داخستن، ئەو کەوانەی کردنەوەیەی پێویستیەتی.

Lineدێڕی 9-10

Nothing to close, or the wrong kind: not balanced.

هیچ شتێک نییە دابخرێت، یان جۆرێکی هەڵەیە: هاوسەنگ نییە.

Lineدێڕی 15

Brackets still waiting at the end, as in (4+(3*2), are an error too.

ئەو کەوانانەی لە کۆتاییدا هێشتا چاوەڕێن، وەک لە (4+(3*2)ـدا، هەڵەن.

Three ways to write an expressionسێ ڕێگا بۆ نووسینی دەربڕینێک

We normally write an operator between its two operands: a + b. This is infix notation. It needs precedence rules and brackets: in a + b * c you multiply first, because * comes before + (Which operator goes first?). There are two other ways:

ئێمە بە ئاسایی لە نێوان دوو دەنووسین: a + b. ئەمە . پێویستی بە یاساکانی پێشینەیی و کەوانە هەیە: لە a + b * cـدا سەرەتا لێکدان دەکەیت، چونکە * پێش + دێت (کام کارپێکەر یەکەم جار؟). دوو ڕێگای تر هەن:

Prefix (Polish) notation puts the operator before its operands: + a b. The Polish logician Jan Łukasiewicz introduced it in 1924.
Postfix (reverse Polish) notation puts the operator after its operands: a b +. For many years HP calculators worked this way.

(پۆڵەندی) پێش دادەنێت: + a b. لۆجیکزانی پۆڵەندی Jan Łukasiewicz لە ساڵی ⁦1924⁩ دایهێنا.
(پۆڵەندیی پێچەوانە) دوای دادەنێت: a b +. بۆ چەندین ساڵ HP بەم شێوەیە کاریان دەکرد.

The same expressions in the three notations (checked with the programs on the next screens)هەمان بە سێ نیشانەکە (بە پەڕەکانی داهاتوو پشکنراون)
Infix	Prefix	Postfix
`a + b * c`	`+ a * b c`	`a b c * +`
`(a + b) * c`	`* + a b c`	`a b + c *`
`(7 - 2) * (3 + 1)`	`* - 7 2 + 3 1`	`7 2 - 3 1 + *`
`(a + b) * (c - d) / e`	`/ * + a b - c d e`	`a b + c d - * e /`

Look at (a + b) * c and a + b * c: in infix only the brackets tell them apart, but in postfix they are simply different orders, a b + c * and a b c * +. Postfix and prefix need no brackets and no precedence rules: the operators already stand in the order they are worked out, so one pass from left to right is enough. That is why a stack-based program can evaluate them so easily.

سەیری (a + b) * c و a + b * c بکە: لە تەنها کەوانەکان جیایان دەکەنەوە، بەڵام لە تەنها دوو ڕیزبەندیی جیاوازن، a b + c * و a b c * +. و پێویستیان بە کەوانە و یاسای پێشینەیی نییە: پێشتر بەو ڕیزبەندییە وەستاون کە دەژمێردرێن، بۆیە یەک جار تێپەڕین لە چەپەوە بۆ ڕاست بەسە. لەبەر ئەمە کە بەکار دەهێنێت دەتوانێت بە ئاسانی بیانژمێرێت.

Reverse Polish Notation and The Stack - ComputerphileComputerphile · Englishئینگلیزی · 327K viewsبینین · 10K likesلایک · Partبەشی 0:54–9:08 (ofلە 13:32)
Infix, prefix and postfix notation, why postfix needs no brackets, and how a stack works out a postfix expression.
، و ، بۆچی پێویستی بە کەوانە نییە و چۆن ئەنجامی بە دەدۆزێتەوە.
Watch 0:54–9:08: infix and prefix (0:54), postfix (2:34) and why postfix needs no brackets or precedence rules (6:11).
لە ⁦0:54⁩ تا ⁦9:08⁩ سەیر بکە: و ⁦(0:54)⁩، ⁦(2:34)⁩ و بۆچی پێویستی بە کەوانە یان یاساکانی نییە ⁦(6:11)⁩.

Infix to postfix with an operator stackلە نیشانەی ناوگرەوە بۆ نیشانەی پاشگر بە ستاکێکی کارپێکەر

A computer can turn infix into postfix with a stack that holds operators and opening brackets while a string collects the output. This is the idea of the shunting-yard algorithm, published by Edsger Dijkstra in 1961 (operators wait on a side track, like railway wagons in a shunting yard). Read the expression from left to right, one symbol at a time:

دەتوانێت بگۆڕێت بۆ بە کە و کەوانەی کردنەوە هەڵدەگرێت لە کاتێکدا کۆ دەکاتەوە. ئەمە بیرۆکەی ⁦shunting-yard⁩ـە کە ⁦Edsger Dijkstra⁩ لە ساڵی ⁦1961⁩ بڵاوی کردەوە ( لەسەر هێڵێکی لاوەکی چاوەڕێ دەکەن، وەک فارگۆنی شەمەندەفەر لە ئیستگەی جیاکردنەوەدا). لە چەپەوە بۆ ڕاست بخوێنەوە، لە هەر جارێکدا یەک هێما:

The algorithmئەلگۆریزمەکە

Operandکارپێکراو
A letter or a number goes straight to the output.
پیت یان ژمارە ڕاستەوخۆ دەچێتە .
Opening bracketکەوانەی کردنەوە
Push (.
( push بکە.
Closing bracketکەوانەی داخستن
Pop operators to the output until ( comes off; drop both brackets.
pop بکە بۆ تا ( دێتە دەرەوە؛ هەردوو کەوانەکە فڕێ بدە.
Operatorکارپێکەر
First pop to the output every operator on the top that has higher or equal precedence (stop at (), then push the new one.
سەرەتا هەموو سەرەوە کە پێشینەیی بەرزتر یان یەکسانی هەیە pop بکە بۆ (لە (ـدا بوەستە)، پاشان نوێیەکە push بکە.
Endکۆتایی
Pop everything left on the stack to the output.
هەموو ئەوەی لەسەر ماونەتەوە pop بکە بۆ .

Converting a * (b + c) - d: the stack holds the operators until their turn comes.گۆڕینی a * (b + c) - d: هەڵدەگرێت تا نۆرەیان دێت.CêIT

Quick checkپشکنینی خێراWhile converting a - b * c, the symbol * arrives and the stack holds -. What happens?لە کاتی گۆڕینی a - b * cـدا هێمای * دێت و -ـی تێدایە. چی ڕوو دەدات؟- is popped to the output firstسەرەتا - بۆ دەرخستە pop دەکرێت* goes straight to the output* ڕاستەوخۆ دەچێتە دەرخستە* is pushed on top of -, because * has higher precedence* لەسەر - push دەکرێت، چونکە * پێشینەیی بەرزتری هەیە

Infix to postfix with an operator stackلە نیشانەی ناوگرەوە بۆ نیشانەی پاشگر بە ستاکێکی کارپێکەر

Step by step: a longer expressionهەنگاو بە هەنگاو: دەربڕینێکی درێژتر

A longer worked example, (a + b) * (c - d) / e, written with a space between symbols. Watch the /: the * on the top has equal precedence, so * goes out first. That keeps a * b / c working from left to right, as in ordinary maths.

نموونەیەکی درێژتر، هەنگاو بە هەنگاو: (a + b) * (c - d) / e، کە بۆشایی لە نێوان هێماکانیدایە. سەیری / بکە: *ـی سەرەوە پێشینەیی یەکسانی هەیە، بۆیە * یەکەم جار دەردەچێت. ئەمە وا دەکات a * b / c لە چەپەوە بۆ ڕاست بژمێردرێت، وەک بیرکاریی ئاسایی.

`(a + b) * (c - d) / e` → `a b + c d - * e /`گۆڕینی `(a + b) * (c - d) / e` بۆ `a b + c d - * e /`
Symbolهێما	Actionکار	Stack (top on the right) (سەرەوە لای ڕاست)	Output
`(`	push`push`	`(`
`a`	to the outputبۆ	`(`	`a`
`+`	push, because the top is `(`push، چونکە سەرەوە `(`ـە	`( +`	`a`
`b`	to the outputبۆ	`( +`	`a b`
`)`	pop `+`, drop `(+` pop بکە، `(` فڕێ بدە		`a b +`
`*`	push`push`	`*`	`a b +`
`(`	push`push`	`* (`	`a b +`
`c`	to the outputبۆ	`* (`	`a b + c`
`-`	push, because the top is `(`push، چونکە سەرەوە `(`ـە	`* ( -`	`a b + c`
`d`	to the outputبۆ	`* ( -`	`a b + c d`
`)`	pop `-`, drop `(-` pop بکە، `(` فڕێ بدە	`*`	`a b + c d -`
`/`	`` has equal precedence: pop it, then push `/` پێشینەیی یەکسانی هەیە: popـی بکە، پاشان `/` push بکە	`/`	`a b + c d - *`
`e`	to the outputبۆ	`/`	`a b + c d - * e`
endکۆتایی	pop everythingهەموو شتێک pop بکە		`a b + c d - * e /`

Infix to postfix with an operator stackلە نیشانەی ناوگرەوە بۆ نیشانەی پاشگر بە ستاکێکی کارپێکەر

The conversion in Pythonگۆڕینەکە لە Pythonـدا

The function follows the five rules exactly. To keep it short, the symbols in the input are separated by spaces, so split() gives the tokens; a dictionary holds the precedence of each operator.

ڕێک پێنج یاساکە جێبەجێ دەکات. بۆ ئەوەی کورت بێت، هێماکانی بە بۆشایی جیا کراونەتەوە، بۆیە split() پارچەکان دەدات؛ پێشینەیی هەر هەڵدەگرێت.

Infix to postfixنیشانەی ناوگر بۆ نیشانەی پاشگرinfix_postfix.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

PRECEDENCE = {"+": 1, "-": 1, "*": 2, "/": 2}

def to_postfix(infix, show=False):
    output = []
    stack = []
    for token in infix.split():
        if token == "(":
            stack.append(token)
        elif token == ")":
            while stack[-1] != "(":            # pop until the opening bracket
                output.append(stack.pop())
            stack.pop()                        # drop the "(" itself
        elif token in PRECEDENCE:
            while (stack and stack[-1] != "("
                   and PRECEDENCE[stack[-1]] >= PRECEDENCE[token]):
                output.append(stack.pop())     # higher or equal goes out first
            stack.append(token)
        else:
            output.append(token)               # an operand goes straight out
        if show:
            print(f"{token:3} | {' '.join(stack):9} | {' '.join(output)}")
    while stack:                               # at the end: empty the stack
        output.append(stack.pop())
    return " ".join(output)

print(to_postfix("( a + b ) * ( c - d ) / e", show=True))
print()
for e in ["a + b * c", "( a + b ) * c", "a * ( b + c ) - d",
          "( 7 - 2 ) * ( 3 + 1 )", "p / q - r", "a - b - c"]:
    print(f"{e:23} ->  {to_postfix(e)}")

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 1

Bigger number = higher precedence.

ژمارەی گەورەتر = پێشینەیی بەرزتر.

Lineدێڕی 9-12

A closing bracket pops operators until the opening bracket, then drops it.

کەوانەی داخستن pop دەکات تا کەوانەی کردنەوە، پاشان فڕێی دەدات.

Lineدێڕی 14-17

Pop higher or equal precedence first, then push.

سەرەتا پێشینەیی بەرزتر یان یەکسان pop بکە، پاشان push بکە.

Lineدێڕی 22-23

At the end, empty the stack into the output.

لە کۆتاییدا بەتاڵ بکەرەوە بۆ ناو .

The last line, a - b - c → a b - c -, shows why equal precedence must be popped: a - b - c means (a - b) - c. If the second - waited on the stack, the result would be a b c - -, which means a - (b - c), a different number.

دوایین دێڕ، a - b - c ← a b - c -، پیشان دەدات بۆچی پێشینەیی یەکسان دەبێت pop بکرێت: a - b - c واتە (a - b) - c. ئەگەر -ـی دووەم لەسەر چاوەڕێی بکردایە، ئەنجامەکە دەبووە a b c - -، کە واتە a - (b - c)، ژمارەیەکی جیاواز.

Infix to postfix with an operator stackلە نیشانەی ناوگرەوە بۆ نیشانەی پاشگر بە ستاکێکی کارپێکەر

Think about it: infix to prefixبیری لێ بکەرەوە: نیشانەی ناوگر بۆ نیشانەی پێشگر

The textbook asks for an algorithm that converts infix to prefix with a stack. One way reuses the postfix method on the expression read backwards:

کتێبەکە داوای دەکات کە بە بگۆڕێت بۆ . ڕێگایەک هەمان ڕێگای لەسەر بە پێچەوانە خوێندراوە بەکار دەهێنێتەوە:

Reverse the list of symbols, and swap every ( with ).
ڕیزی هێماکان پێچەوانە بکەرەوە و هەموو (ـێک لەگەڵ ) ئاڵوگۆڕ بکە.
Convert it as for postfix, but pop only operators of strictly higher precedence (for equal ones, wait).
وەک بۆ بیگۆڕە، بەڵام تەنها پێشینەیی بە تەواوی بەرزتر pop بکە (بۆ یەکسانەکان چاوەڕێ بکە).
Reverse the result.
ئەنجامەکە پێچەوانە بکەرەوە.

Infix to prefixنیشانەی ناوگر بۆ نیشانەی پێشگرinfix_prefix.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

PRECEDENCE = {"+": 1, "-": 1, "*": 2, "/": 2}

def to_prefix(infix):
    # 1. read the expression backwards and swap the brackets
    tokens = infix.split()[::-1]
    tokens = ["(" if t == ")" else ")" if t == "(" else t for t in tokens]
    # 2. convert like infix -> postfix, but pop only HIGHER precedence
    output, stack = [], []
    for token in tokens:
        if token == "(":
            stack.append(token)
        elif token == ")":
            while stack[-1] != "(":
                output.append(stack.pop())
            stack.pop()
        elif token in PRECEDENCE:
            while (stack and stack[-1] != "("
                   and PRECEDENCE[stack[-1]] > PRECEDENCE[token]):
                output.append(stack.pop())
            stack.append(token)
        else:
            output.append(token)
    while stack:
        output.append(stack.pop())
    # 3. reverse the result
    return " ".join(output[::-1])

for e in ["a + b * c", "( a + b ) * c", "( a + b ) * ( c - d ) / e", "a - b - c", "( 7 - 2 ) * ( 3 + 1 )"]:
    print(f"{e:27} ->  {to_prefix(e)}")

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 5-6

Step 1: read backwards and swap the brackets.

هەنگاوی 1: بە پێچەوانە بخوێنەوە و کەوانەکان ئاڵوگۆڕ بکە.

Lineدێڕی 18

> instead of >=: equal precedence waits.

> لەبری >=: پێشینەیی یەکسان چاوەڕێ دەکات.

Lineدێڕی 26

Step 3: reverse the output.

هەنگاوی 3: پێچەوانە بکەرەوە.

Evaluating postfix with an operand stackژماردنی نیشانەی پاشگر بە ستاکێکی کارپێکراو

To work out a postfix expression, use a stack of operands (numbers). Read the symbols from left to right:

بۆ ژماردنی بە ، لە (ژمارەکان) بەکار بهێنە. هێماکان لە چەپەوە بۆ ڕاست بخوێنەوە:

The algorithmئەلگۆریزمەکە

Numberژمارە
Push it.
pushـی بکە.
Operatorکارپێکەر
Pop two numbers. The first one popped is the right operand, the second is the left one. Work out left operator right and push the result.
دوو ژمارە pop بکە. یەکەم ژمارەی pop کراو ڕاستە، دووەمیان چەپ. left operator right بژمێرە و ئەنجامەکە push بکە.
Endکۆتایی
If exactly one number is left, it is the answer; anything else means the expression was invalid.
ئەگەر ڕێک یەک ژمارە مابێتەوە، ئەوە وەڵامەکەیە؛ هەر شتێکی تر واتە نادروست بووە.

Animation in eight frames evaluating 6 2 3 + * 4 -. The expression is shown at the top with the current symbol highlighted, and a stack of boxes grows upwards. 6, 2 and 3 are pushed. + pops 3 and 2 and pushes 5. * pops 5 and 6 and pushes 30. 4 is pushed. - pops 4 as the right operand and 30 as the left one and pushes 26. The last frame shows the single value 26 as the answer. — Numbers wait on the stack; each operator takes the top two and pushes its result.ژمارەکان لەسەر چاوەڕێ دەکەن؛ هەر دوو ژمارەی سەرەوە وەردەگرێت و ئەنجامەکەی push دەکات.CêIT

Evaluating postfix with an operand stackژماردنی نیشانەی پاشگر بە ستاکێکی کارپێکراو

A second example with all four operatorsنموونەیەکی دووەم بە هەر چوار کارپێکەرەکە

A second example with all four operators: 9 3 1 + * 8 2 / -, which is 9 * (3 + 1) - 8 / 2 in infix.

نموونەیەکی دووەم بە هەر چوار : 9 3 1 + * 8 2 / -، کە بە دەبێتە 9 * (3 + 1) - 8 / 2.

Symbolهێما	Actionکار	Stack (top on the right) (سەرەوە لای ڕاست)
`9`	push`push`	`9`
`3`	push`push`	`9 3`
`1`	push`push`	`9 3 1`
`+`	pop 1 (right), pop 3 (left): $3 + 1 = 4$ ⁦pop 1⁩ (ڕاست)، ⁦pop 3⁩ (چەپ): $3 + 1 = 4$	`9 4`
`*`	pop 4, pop 9: $9 \times 4 = 36$ ⁦pop 4⁩، ⁦pop 9⁩: $9 \times 4 = 36$	`36`
`8`	push`push`	`36 8`
`2`	push`push`	`36 8 2`
`/`	pop 2 (right), pop 8 (left): $8 \div 2 = 4$ ⁦pop 2⁩ (ڕاست)، ⁦pop 8⁩ (چەپ): $8 \div 2 = 4$	`36 4`
`-`	pop 4 (right), pop 36 (left): $36 - 4 = 32$ ⁦pop 4⁩ (ڕاست)، ⁦pop 36⁩ (چەپ): $36 - 4 = 32$	`32`
endکۆتایی	one value left: the answerتەنها یەک لەسەر هەیە: وەڵامەکە	32

Evaluating postfix with an operand stackژماردنی نیشانەی پاشگر بە ستاکێکی کارپێکراو

Postfix evaluation in Pythonژماردنی نیشانەی پاشگر لە Pythonـدا

Evaluate a postfix expressionدەربڕینێک بە نیشانەی پاشگر بژمێرەpostfix_eval.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def apply(op, left, right):
    if op == "+":
        return left + right
    if op == "-":
        return left - right
    if op == "*":
        return left * right
    return left / right

def evaluate(postfix, show=False):
    stack = []
    for token in postfix.split():
        if token in ("+", "-", "*", "/"):
            right = stack.pop()                # popped first: the RIGHT operand
            left = stack.pop()                 # popped second: the LEFT operand
            stack.append(apply(token, left, right))
        else:
            stack.append(int(token))           # a number: push it
        if show:
            print(f"{token:2} | {stack}")
    if len(stack) != 1:
        raise ValueError("invalid postfix expression")
    return stack.pop()

print(evaluate("9 3 1 + * 8 2 / -", show=True))
print()
print(evaluate("6 2 3 + * 4 -"))
print(evaluate("7 2 - 3 1 + *"))

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 1-8

apply() works out one operation, with the operands in the right order.

apply() یەک کردەوە دەژمێرێت، بە ڕیزبەندیی دروستی .

Lineدێڕی 14-15

First pop = right operand, second pop = left operand.

popـی یەکەم = ڕاست، popـی دووەم = چەپ.

Lineدێڕی 21-22

More or less than one value at the end means a broken expression.

زیاتر یان کەمتر لە یەک لە کۆتاییدا واتە تێکچوو.

/ makes a decimal number in Python, so the answer is 32.0. A check at each operator also catches invalid input instead of crashing with IndexError:

لە / دروست دەکات، بۆیە وەڵامەکە 32.0ـە. پشکنینێک لە هەر نادروستیش دەگرێت لەبری ئەوەی بە IndexError بکەوێت:

Invalid postfix expressionsدەربڕینەکانی نادروستی نیشانەی پاشگرpostfix_errors.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def apply(op, left, right):
    if op == "+":
        return left + right
    if op == "-":
        return left - right
    if op == "*":
        return left * right
    return left / right

def evaluate(postfix):
    stack = []
    for token in postfix.split():
        if token in ("+", "-", "*", "/"):
            if len(stack) < 2:
                return "invalid: not enough numbers for " + token
            right = stack.pop()
            left = stack.pop()
            stack.append(apply(token, left, right))
        else:
            stack.append(int(token))
    if len(stack) != 1:
        return "invalid: " + str(len(stack)) + " values are left"
    return stack.pop()

print(evaluate("4 5 + 3"))
print(evaluate("4 + 5"))
print(evaluate("8 2 /"), evaluate("2 8 /"))

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 14-15

An operator needs two numbers on the stack.

هەر پێویستی بە دوو ژمارە لەسەر هەیە.

Lineدێڕی 21-22

4 5 + 3 leaves two values: an operator is missing.

4 5 + 3 دوو جێ دەهێڵێت: نییە.

Lineدێڕی 27

The same numbers in the other order give another answer.

هەمان ژمارەکان بە ڕیزبەندییەکی تر وەڵامێکی تر دەدەن.

Quick checkپشکنینی خێراIn evaluate(), what would go wrong if the two pops were swapped (left = stack.pop() first)?لە evaluate()ـدا ئەگەر دوو popـەکە ئاڵوگۆڕ بکرێن (سەرەتا left = stack.pop())، چی هەڵە دەبێت؟Subtraction and division would give wrong answersلێدەرکردن و دابەشکردن وەڵامی هەڵە دەدەنNothing: the order never mattersهیچ: ڕیزبەندی هەرگیز گرنگ نییەEvery expression would raise an errorهەموو دەربڕینێک هەڵەیەک دروست دەکات

Common mistakesهەڵە باوەکان

Mistakeهەڵە	What happensچی ڕوو دەدات	Fixچارەسەر
`pop()` on an empty list`pop()` لەسەر بەتاڵ	`IndexError: pop from empty list`	check `is_empty()` (or `if stack:`) firstسەرەتا `is_empty()` (یان `if stack:`) بپشکنە
`stack.pop(0)` or `stack[0]` for the top`stack.pop(0)` یان `stack[0]` بۆ سەرەوە	you get the bottom, the oldest itemخوارەوە وەردەگریت، کۆنترین	`stack.pop()` and `stack[-1]stack.pop()` و `stack[-1]`
Taking the operands in the wrong order in postfixوەرگرتنی بە ڕیزبەندیی هەڵە لە	`8 2 /` gives 0.25 instead of 4`8 2 /` لەبری 4 دەداتە ⁦0.25⁩	first pop = right, second pop = leftpopـی یەکەم = ڕاست، popـی دووەم = چەپ
Popping only higher precedence in infix → postfixpop کردنی تەنها پێشینەیی بەرزتر لە ←	`a - b - c` becomes `a b c - -`, a different value`a - b - c` دەبێتە `a b c - -`، جیاواز	pop higher or equalبەرزتر یان یەکسان pop بکە
Forgetting to drop `(` after a `)`لەبیرکردنی فڕێدانی `(` دوای `)`	a bracket appears in the outputکەوانەیەک لە دەردەکەوێت	pop the `(` itself and throw it awayخودی `(` pop بکە و فڕێی بدە
Checking only the number of bracketsپشکنینی تەنها ژمارەی کەوانەکان	`)(` or `(]` is wrongly accepted`)(` یان `(]` بە هەڵە وەردەگیرێت	use a stack: kind and order must match بەکار بهێنە: جۆر و ڕیزبەندی دەبێت یەک بگرنەوە
Expecting a list stack to overflowچاوەڕوانیی لە کە لەسەر دروستکراوە	it never fills up; memory runs out insteadهەرگیز پڕ نابێت؛ لەبری ئەوە تەواو دەبێت	give the stack a limit and an `is_full()` checkسنوورێک و پشکنینی `is_full()` بە بدە

Exercisesڕاهێنانەکان

ExerciseڕاهێنانTrue or false?ڕاست یان هەڵە؟

(a) A stack is a linear data structure. (b) The item pushed first is popped first. (c) A push can cause underflow. (d) In postfix notation the operators come after their operands. (e) Postfix expressions need brackets to show what is worked out first.

(أ) هێڵییە. (ب) ئەو یەکەم جار push کراوە یەکەم جار pop دەکرێت. (ج) push دەتوانێت دروست بکات. (د) لە دوای دێن. (هـ) پێویستیان بە کەوانە هەیە بۆ پیشاندانی ئەوەی کامە سەرەتا دەژمێردرێت.

Show answerوەڵامەکە پیشان بدە

(a) True.
(b) False: last in, first out.
(c) False: a push can cause overflow (on a full stack); a pop causes underflow.
(d) True.
(e) False: postfix needs no brackets.

(أ) ڕاست.
(ب) هەڵە: دوایین هاتوو، یەکەم دەرچوو.
(ج) هەڵە: push دەتوانێت دروست بکات (لەسەر پڕ)؛ pop دروست دەکات.
(د) ڕاست.
(هـ) هەڵە: پێویستی بە کەوانە نییە.

ExerciseڕاهێنانPredict the outputدەرخستەکە پێشبینی بکە

What does this program print? Work it out on paper first.

ئەم چی چاپ دەکات؟ سەرەتا لەسەر کاغەز کاری لەسەر بکە.

predict.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

numbers = [5, 15, 25]
numbers.append(35)
result = numbers.pop() - numbers.pop()
print("Result =", result)

letters = []
for ch in "LOOP":
    letters.append(ch)
word = ""
while letters:
    word = word + letters.pop()
print("Word =", word)

Show answerوەڵامەکە پیشان بدە

Outputدەرخستە

Result = 10
Word = POOL

numbers.pop() gives 35 (the top) and the next pop() gives 25, so $35 - 25 = 10$ . The letters are pushed as L, O, O, P and popped as P, O, O, L.

numbers.pop() ژمارە ⁦35⁩ (سەرەوە) دەدات و pop()ـی دواتر ⁦25⁩ دەدات، بۆیە $35 - 25 = 10$ . پیتەکان بە L، O، O، ⁦P push⁩ دەکرێن و بە P، O، O، ⁦L pop⁩ دەکرێن.

ExerciseڕاهێنانBrackets, step by stepکەوانەکان، هەنگاو بە هەنگاو

Show the stack after every bracket while checking [(1+2)*{3-(4/2)}], and then {(8-3]*2}.

دوای هەموو کەوانەیەک پیشان بدە لە کاتی پشکنینی [(1+2)*{3-(4/2)}] و پاشان {(8-3]*2}.

Show answerوەڵامەکە پیشان بدە

Outputدەرخستە

  [   stack: [
  (   stack: [(
  )   stack: [
  {   stack: [{
  (   stack: [{(
  )   stack: [{
  }   stack: [
  ]   stack: (empty)
True
  {   stack: {
  (   stack: {(
  ]   mismatch
False

The first expression ends with an empty stack: balanced. In the second, ] arrives while ( is on the top: the kinds do not match.

یەکەم بە بەتاڵ کۆتایی دێت: هاوسەنگە. لە دووەمدا ] دێت لە کاتێکدا ( لە سەرەوەیە: جۆرەکان یەک ناگرنەوە.

ExerciseڕاهێنانReverse the wordsوشەکان پێچەوانە بکەرەوە

Write a function that uses a stack to reverse the order of the words in a sentence (not the letters).

بنووسە کە بەکار دەهێنێت بۆ پێچەوانەکردنەوەی ڕیزبەندیی وشەکانی ڕستەیەک (نەک پیتەکان).

Hintئاماژە

Push the words from split(), pop them all, and join() them.

وشەکانی split() push بکە، هەموویان pop بکە و بە join() پێکیان ببەستەوە.

Show answerوەڵامەکە پیشان بدە

reverse_words.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def reverse_words(sentence):
    stack = []
    for word in sentence.split():
        stack.append(word)          # push every word
    words = []
    while stack:
        words.append(stack.pop())   # pop: the last word comes out first
    return " ".join(words)

print(reverse_words("tea is ready in the tea house"))
print(reverse_words("Python is easy to learn"))

ExerciseڕاهێنانEvaluate with valuesبە نرخەکان بیژمێرە

With $A = 8$ , $B = 6$ , $C = 4$ and $D = 2$ , evaluate the postfix expressions (a) A B + C * and (b) A B * C / D *. Show the stack after each symbol.

بە $A = 8$ ، $B = 6$ ، $C = 4$ و $D = 2$ ، (أ) A B + C * و (ب) A B * C / D * بژمێرە. دوای هەر هێمایەک پیشان بدە.

Show answerوەڵامەکە پیشان بدە

values_eval.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def apply(op, left, right):
    if op == "+":
        return left + right
    if op == "-":
        return left - right
    if op == "*":
        return left * right
    return left / right

def evaluate(postfix, values):
    stack = []
    for token in postfix.split():
        if token in ("+", "-", "*", "/"):
            right = stack.pop()
            left = stack.pop()
            stack.append(apply(token, left, right))
        else:
            stack.append(values[token])        # A -> 8, B -> 6 ...
        print(f"   {token}: {stack}")
    return stack.pop()

values = {"A": 8, "B": 6, "C": 4, "D": 2}
for e in ["A B + C *", "A B * C / D *"]:
    print(e)
    print("   answer:", evaluate(e, values))

(a) $(8 + 6) \times 4 = 56$ . (b) $8 \times 6 = 48$ , $48 \div 4 = 12$ , $12 \times 2 = 24$ (Python shows 24.0 because of /).

(أ) $(8 + 6) \times 4 = 56$ . (ب) $8 \times 6 = 48$ ، $48 \div 4 = 12$ ، $12 \times 2 = 24$ ( بەهۆی /ـەوە ⁦24.0⁩ پیشان دەدات).

ExerciseڕاهێنانConvert to postfixبیگۆڕە بۆ نیشانەی پاشگر

Convert (a) A * B + C / D and (b) A - (B + C) * D to postfix, showing the stack and the output after each symbol. Then work out both with $A = 8$ , $B = 6$ , $C = 4$ and $D = 2$ .

(أ) A * B + C / D و (ب) A - (B + C) * D بگۆڕە بۆ و و دوای هەر هێمایەک پیشان بدە. پاشان هەردووکیان بە $A = 8$ ، $B = 6$ ، $C = 4$ و $D = 2$ بژمێرە.

Show answerوەڵامەکە پیشان بدە

Symbol | stack | output (from the to_postfix() function)هێما | ستاک | دەرخستە (لە کرداری to_postfix())

A * B + C / D
A   |           | A
*   | *         | A
B   | *         | A B
+   | +         | A B *
C   | +         | A B * C
/   | + /       | A B * C
D   | + /       | A B * C D
postfix: A B * C D / +
value with A=8, B=6, C=4, D=2: 50.0

A - ( B + C ) * D
A   |           | A
-   | -         | A
(   | - (       | A
B   | - (       | A B
+   | - ( +     | A B
C   | - ( +     | A B C
)   | -         | A B C +
*   | - *       | A B C +
D   | - *       | A B C + D
postfix: A B C + D * -
value with A=8, B=6, C=4, D=2: -12

(a) A B * C D / + gives $48 + 2 = 50$ . (b) A B C + D * - gives $8 - (10 \times 2) = -12$ .

(أ) A B * C D / + دەکاتە $48 + 2 = 50$ . (ب) A B C + D * - دەکاتە $8 - (10 \times 2) = -12$ .

ExerciseڕاهێنانOdd numbers on a stackژمارە تاکەکان لەسەر ستاکێک

Read whole numbers until the user enters a blank line. Push only the odd ones onto a stack. Show the stack, then find the largest odd number by popping until the stack is empty.

بخوێنەوە تا دێڕێکی بەتاڵ دەنووسێت. تەنها ژمارە تاکەکان بخەرە سەر . پیشان بدە، پاشان بە pop کردن تا بەتاڵ دەبێت گەورەترین ژمارەی تاک بدۆزەوە.

Hintئاماژە

Start with largest = None and replace it whenever a popped number is bigger.

بە largest = None دەست پێ بکە و هەر کاتێک ژمارەیەکی pop کراو گەورەتر بوو جێی بگرەوە.

Show answerوەڵامەکە پیشان بدە

odd_stack.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

odd = []
while True:
    text = input("Number (blank to stop): ")
    if text == "":
        break
    n = int(text)
    if n % 2 == 1:            # odd: push it
        odd.append(n)
print("Stack (top first):", odd[::-1])

largest = None
while odd:                    # pop until empty, keep the largest so far
    n = odd.pop()
    if largest is None or n > largest:
        largest = n
print("Largest odd number:", largest)

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 7-8

n % 2 == 1 is true for odd numbers.

n % 2 == 1 بۆ ژمارە تاکەکان ڕاستە.

Lineدێڕی 12-15

Keep the largest value seen so far while popping.

لە کاتی pop کردندا گەورەترین تا ئێستا بینراو بهێڵەرەوە.

Summaryپوختە

A data structure stores data together with the operations on it; linear ones keep a sequence.
A stack adds and removes only at the top: last in, first out (LIFO).
Operations: push, pop, peek, is_empty, size (is_full for a fixed size). Pushing onto a full stack is overflow; popping an empty one is underflow.
In Python a list is a stack: append() = push, pop() = pop, [-1] = peek.
Stacks undo edits, power the Back button, reverse text, check brackets and hold function calls.
Infix a + b, prefix + a b, postfix a b +. Postfix needs no brackets or precedence rules.
Infix → postfix uses an operator stack (pop higher or equal precedence first); postfix evaluation uses an operand stack (first pop = right operand).

کۆمەڵێک لەگەڵ ئەو کارانەی لەسەریان دەکرێن هەڵدەگرێت؛ جۆرە هێڵییەکان ڕیزبەندییەک دەپارێزن.
تەنها لە سەرەوە زیاد دەکات و لادەبات: دوایین هاتوو، یەکەم دەرچوو ⁦(LIFO)⁩.
کارەکان: push، pop، peek، ⁦is_empty⁩، ⁦size (is_full⁩ بۆ قەبارەی جێگیر). push بۆ سەر پڕ ؛ pop لە بەتاڵ .
لە : append() = push، pop() = pop، [-1] = peek.
دەستکارییەکان پاشگەز دەکەنەوە، دوگمەی Back کار پێ دەکەن، دەق پێچەوانە دەکەنەوە، کەوانە دەپشکنن و بانگکردنی هەڵدەگرن.
a + b، + a b، a b +. پێویستی بە کەوانە و یاسای پێشینەیی نییە.
← بەکار دەهێنێت (سەرەتا پێشینەیی بەرزتر یان یەکسان pop بکە)؛ ژماردنی بەکار دەهێنێت (popـی یەکەم = ڕاست).

Next: Queues and deques, where the first item in is the first one out.

دواتر: کیووەکان و کیووە دووسەرەکان، کە تێیدا یەکەم هاتوو یەکەم دەرچووە.

Review questionsپرسیارەکانی پێداچوونەوە

Why does a Python list make a good stack?بۆچی لیستێکی Python ستاکێکی باشە؟

append() and pop() both work at the end of the list, where nothing else has to move, so they are fast.

append() و pop() هەردووکیان لە کۆتایی کار دەکەن، کە هیچ شتێکی تر پێویست ناکات بجووڵێت، بۆیە خێران.

What is (a + b) * c in postfix?(a + b) * c بە نیشانەی پاشگر چییە؟

a b + c *

Evaluating postfix, which popped value is the left operand?لە ژماردنی نیشانەی پاشگردا، کام نرخ pop کراو کارپێکراوی چەپە؟

The second one popped (it was pushed first).

دووەمیان کە pop کراوە (یەکەم جار push کرابوو).

What is the difference between overflow and underflow?جیاوازیی نێوان سەرڕێژبوون و ژێرڕێژبوون چییە؟

Overflow: pushing onto a full stack. Underflow: popping from an empty one.

: push بۆ سەر پڕ. : pop لە بەتاڵ.

Videoڤیدیۆ

Watch a videoسەیری ڤیدیۆیەک بکە

A video that viewers liked a lot and praised in their comments, chosen for this lesson.ڤیدیۆیەک کە بینەران زۆریان پێ خۆش بووە و لە کۆمێنتەکانیاندا ستایشیان کردووە، بۆ ئەم وانەیە هەڵبژێردراوە.

Stacks in 3 minutesMichael Sambol · Englishئینگلیزی · 69K viewsبینین · 1.7K likesلایک
A stack in three minutes: last in, first out, push and pop on an example, and a short Python version that uses a list.
لە سێ خولەکدا: LIFO (دوایین کە دێتە ژوورەوە یەکەم دەچێتە دەرەوە)، push و pop لەسەر نموونەیەک و کۆدێکی کورتی کە بەکاردەهێنێت.
A 3-minute overview: LIFO (0:16), pop (0:31), an example (0:46) and code (1:34).
پێداچوونەوەیەکی 3 خولەکی: ⁦LIFO (0:16)⁩، ⁦pop (0:31)⁩، نموونەیەک ⁦(0:46)⁩ و کۆد ⁦(1:34)⁩.

Lesson complete!وانەکە تەواو بوو!

Well done. Review the key terms, then go on to the next lesson.دەستخۆش. سەیرێکی زاراوە سەرەکییەکان بکەرەوە، پاشان بڕۆ بۆ وانەی داهاتوو.

Key termsزاراوە سەرەکییەکان

Next lessonوانەی داهاتوو

Queues and Deques: First In, First Outکیووەکان و کیووە دووسەرەکان: یەکەم هاتوو، یەکەم دەرچوو

Related lecturesوانە پەیوەندیدارەکان

References and further readingسەرچاوەکان و خوێندنەوەی زیاتر

This lecture is a first edition. The Kurdish text and terminology are waiting for review by Kurdish IT teachers.ئەم وانەیە چاپی یەکەمە. دەقە کوردییەکە و زاراوەکانی چاوەڕێی پێداچوونەوەی مامۆستایانی کوردی بواری IT ن.