Stack

Imagine a pile of plates. If a new plate is placed on top, it is the first plate we remove. Many programs use this last-in, first-out (LIFO) arrangement to handle tasks such as undoing an edit, reversing data, checking brackets and evaluating expressions. This chapter develops the stack idea from first principles, implements it in Python and solves every exercise in NCERT Class XII Computer Science, Chapter 3.

Source coverage: The supplied NCERT Class XII textbook, Chapter 3 “Stack,” printed pp. 39–52 (lecs103.pdf), includes §§3.1–3.7, a multi-function stack of glasses demonstration, infix-to-postfix Algorithm 3.1 and Example 3.1, postfix-evaluation Algorithm 3.2 and Example 3.2, and seven numbered exercises. All seven exercises, including every printed subpart, are fully solved below. The exercise bank is paraphrased and the explanations are original. There are no separately numbered Activities in this chapter.

Curriculum alignment: The uploaded Class XII master curriculum assigns C12-DS-01 — Stack Concept and Operations and C12-DS-02 — Stack Implementation Using Python Lists. The NCERT chapter also teaches expression notation, infix-to-postfix conversion and postfix evaluation; these are included as NCERT chapter extensions and applications of C12-DS-02, not invented permanent lesson IDs. Reading anchors C12-CH03-S01 through C12-CH03-S06 are sections within this one chapter.

Learning objectives#

By the end of this resource, you should be able to:

1. Define data structure, linear structure, stack, LIFO and TOP with examples.
2. Trace PUSH, POP, PEEK/TOP, isEmpty, size and display, and distinguish underflow from overflow.
3. Implement a stack safely using the right end of a Python list with append() and pop().
4. Explain common stack applications, including undo history, backtracking, function calls and bracket matching.
5. Distinguish infix, prefix and postfix notation, and show the operator-stack state while converting infix to postfix.
6. Trace and evaluate postfix expressions with correct operand order and input validation.
7. Answer all NCERT Exercises 1–7, including the odd-number stack program.
8. Solve thirty additional questions, including output tracing and original programming problems.

Chapter reading map#

The conceptual lessons, practical Python demonstrations, NCERT solution bank, and original practice are separated by headings so they can be presented as distinct, searchable resources on akhileshsaini.com.

Section C12-CH03-S01 — What Is a Stack?#

Permanent lesson: C12-DS-01 — Stack Concept and Operations. NCERT: §§3.1–3.2.

1. Data structures and linear organisation#

A data structure is a way of arranging and accessing data together with the operations we need to perform on it. The same information may be organised differently depending on how the program uses it: a list can preserve order; a dictionary can look up values by key; a stack imposes an additional access discipline.

A linear data structure arranges elements in a sequence. A stack is linear because its contents have an order, but its defining characteristic is more specific: insertion and deletion occur at the same end.

Suppose we push three books in the order English, Maths, Science. Reading from bottom to top, the stack contains:

TOP → Science   (last added; first removed)
      Maths
      English   (first added; last removed)
BOTTOM

The ordering rule is called LIFO — Last In, First Out. This does not mean every operation is restricted to reading only one value: we can display an entire stack for teaching, but the actual insertion/removal operations must respect the TOP end.

2. Essential vocabulary#

Exam trap: A plain Python list does not impose a fixed stack capacity. It normally grows dynamically until memory or another resource limit intervenes. For a classroom bounded stack, we explicitly choose a capacity and check it before pushing. Conversely, the built-in list.pop() on [] raises IndexError; underflow is the conceptual name for that invalid operation, not a separate built-in Python UnderflowError class.

3. Why stacks are useful#

• Undo in a text editor: The latest change can be undone first. Real undo/redo systems may use two histories or a richer command model.
• Reversing a sequence: Pushing characters in reading order and popping them produces reverse order.
• Function calls: A program's call stack manages nested function execution and return information; this is a system-level use, not merely a student-created Python list.
• Parentheses and bracket matching: Opening brackets are remembered until the correct closing bracket arrives.
• Navigation and backtracking: Recently visited states may be revisited in reverse order. A realistic browser may also maintain a separate forward-history structure.
• Expression conversion/evaluation: Operators or operands are managed using stacks in predictable order.

Think it through: Why is a queue different? A queue commonly follows FIFO — First In, First Out: insertion at the rear, deletion from the front. A stack adds and removes at the same end. Do not mix up the two.

Quick check#

Push P, then Q, then R. If one item is popped and S is pushed, the stack becomes [P, Q, S], with S at TOP. R was popped. You cannot pop P first without removing S and Q (or violating stack discipline).

Section C12-CH03-S02 — Stack Operations and Their Traces#

Permanent lesson: C12-DS-01. NCERT: §3.3.

1. PUSH: insertion at TOP#

A new item is inserted at the top. In a bounded stack, pushing is allowed only while size < capacity.

Before: [5, 10]       TOP = 10
PUSH(15)
After:  [5, 10, 15]   TOP = 15

2. POP: deletion from TOP#

Popping both returns and removes the most recently inserted item:

Before: [5, 10, 15]   TOP = 15
POP() returns 15
After:  [5, 10]       TOP = 10

Popping an empty stack is underflow. peek() is different: it only observes the top. display() may show values without changing any stored element.

3. A complete operation trace#

We represent the bottom of the stack on the left and TOP on the right.

A useful classroom representation begins with top_index = -1 when empty and updates it after each push/pop. In an ordinary Python list implementation, we don't need a separate TOP index: the last item stack[-1] is already at TOP.

4. Time complexity and practical choices#

With a Python list, stack.append(x) and stack.pop() at the end usually take amortized O(1) and O(1) time, respectively. stack[-1], len(stack) and not stack are O(1). Appending occasionally triggers allocation and copying, so describing every append as strict worst-case O(1) would be inaccurate. Scanning or displaying n elements takes O(n). Adding/removing at the front (insert(0, ...), pop(0)) normally costs O(n), so choose the right end for a list-based stack.

5. Fixed-capacity example (supplemental)#

capacity = 2
stack = []

def push(value):
    if len(stack) == capacity:
        print("Overflow: the bounded stack is full")
        return False
    stack.append(value)
    return True

push(12)
push(24)
push(36)             # rejected: capacity already reached
print(stack)          # [12, 24]

The False result here is a chosen design, not a built-in behavior of list.append(). In a real application you might instead raise a custom exception.

Section C12-CH03-S03 — Implementing a Stack with Python Lists#

Permanent lesson: C12-DS-02 — Stack Implementation Using Python Lists. NCERT: §3.4.

1. Mapping stack operations onto list operations#

The most natural beginner implementation is stack = [], with TOP at the last list position. Use append() for PUSH, pop() for POP and stack[-1] for PEEK after checking non-emptiness.

Reminder: list.pop() should be guarded or its IndexError handled. In student examples below, we use an explicit emptiness test and a visible Underflow message to match the NCERT classroom model. If a stack must store None as a legitimate value, returning None to signal an empty stack is ambiguous; prefer a documented exception or a (success, value) result.

2. The NCERT stack-of-glasses example, rewritten and explained#

NCERT introduces the functions isEmpty, opPush, size, top, opPop and display for a stack of glasses. This is an original, executable implementation using the same educational API and LIFO behavior. The public methods are implemented here as functions taking the stack as a parameter, so they can be reused with different lists.

def isEmpty(glassStack):
    return len(glassStack) == 0


def opPush(glassStack, element):
    glassStack.append(element)


def size(glassStack):
    return len(glassStack)


def top(glassStack):
    if isEmpty(glassStack):
        print("Stack is empty")
        return None
    return glassStack[-1]


def opPop(glassStack):
    if isEmpty(glassStack):
        print("Underflow")
        return None
    return glassStack.pop()


def display(glassStack):
    print("Current elements in the stack are:")
    for element in reversed(glassStack):
        print(element)


glassStack = []
opPush(glassStack, "glass1")
opPush(glassStack, "glass2")
print("Size:", size(glassStack))
print("Popped:", opPop(glassStack))
opPush(glassStack, "glass3")
print("Top:", top(glassStack))
display(glassStack)
while not isEmpty(glassStack):
    print("Popped:", opPop(glassStack))
print("Empty:", isEmpty(glassStack))

Worked output:

Size: 2
Popped: glass2
Top: glass3
Current elements in the stack are:
glass3
glass1
Popped: glass3
Popped: glass1
Empty: True

Trace of the crucial operations: Push glass1, push glass2, then pop glass2. Push glass3: it becomes TOP, above glass1. The final two pops therefore return glass3 and glass1, in that order.

NCERT wording versus Python behavior: A memory-limited list can fail with MemoryError, so saying a dynamically grown list could never overflow is too absolute. The meaningful classroom point is that Python lists have no fixed, explicitly declared stack capacity, unlike some bounded stack implementations.

3. A reusable class (supplemental, optional for beginners)#

A class can keep the stack's internal representation private and provide predictable error handling. This expands the same concept; it does not introduce a new curriculum lesson ID.

class Stack:
    def __init__(self):
        self._items = []

    def push(self, value):
        self._items.append(value)

    def pop(self):
        if not self._items:
            raise IndexError("stack underflow")
        return self._items.pop()

    def peek(self):
        if not self._items:
            raise IndexError("stack is empty")
        return self._items[-1]

    def is_empty(self):
        return not self._items

    def size(self):
        return len(self._items)


numbers = Stack()
numbers.push(11)
numbers.push(23)
print(numbers.peek(), numbers.pop(), numbers.size())
# 23 23 1

If the program requires only beginner-level functions, the earlier NCERT-compatible version is sufficient. The class is useful for understanding abstraction: the caller uses stack operations without directly modifying an internal list.

4. Common mistakes#

• Using pop(0) for stack deletion: that removes the first value and turns the program into a queue-like behavior when appending at the right end.
• Forgetting the empty check: [].pop() raises IndexError.
• Treating PEEK as POP: PEEK does not alter the stack.
• Treating a display printout as storage order: In these examples, storage order is bottom-to-top left-to-right, while display() prints top-to-bottom.
• Confusing a None data item with an empty-return sentinel: write an explicit API contract.

Section C12-CH03-S04 — Notations and Matching Parentheses#

Curriculum mapping: C12-DS-02 (application); NCERT chapter extension: §3.5, matching-bracket applications.

1. Infix, prefix and postfix#

A binary arithmetic expression combines operands (numbers or variables) and operators (+, -, *, /). Its order can be written in three equivalent ways:

The notation is about the tree of operations; parentheses group infix operations, while correctly constructed prefix/postfix expressions express order through the arrangement of tokens. Infix operators follow precedence and associativity, e.g. A + B * C means A + (B * C).

For the NCERT example (x + y)/(z * 8):

Infix:   (x + y) / (z * 8)
Prefix:  / + x y * z 8
Postfix: x y + z 8 * /

Operators in postfix notation can be processed from left to right without re-deciding infix precedence at evaluation time, provided the postfix input is valid.

2. Parentheses matching with a stack#

When scanning an expression from left to right:

1. If the character is an opening bracket, push it.
2. If it is a closing bracket, pop the latest opening bracket; check that the pair matches.
3. A closing bracket with no opener is invalid immediately.
4. Any opening bracket still present at the end is unmatched.

The original NCERT Q4 focuses on parentheses ( and ). We can support the three common bracket types for additional practice:

def brackets_match(expression):
    stack = []
    pairs = {")": "(", "]": "[", "}": "{"}
    for char in expression:
        if char in "([{":
            stack.append(char)
        elif char in pairs:
            if not stack or stack.pop() != pairs[char]:
                return False
    return not stack

print(brackets_match("((2+3)*(4/2))+2"))  # True
print(brackets_match("([)]"))            # False
print(brackets_match("((A+B)"))          # False

Scope note: This simple illustration assumes that bracket characters have their ordinary structural meaning. A full programming-language parser must also deal with quoted strings, comments and escaping; do not mistake this exercise for a complete Python syntax checker.

Section C12-CH03-S05 — Conversion from Infix to Postfix#

Curriculum mapping: C12-DS-02 (application); NCERT chapter extension: §3.6, Algorithm 3.1, Example 3.1.

1. Why an operator stack is needed#

The expression A + B * C is not evaluated left-to-right without considering precedence. A computer can instead read the postfix form A B C * +, where the order is explicit. An operator stack temporarily keeps operators until they can be placed correctly into the output.

For our classroom converter, we use single-letter operands (A, B, etc.) and single-digit constants, parentheses and + - * /. This matches the basic NCERT examples. For multi-digit numbers and richer expressions, the input should first be tokenized and additional rules should be specified.

2. Conversion rules#

• Operand: send directly to the output.
• Opening (: push it to the operator stack.
• Closing ): pop operators to output until the matching ( is reached, then discard both brackets.
• Operator: pop previous operators with greater or equal precedence (for the left-associative operators + - * /), unless blocked by (. Then push the current operator.
• End: pop all remaining operators into the output; unmatched parentheses are invalid.

Precedence is * and / higher than + and -. Equal precedence matters: A - B + C is interpreted as (A - B) + C and thus becomes A B - C +, not A B C + -.

NCERT's printed prose for popping operators is simplified; the implementation here makes equal precedence, left associativity and malformed parentheses explicit. For Python's right-associative exponentiation operator **, a different equal-precedence rule would be required; it is outside this demonstration.

3. Full algorithm in Python#

def infix_to_postfix(expression):
    priority = {"+": 1, "-": 1, "*": 2, "/": 2}
    operators = []
    output = []

    for token in expression.replace(" ", ""):
        if token.isalnum():
            output.append(token)
        elif token == "(":
            operators.append(token)
        elif token == ")":
            while operators and operators[-1] != "(":
                output.append(operators.pop())
            if not operators:
                raise ValueError("unmatched closing parenthesis")
            operators.pop()  # remove matching '('
        elif token in priority:
            while (operators and operators[-1] != "(" and
                   priority[operators[-1]] >= priority[token]):
                output.append(operators.pop())
            operators.append(token)
        else:
            raise ValueError(f"unsupported character: {token!r}")

    while operators:
        token = operators.pop()
        if token == "(":
            raise ValueError("unmatched opening parenthesis")
        output.append(token)

    return " ".join(output)

print(infix_to_postfix("(x+y)/(z*8)"))
print(infix_to_postfix("A+B-C*D"))
print(infix_to_postfix("A*((C+D)/E)"))

Output:

x y + z 8 * /
A B + C D * -
A C D + E / *

Important limitation: This classroom function converts single-character operands. It does not automatically interpret 12 as one operand or support unary negative values. In this chapter's numeric postfix evaluator, we work with whitespace-separated tokens so multi-digit numbers can be handled safely.

4. NCERT Example 3.1: (x + y)/(z * 8)#

The operator stack is shown bottom-to-top; the rightmost character is TOP.

This is the operation order shown in the NCERT figure. No parentheses appear in the final postfix expression.

Section C12-CH03-S06 — Evaluation of Postfix Expressions#

Curriculum mapping: C12-DS-02 (application); NCERT chapter extension: §3.7, Algorithm 3.2, Example 3.2.

1. Operand stack and evaluation order#

During conversion, the stack temporarily holds operators. During evaluation, the stack holds operands / intermediate results. This distinction is a common source of confusion.

Read the postfix expression from left to right:

1. On an operand, push its numeric value.
2. On a binary operator, pop the right operand first and the left operand second.
3. Compute left operator right; push the answer.
4. At the end, exactly one value must remain. No elements or too many elements means invalid postfix syntax.

Subtraction and division show why order matters: for 8 2 -, the correct answer is 8 - 2 = 6, not 2 - 8.

2. NCERT Example 3.2: 7 8 2 * 4 / +#

In Python, / produces a float, so the executed result is 11.0, even though NCERT's arithmetic result is written as 11. Both describe the same mathematical quantity; the Python output representation is explicitly distinguished below.

3. Safe Python evaluator for space-separated postfix expressions#

This function supports numbers (including decimals and negative values already tokenized) and the four binary operators. It detects insufficient operands, division by zero and invalid leftover values.

def evaluate_postfix(expression):
    stack = []
    operators = {"+", "-", "*", "/"}

    for token in expression.split():
        if token in operators:
            if len(stack) < 2:
                raise ValueError("insufficient operands")
            right = stack.pop()
            left = stack.pop()
            if token == "+":
                value = left + right
            elif token == "-":
                value = left - right
            elif token == "*":
                value = left * right
            else:
                if right == 0:
                    raise ZeroDivisionError("division by zero")
                value = left / right
            stack.append(value)
        else:
            try:
                stack.append(float(token))
            except ValueError as exc:
                raise ValueError(f"invalid operand: {token!r}") from exc

    if len(stack) != 1:
        raise ValueError("malformed postfix expression")
    return stack[0]

print(evaluate_postfix("7 8 2 * 4 / +"))  # 11.0
print(evaluate_postfix("9 3 / 2 +"))    # 5.0

Avoid this error: float(token) treats the string "12" as a single value but the NCERT per-character algorithm assumes a simpler format. Tokenization is why the function explicitly calls .split().

4. Evaluating prefix expressions (NCERT margin prompt)#

NCERT additionally asks the reader to propose an algorithm for evaluating a prefix expression. For binary operators, scan right to left. Push operands; on meeting an operator, pop left operand first, then right operand, compute the operation and push the result. At the end, one result should remain.

For + 7 / * 8 2 4 (prefix of the preceding postfix example), evaluate 8*2=16, then 16/4=4, and finally 7+4=11. A working version is supplied in the supplemental teaching questions below.

5. Revision: contrast the two stack uses#

NCERT Chapter 3 — Complete Exercise Solutions (Questions 1–7)#

All seven numbered exercises on the final page of NCERT Chapter 3 are solved below. Subparts retain the original identifiers, and printed code questions are explained using valid Python quotation marks. The exercise descriptions are paraphrased rather than reproduced as a substitute for the textbook.

NCERT Exercise 1 — True or False (four subparts)#

Memory aid: PUSH → add → potential overflow; POP → remove → potential underflow. An unbounded list has no artificial fixed capacity.

NCERT Exercise 2 — Predict the output (both parts)#

Q2(a) — Two POPs after appending to a number list#

The given Python example starts with a list holding 10, 20, 30, appends 40, then pops twice and accumulates the returned values.

result = 0
numberList = [10, 20, 30]
numberList.append(40)
result = result + numberList.pop()
result = result + numberList.pop()
print("Result=", result)

Trace:

Exact output:

Result= 70

print("Result=", result) inserts a space between its two arguments. The remaining stack has [10, 20].

Q2(b) — Pop three characters into a string#

answer = []
output = ""
answer.append("T")
answer.append("A")
answer.append("M")
ch = answer.pop()
output = output + ch
ch = answer.pop()
output = output + ch
ch = answer.pop()
output = output + ch
print("Result=", output)

Trace: After the pushes, the stack is ['T', 'A', 'M'] (M at TOP). Pops return M, then A, then T. Concatenating in popped order builds "M", then "MA", then "MAT".

Exact output:

Result= MAT

NCERT Exercise 3 — Reverse a string using a stack#

A normal Python slice such as text[::-1] can reverse a string, but the exercise specifically requires the stack method. Push each character, then pop until empty.

def reverse_using_stack(text):
    stack = []
    for char in text:
        stack.append(char)

    reversed_characters = []
    while stack:
        reversed_characters.append(stack.pop())
    return "".join(reversed_characters)

word = input("Enter a string: ")
print("Reversed:", reverse_using_stack(word))

Sample input: PYTHON

Sample output:

Reversed: NOHTYP

Why it works: For the word CAT, the pushes are C, A, T; pops return T, A, C. The returned reversed string is TAC. An empty input produces an empty output; spaces are preserved as characters.

NCERT Exercise 4 — Step-by-step matching of parentheses#

The textbook expression is:

((2+3)*(4/2))+2

Scan all characters, pushing the position of each opening ( and popping it at a closing ). Only bracket characters change the stack; numbers and operators are skipped. Positions below are 1-based positions in the original expression.

Conclusion: All opening parentheses have matching closing parentheses. The expression is balanced. The arithmetic expression itself also evaluates to ((5)*(2))+2 = 12, but calculating it is not required to establish bracket matching.

Important distinction: A bracket counter alone could fail to detect incorrect nesting for mixed bracket types. A stack can check matching types as well as nesting.

A runnable trace program:

def show_parenthesis_matches(expression):
    opening_positions = []
    for position, ch in enumerate(expression, start=1):
        if ch == "(":
            opening_positions.append(position)
            print("Open", position, "stack:", opening_positions)
        elif ch == ")":
            if not opening_positions:
                print("Unmatched closing at", position)
                return False
            opened_at = opening_positions.pop()
            print("Matched", opened_at, "with", position,
                  "stack:", opening_positions)
    return not opening_positions

print(show_parenthesis_matches("((2+3)*(4/2))+2"))
# True

NCERT Exercise 5 — Evaluate postfix expressions and show each stack state#

Given A = 3, B = 5, C = 1 and D = 4, substitute the values when pushing operands.

Q5(a): A B + C *#

Answer: 8. The infix equivalent is (A+B)*C.

Q5(b): A B * C / D *#

Answer: 60 (or 60.0 in Python when implementing / as true division). The infix grouping is ((A*B)/C)*D. Beware the reversed-order error: the correct operation is 15 / 1, not 1 / 15.

Runnable validation for both subparts#

def evaluate_with_variables(tokens, values):
    stack = []
    for token in tokens.split():
        if token in "+-*/":
            right = stack.pop()
            left = stack.pop()
            if token == "+":
                stack.append(left + right)
            elif token == "-":
                stack.append(left - right)
            elif token == "*":
                stack.append(left * right)
            else:
                stack.append(left / right)
        else:
            stack.append(values[token])
    return stack.pop()

values = {"A": 3, "B": 5, "C": 1, "D": 4}
print(evaluate_with_variables("A B + C *", values))      # 8
print(evaluate_with_variables("A B * C / D *", values))  # 60.0

This small function assumes valid input; the teaching evaluator in §S06 performs stronger validation for standalone numeric expressions.

NCERT Exercise 6 — Infix to postfix, with stack and output after every step#

The operator stack is written bottom-to-top, with its TOP at the right.

Q6(a): A + B - C * D#

Final answer: A B + C D * -, or without spaces, AB+CD*-.

Reason: (A + B) - (C * D). Converting A + (B - C) * D would be a different expression, so equal-precedence associativity must be respected.

Q6(b): A * ((C + D)/E)#

Final answer: A C D + E / *, or ACD+E/* without spaces.

Reason: First add C+D, then divide that sum by E, then multiply by A. The result has no parentheses and exactly three binary operators: +, / and *.

NCERT Exercise 7 — Stack of odd numbers and its largest value#

The NCERT exercise asks us to take entered numbers, push only odd numbers, then display the stack and find the largest stored odd number by repeatedly popping. We follow that specific requirement rather than using a direct max(stack) shortcut.

def odd_stack_largest(numbers):
    odd_stack = []
    for number in numbers:
        if number % 2 != 0:
            odd_stack.append(number)

    print("Stack bottom to top:", odd_stack)
    if not odd_stack:
        print("No odd numbers entered.")
        return None

    largest = None
    print("Popping TOP to BOTTOM:")
    while odd_stack:
        item = odd_stack.pop()
        print(item)
        if largest is None or item > largest:
            largest = item

    print("Largest odd number:", largest)
    return largest

values = [12, 7, -3, 14, 21, 9, 0]
odd_stack_largest(values)

Sample output:

Stack bottom to top: [7, -3, 21, 9]
Popping TOP to BOTTOM:
9
21
-3
7
Largest odd number: 21

For a complete interactive submission, accept the number of inputs first and then read each integer. This wrapper reuses the same tested algorithm:

def collect_numbers():
    count = int(input("How many numbers? "))
    if count < 0:
        raise ValueError("count cannot be negative")
    numbers = []
    for i in range(count):
        numbers.append(int(input(f"Number {i + 1}: ")))
    return numbers

# First define odd_stack_largest() as shown immediately above.
# Then run:
# odd_stack_largest(collect_numbers())

Important edge cases:

• No odd numbers: report a meaningful message instead of calling max([]).
• Negative odd numbers: % 2 != 0 also identifies them correctly in Python.
• Duplicates: keep every entered odd number unless the question explicitly asks for unique values.
• Stack emptied at end: the textbook hint requires successive POPs. A separate stored largest variable retains the answer after the list is emptied.
• No false index assumptions: the rightmost value is the current TOP.

NCERT Worked Example and Algorithm Review#

Example A — Stack of glasses (§3.4)#

The full runnable teaching version appears in Section S03. Its key functions and NCERT-aligned operations are:

The NCERT demonstration pushes glass1, pushes glass2, pops glass2, pushes glass3, and finally removes glass3 and glass1. The result follows LIFO at every step.

Example B — Algorithm 3.1: infix to postfix (§3.6)#

NCERT uses (x + y)/(z * 8) and shows operators/parentheses in an operator stack. We provide the complete table and a validated Python converter in Section S05. Its answer is x y + z 8 * /.

Example C — Algorithm 3.2: postfix evaluation (§3.7)#

NCERT uses 7 8 2 * 4 / +. We show all pushes/pops in Section S06 and a Python evaluator. The mathematical result is 11; Python true-division produces 11.0.

Textbook margin prompts — answered#

How are nested function calls handled? The execution runtime keeps a call stack of active functions (frames) to support nested calls and returns. A student's stack = [] is an illustrative model; it is not itself Python's internal call-stack implementation.

How does an operating system manage available memory? Memory management may use free lists, page tables, bitmaps and allocator metadata. It is not generally correct to claim that all available memory is simply stored in a single ordinary LIFO stack. NCERT raises this as a thinking prompt, not a blanket statement that the answer must be a stack.

How could we evaluate a prefix expression using a stack? Scan the prefix tokens right-to-left; push each operand; on an operator pop two operands in left/right order, calculate, push the result, and require exactly one value at the end. A basic implementation for numbers follows:

def evaluate_prefix(expression):
    stack = []
    operators = {"+", "-", "*", "/"}
    for token in reversed(expression.split()):
        if token in operators:
            if len(stack) < 2:
                raise ValueError("not enough operands")
            left = stack.pop()
            right = stack.pop()
            if token == "+":
                value = left + right
            elif token == "-":
                value = left - right
            elif token == "*":
                value = left * right
            else:
                if right == 0:
                    raise ZeroDivisionError("division by zero")
                value = left / right
            stack.append(value)
        else:
            stack.append(float(token))
    if len(stack) != 1:
        raise ValueError("malformed prefix expression")
    return stack[0]

print(evaluate_prefix("+ 7 / * 8 2 4"))  # 11.0

Original Practice Questions — 30 with Answers and Explanations#

The following thirty questions are original learning and examination-style practice, not quotations or previous-year examination questions. They include ten conceptual multiple-choice questions, eight trace problems, six reasoning tasks and six coding/application tasks. Each answer is explained.

Foundation MCQs (1–10)#

Practice 1 — Which operation removes the newest item?#

Question. Which stack operation both returns and removes the last item inserted? (A) PUSH, (B) POP, (C) PEEK, (D) SIZE.

Answer: B — POP. PEEK observes the item but leaves the stack unchanged. PUSH adds an item, and SIZE counts elements.

Practice 2 — Identify the rule#

Question. An item added last comes out first. Is this (A) FIFO, (B) sorted order, (C) LIFO, or (D) random access?

Answer: C — LIFO. The latest pushed element occupies TOP and therefore is removed next.

Practice 3 — Empty-list deletion#

Question. Which Python exception is normally raised by [].pop()? (A) ValueError, (B) IndexError, (C) KeyError, (D) TypeError.

Answer: B — IndexError. The stack condition is called underflow, but Python uses IndexError for popping an empty list.

Practice 4 — Best list operation#

Question. To implement a stack efficiently with its TOP at the right end, choose (A) insert(0,x) and pop(0), (B) append(x) and pop(), (C) sort() and clear(), (D) extend() and reverse().

Answer: B. Adding and removing at the end avoids shifting other list items and matches LIFO behavior.

Practice 5 — PEEK behavior#

Question. After calling PEEK on [3, 6, 9], the content is (A) [3,6], (B) [9], (C) [3,6,9], (D) [].

Answer: C. PEEK returns 9, but it does not mutate the stack.

Practice 6 — Postfix of (A+B)*C#

Question. Choose its postfix form: (A) A B C + *, (B) A B + C *, (C) * + A B C, (D) A + B * C.

Answer: B — A B + C *. The addition must happen before multiplication. Option C is prefix, not postfix.

Practice 7 — Conversion stack contents#

Question. During infix-to-postfix conversion, the operator stack primarily stores (A) final results, (B) operators and parentheses, (C) input numbers only, or (D) variables' Python values.

Answer: B. During postfix evaluation a different stack stores operand values and intermediate results.

Practice 8 — Operand order#

Question. The postfix expression 9 3 - evaluates to (A) -6, (B) 6, (C) 12, (D) 3.

Answer: B — 6. Pop right operand 3 first, then left operand 9; calculate 9−3.

Practice 9 — Complexity of stack display#

Question. A complete display of all n items is usually (A) O(1), (B) O(log n), (C) O(n), (D) O(n²).

Answer: C — O(n). Every stored element must be visited once to display it.

Practice 10 — True statement about capacity#

Question. A Python-list stack with no explicit capacity check (A) always has capacity 10, (B) always reports a built-in stack overflow error once its length reaches 100, (C) grows subject to system resources, or (D) cannot store strings.

Answer: C. Python lists are dynamic and may store mixed data; available memory, not a built-in teaching limit, restricts growth.

Output-tracing questions (11–18)#

Practice 11 — PUSH then POP#

s = [2, 4]
s.append(6)
print(s.pop(), s)

Answer: 6 [2, 4]. append(6) puts 6 on TOP. pop() removes and returns that last value.

Practice 12 — Two pops and a new push#

s = ["A", "B", "C"]
first = s.pop()
second = s.pop()
s.append("D")
print(first, second, s[-1], s)

Answer: C B D ['A', 'D']. The latest item C is popped before B; after the new push, D is TOP.

Practice 13 — PEEK does not alter size#

s = [10, 20, 30]
print(s[-1])
print(len(s))
print(s)

Answer: Three lines: 30, 3 and [10, 20, 30]. Reading [-1] changes nothing.

Practice 14 — Empty check avoids underflow#

s = []
if s:
    print(s.pop())
else:
    print("Empty")
print(len(s))

Answer: Empty and then 0. An empty Python list is false in Boolean context, so pop() is not attempted.

Practice 15 — Printing TOP-to-BOTTOM#

s = ["red", "green", "blue"]
for item in reversed(s):
    print(item)

Answer:

blue
green
red

Explanation: reversed(s) visits TOP first. It does not modify the original list.

Practice 16 — POP does not remove the first element#

s = [5, 8, 11]
print(s.pop())
print(s.pop())
print(s)

Answer: 11, 8, [5] on three separate lines. 5 remains because it entered first.

Practice 17 — Postfix with subtraction and multiplication#

Question. Evaluate 10 2 3 * - and show final result.

Answer: 4. Push 10, 2, 3; * replaces 2 and 3 with 6; - computes 10−6=4. At the end, the operand stack is [4].

Practice 18 — Trace parentheses#

Question. Are ((A+B)*(C-D)) and ((A+B)*(C-D) both balanced?

Answer: The first is balanced; the second is not. The first ends with an empty bracket stack; the second leaves the outer opening parenthesis unmatched.

Short-answer and reasoning (19–24)#

Practice 19 — Define underflow and overflow clearly#

Answer: Underflow means removal is attempted when the stack is empty. Overflow means an insertion would exceed the capacity of a bounded stack (or, more generally, resources prevent it). With a basic unbounded Python list there is no configured maximum length; .pop() on empty raises IndexError and memory exhaustion may cause MemoryError. These are not interchangeable conditions.

Practice 20 — Why is pop(0) the wrong approach for this implementation?#

Answer: If the newest element is appended to the right end, pop(0) removes the oldest element at the left. That violates LIFO. It is also normally O(n) because remaining list entries must shift.

Practice 21 — Why must postfix subtraction and division preserve order?#

Answer: These operations are not commutative. The first value popped is the right-hand operand, while the next value is the left-hand operand. For 20 5 /, calculate 20/5=4, not 5/20=0.25.

Practice 22 — Why may a postfix expression be invalid even with recognisable tokens?#

Answer: It may contain too many operators (2 +), leave extra operands (2 3), or contain invalid tokens. A well-formed binary postfix expression must never request two operands when fewer are available and must end with exactly one result.

Practice 23 — Compare conversion and evaluation stack roles#

Answer: Infix-to-postfix conversion saves operators and opening parentheses temporarily; operands usually go straight to output. Postfix evaluation saves numbers and intermediate results; operators trigger pops, calculations and pushes. Mixing these roles produces incorrect algorithms.

Practice 24 — How do redo and undo histories relate to stacks?#

Answer: Undo usually applies the most recently recorded reversible action first. A redo history may track undone operations separately; after a new edit, an application may clear its redo history. These are application design choices rather than guaranteed behavior of Python lists.

Applied programming (25–30)#

Practice 25 — Write a stack-based palindrome checker#

Task: Check whether a string is the same forward and backward, using a stack. For this exercise, compare exact characters, including case and spaces.

def is_stack_palindrome(text):
    stack = list(text)
    for char in text:
        if char != stack.pop():
            return False
    return True

print(is_stack_palindrome("level"))  # True
print(is_stack_palindrome("Python")) # False

Explanation: list(text) is a stack from left-to-right characters. Each pop returns the character mirrored from the right end. Any mismatch makes the string non-palindromic.

Practice 26 — Check whether a bounded stack is full#

def bounded_push(stack, value, capacity):
    if len(stack) >= capacity:
        return False
    stack.append(value)
    return True

s = []
print(bounded_push(s, 4, 2))  # True
print(bounded_push(s, 7, 2))  # True
print(bounded_push(s, 9, 2))  # False
print(s)                       # [4, 7]

Explanation: The explicit capacity check prevents a third item. This avoids a false claim that Python's built-in list has a capacity of two.

Practice 27 — Evaluate a simple postfix expression with a trace#

Task: Calculate 5 6 2 / + and list intermediate stacks.

Answer:

The result is 8 mathematically (8.0 with Python /). Both the number and the operand order matter; an unguarded stack evaluator may otherwise silently produce nonsense.

Practice 28 — Count how many parentheses are unmatched#

Task: For a string containing only parentheses as structural brackets, count unmatched openings and closings.

def unmatched_parentheses(expression):
    stack = []
    unmatched_closings = 0
    for ch in expression:
        if ch == "(":
            stack.append(ch)
        elif ch == ")":
            if stack:
                stack.pop()
            else:
                unmatched_closings += 1
    return len(stack), unmatched_closings

print(unmatched_parentheses("(A+B))("))  # (1, 1)

Explanation: One extra closing bracket appears before the final extra opening bracket, so the result is one unmatched opener and one unmatched closer. Merely comparing total counts would miss this nesting problem.

Practice 29 — Convert a small infix expression manually and verify#

Task: Convert (P-Q)*(R+S) to postfix.

Answer: P Q - R S + * (or PQ-RS+* without spaces). First form P Q -, next R S +, and finally multiply the two results. Using the Section S05 converter:

# The helper infix_to_postfix is defined in Section S05.
# print(infix_to_postfix("(P-Q)*(R+S)"))
# P Q - R S + *

Practice 30 — Implement undo for a simple value history#

Task: Record prior counter values so the most recent change can be reversed first.

counter = 0
undo_stack = []

def change_counter(new_value):
    global counter
    undo_stack.append(counter)  # remember previous value
    counter = new_value

def undo():
    global counter
    if not undo_stack:
        return False
    counter = undo_stack.pop()
    return True

change_counter(5)
change_counter(9)
print(counter)      # 9
undo()
print(counter)      # 5
undo()
print(counter)      # 0
print(undo())       # False

Explanation: Each change first pushes the old value. The latest saved value is restored first when undo is invoked, providing the desired LIFO effect. A production editor would manage commands, redo, persistence and more, but the underlying stack concept is the same.

Quick Revision — Stack at a Glance#

Exam-ready algorithm checklist#

• I can distinguish LIFO from FIFO and identify TOP consistently.
• I can predict the value of each POP and the remaining list.
• I can explain underflow and bounded overflow without inventing Python exception classes.
• I can implement all six NCERT stack-of-glasses functions.
• I can reverse a word with pushes and pops instead of a slicing shortcut.
• I can show every opening/closing parenthesis position in NCERT Q4.
• I can calculate NCERT Q5(a) and Q5(b) and explain true-division formatting.
• I can derive both NCERT Q6 postfix expressions with stack/output tables.
• I can push only odd inputs, pop all stored values and find the largest one.
• I can explain why prefix/postfix arithmetic requires careful operand order.

Viva / oral practice — short explained answers#

Why do we call a stack a restricted linear structure? Its items are ordered, but the API permits adding/removing only at TOP.

Can we implement a stack using a Python tuple? A tuple is immutable, so it cannot support normal in-place push and pop. You could create new tuples, but a list is more convenient and efficient for classroom stacks.

What does stack[-1] return? The rightmost (last) item; if the list is empty, IndexError is raised.

Why does postfixed 5 2 - produce 3? The first pop gives right operand 2, the second gives left operand 5; calculate 5-2.

Does display() have to destroy the stack? No. Looping over reversed(stack) reads without popping. A repeated-pop display would empty it unless items were restored.

Why are parentheses unnecessary in valid postfix notation? Operator positions already encode evaluation order, assuming the token sequence is correctly formed.

Can a stack contain repeated elements? Yes. A stack imposes an access discipline, not uniqueness.