PadhaikoAll subjects

Past exam question: 2078 Chaitra (Regular), Q2

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Definition of stack and its operations · Array implementation of…

Question

Define stack. Convert following infix expression to postfix expression showing stack status in each step; A×(B+C) -(B^D)×A + E / F.

Solution

Definition of Stack: A stack is a linear Abstract Data Type (ADT) that follows the Last-In, First-Out (LIFO) principle: insertions (push) and deletions (pop) occur strictly at one end called the top. Attempting to push onto a full stack causes Stack Overflow, and attempting to pop from an empty stack causes Stack Underflow.

Operator Precedence and Associativity Rules:

  1. ^ (Exponentiation): Highest precedence, right-associative.
  2. × (*), /: Medium precedence, left-associative.
  3. +, -: Lowest precedence, left-associative.
  4. ( is pushed directly onto the stack; when ) is scanned, pop operators to output until ( is popped and discarded.
  5. Note: In the printed expression A×(B+C) -(B^D)×A + E / F, × denotes multiplication (*).

Tabular Stack Trace for A*(B+C)-(B^D)*A+E/F:

Scanned SymbolStack (Bottom Top)Postfix OutputAction
A(empty)AAppend operand A
××APush ×
(× (APush (
B× (A BAppend operand B
+× ( +A BPush +
C× ( +A B CAppend operand C
)×A B C +Pop +, discard (
--A B C + ×Pop × (), push -
(- (A B C + ×Push (
B- (A B C + × BAppend operand B
^- ( ^A B C + × BPush ^
D- ( ^A B C + × B DAppend operand D
)-A B C + × B D ^Pop ^, discard (
×- ×A B C + × B D ^Push × ()
A- ×A B C + × B D ^ AAppend operand A
++A B C + × B D ^ A × -Pop × then - (equal/higher precedence), push +
E+A B C + × B D ^ A × - EAppend operand E
/+ /A B C + × B D ^ A × - EPush / ()
F+ /A B C + × B D ^ A × - E FAppend operand F
(end)(empty)A B C + × B D ^ A × - E F / +Pop / then +
Answer:

(or ABC+*BD^A*-EF/+ using * for multiplication).

All past exam questions for Data Structure and Algorithms