Stack Data Structures and Expression and Management and Expression Evaluation

Definition and Properties of Stacks

• A stack is an ordered collection of data elements where access occurs only at one end called the top.

• It follows the Last In First Out (LIFO) policy.

• Both addition and deletion of data are performed at the top.

Basic Operations of a Stack ADT

• Push: Adds an element to the top of the stack.

• Pop: Removes and returns the top element of the stack.

• Empty: Checks if the stack contains no elements.

• Full: Checks if the stack has reached its maximum capacity.

• Peek: Returns the top-most element without removing it from the stack.

Applications of Stack

• Storing data and addresses in processors.

• Games and card applications.

• Base conversion of numbers.

• Evaluating expressions ($\text{infix}$, $\text{postfix}$, and $\text{prefix}$).

• Facilitating undo and redo operations.

Expression Types and Evaluation

• Infix: Operators are written between operands (e.g., $A + B - C$). These follow BOMDAS precedence. Associativity is left-to-right, except for exponents, which are right-to-left.

• Postfix (Reverse Polish Notation): Operators are written after operands (e.g., $A B C + \times D /$). Evaluation is strictly left-to-right, and no parentheses are required.

• Prefix (Polish Notation): Operators are written before operands. They act on the two nearest values to their right.

Conversion Algorithms

• Infix to Postfix: Involves examining input elements; operands are output immediately while operators are pushed to a stack based on priority levels. Parentheses control the popping and discarding of operators.

• Infix to Prefix: The input string is first reversed, then converted using stack-based logic (similar to postfix but handling parentheses and operator precedence slightly differently), and finally, the output string is reversed.

C++ Implementation and Example

• Stacks can be implemented using arrays or linked lists.

• In C++, the <stack> library provides built-in functionality.

• Example using elements $0.04$, $0.03$, $0.05$, $76.55$, and $23.65$:

  • Initializing stack<double> s and using s.push() for each value.

  • The stack size is retrieved via s.size().

  • The top-most element is accessed using s.top(), which in this case would be $23.65$.