Kanchi Sankara Vidhyashram, West Tiruchendur.
Grade XII (Computer Science)
Stack Operations & Postfix — Worksheet
1. Short answer (concepts — concise)
a) Define a stack in one sentence and state its ordering principle.
b) List the two fundamental operations on a stack and briefly state what each does.
c) What is “underflow”? What is “overflow” in the context of a stack? Explain why an
implementation using Python lists typically avoids overflow.
d) Explain why postfix (reverse Polish) notation does not need parentheses.
2. Trace and reasoning (show stack contents after each step)
a) Starting with an empty stack, perform these operations and show the stack (bottom
→ top) after each step: PUSH 5, PUSH 10, PUSH 15, POP, PUSH 7, POP, POP. Also state
the final result when trying one more POP.
b) Show stack states (bottom → top) while evaluating the postfix expression: 3 4 2 * 1 5
-23^^/+
(Assume ^ is exponentiation and evaluate step-by-step; you may leave numeric
simplification to one decimal if needed. Show each push/pop and intermediate value
pushed.)
3. Code writing — implement stack functions (write Python functions as asked)
1.a) Write a Python function opPush(stack, element) that pushes element onto stack
and returns None. Use Python list as the stack. Include an isEmpty(stack) helper.
b) Write a Python function opPop(stack) that pops and returns the top element; if stack
is empty, it should print "underflow" and return None.
c) Write a Python function top(stack) that returns the top element without removing it;
if empty, print "Stack is empty" and return None.
d) Write a Python function display(stack) that prints elements from top to bottom with
a clear label.
2.a.(i) PUSH(N) This function accepts a list of names, N as parameter. It then pushes
only those names in the stack named OnlyA which contain the letter 'A'.
(ii) POPA(OnlyA) This function pops each name from the stack OnlyA and displays it.
When the stack is empty, the message "EMPTY" is displayed.
b. (i) pushEven(N) This function accepts a list of integers named Nas parameter. It then
pushes only even numbers into the stack named EVEN.
(ii) popEven(EVEN) This function pops each integer from the stack EVEN and displays
the popped value. When the stack is empty, the message "Stack Empty" is displayed.
3.A stack named KeyStack contains records of some computer keyboards. Each record
is represented as a list containing Make,Keys, Connectivity. The Make and Connectivity
are strings,and Keys is an integer. For example, a record in the stack may be ('Hitech',
105, 'USB').
Write the following user-defined functions in Python to perform the
specified operations on KeyStack :
(I) push_key(KeyStack, new_key): This function takes the stack KeyStack and a new
record new_key as arguments and pushes this new record onto the stack.
(II) pop_key(KeyStack): This function pops the topmost record from the stack and
returns it. If the stack is already empty, the function should display the message
“Underflow”.
(III) isEmpty(KeyStack): This function checks whether the stack is empty. If the stack is
empty, the function should return True, otherwise the function should return False.
Write the following user-defined functions in Python :
(I) push_vowels(S,St): Here S is a string and St is a list representing a stack. The function
should push all the vowels of the string S onto the stack St. For example, if the string S is
"Easy Concepts", then the function push_vowels() should push the elements 'E','a','o','e'
onto the stack.
(II) pop_one(St) : The function should pop an element from the stack St, and return this
element. If the stack is empty, then the function should display the message ‘Stack
Underflow’,and return None.
(III) display_all(St): The function should display all the elements of the stack St, without
deleting them. If the stack is empty, the function should display the message ‘Empty
Stack’.
[Link] the following infix expressions to postfix.
a) (A + B) * (C - D)
b) A + B * C - D / E
c) ( ( 2 + 3 ) * ( 4 / 2 ) ) + 2
d) ( ( A + B ) * ( C / ( D - E ) ) ) ^ ( F / G )
e) A + ( B * C - ( D / E ^ F ) * G ) * H
6. Postfix evaluation (use stack of operands)
a) Evaluate the postfix expression 7 8 2 * 4 / + using the stack-evaluation algorithm and
show the stack contents after processing each token. Give the final numerical result.
b) Evaluate the postfix expression 5 1 2 + 4 * + 3 - using the stack-evaluation algorithm
and show the stack contents after processing each token. Give the final numerical result.
c) Given A=3, B=5, C=1, D=4 evaluate these postfix expressions, showing stack states
after each operation:
i) A B + C *
ii) A B * C / D *
7. Fill in the Blanks:
[Link] data structure is internally used for implementation of a recursive algorithm?
a) Stack b) Linked List c) Tree d) Queue
[Link] function returns the sum of all elements of a list?
a) count () b) total () c) add () d) sum ()
[Link] stands for
a) Latest in fastest out b) List of File Outputs c) Last in First Out d) First in Last Out
4. The data structure required to check whether an expression contains balanced parenthesis is
________.
a) Tree b) Stack c) Queue d) Array
[Link] of the following list methods accepts exactly 2 parameters?
a) extend() b) pop() c) append() d) insert()
6. Consider the following operation performed on a stack of size 5.
Push(1); Pop(); Push(2); Push(3); Pop(); Push(4); Pop(); Pop(); Push(5);
After the completion of all operation, the number of elements present in stack are:
a) 3 b) 2 c) 1 d) 4
7. Pushing is an act of:
a) Taking off items from stack b) Adding values
c) Adding items to a stack d) Transferring items from stack
[Link] follows the strategy of ________.
a) LIFO b) RANDOM c) FIFO d) LRU
9. What is the result of the following operation?
Top(Push (s, x))
a) s b) x c) Both d) Null
10. Consider the statements given below and then choose the correct output from the given
options: L=[ ’TIC’, ’TAC’] print(L[ :: - 1] )
a) [ ’CAT’, ’CIT’] b) [ ’TIC’, ’TAC’] c) [ ’CIT’, ’CAT’] d) [ ’TAC’, ’TIC’]
[Link] is the conventional name of pointer associated with the stack?
a) FIRST b) REAR c) TOP d) FRONT
[Link] data structure is used for implementing recursion?
a) List b) Queue c) Stack d) Array
13. In a stack, if a user tries to remove an element from empty stack is called
a) Empty b) Overflow c) Underflow d) Garbage collection
[Link] of the following name does not relate to stacks?
a) LIFO lists b) LOFI lists c) FIFO lists d) FILO lists
[Link] of inserting an element in a stack is called ________.
a) Pop b) Create c) Evaluation d) Push
16. Choose the correct output for the following sequence of stack operations.
push (5), push (8), pop,push (2), push (5), pop, push (1)
a) b) c) d) 521
17. Process of removing an element from stack is called ________.
a) Pop b) Create c) Push d) Evaluation
18. The insertion operation in the stack is called ________.
a) insert b) top c) push d) pop
19. ________ is the term used to delete an element from the stack.
a) Pop b) Pull c) Pump d) Push
20. When a stack, implemented as an array/list of fixed size, is full and no new element can be
accommodated, it is called an ________.
a) NOFLOW b) EXTRAFLOW c) UNDERFLOW d) OVERFLOW
21. Which of the following is an application of stack?
a) Infix to postfix b) Finding factorial
c) Reversing of a string d) All of these
22. Act of adding values into a stack is called
a) Pushing b) Polling c) Pulling d) Popping
23. Which data structure is needed to convert infix notation to postfix notation?
a) Branch b) Tree c) Queue d) Stack
24. Which of the following is not an inherent application of stack?
a) Reversing a string b) Job scheduling
c) Implementation of recursion d) Evaluation of postfix expression
25. When a stack is empty and an element’s deletion is tried from the stack, it is called an
________.
a) EXTRAFLOW b) OVERFLOW c) UNDERFLOW d) NOFLOW