unit3

Stacks Chapter 6

Fundamentals

• A stack is a sequence of data elements of the same type arranged one after another conceptually.

• Elements can be added to the top of the stack only (called "PUSH").

• Elements can be removed from the top of the stack only (called "POP").

Applications of Stacks

• Operating Systems

  • Used for keeping track of method calls in a running program.

• Compilers

  • Used for converting arithmetic expressions to machine code.

Conceptual Picture

• Depending on the implementation of a stack, it may or may not have a maximum capacity.

  • Example:

    • Stacked elements: 20, 31, 12

    • Top points to the most recent element added.

Stack Operations

PUSH Operation

• When PUSHing 49, the stack changes as follows:

  • TOP shifts from 12 to 49. Elements become 49, 12, 31, 20.

POP Operation

• When POPping, the stack changes as follows:

  • TOP shifts from 49 to 12. Elements become 20, 31, 12.

  • Note: Depending on implementation, the element 49 may still be in memory but not part of the stack.

Implementation of a Stack

Using Arrays

• Array structure: Top index keeps track of the last added element.

• The challenge is determining efficiency between different methods of stack implementation.

Basic Stack Operations

• Constructor: creates an empty stack.

• isEmpty: checks if the stack is empty.

• push: adds an element to the top of the stack if it is not full.

• pop: removes the top element from the stack if it is not empty.

Extended Stack Operations

• peek: examines the top element of the stack without removing it (if not empty).

• size: returns the number of elements in the stack, requiring basic operations to implement it.

An IntStack using Arrays

Class Definition

• public class IntStack implements Cloneable

• Contains CAPACITY set to 100, an integer array to hold data, and a "top" to track the last index.

Constructor and Methods

• Constructor initializes the stack.

• isEmpty checks if the top is -1, indicating an empty stack.

• push checks for full stack and adds the item.

• pop checks for empty stack and retrieves the top item.

• peek checks the top item without removing it.

Implementation of a Stack Using Linked Lists

IntStack with Lists

• Structure:

  • public class IntStack implements Cloneable contains a reference to the top node.

• Constructor initializes the top to null.

• isEmpty checks if top is null.

• push creates a new node, linking it to the previous top.

• pop retrieves the top data and adjusts the top pointer.

• peek examines the data at the top node.

Balanced Parentheses

Definition

• An arithmetic expression has balanced parentheses if:

  • Left parentheses equal right parentheses of each type.

  • Each right parenthesis matches the corresponding left parenthesis to its left while balanced.

Examples

• Balanced: ({A + B} – C)

• Not Balanced: ({A + B) – C}

Algorithm for Checking Balanced Parentheses

• Scan the expression left to right.

  • For each left parenthesis found, push onto the stack.

  • For each right parenthesis, pop from the stack.

  • Return false if the stack is empty or mismatched.

  • Return true if the stack is empty at the end of the scan.

Evaluating Expressions

Fully Parenthesized Expressions

• Every operator has a pair of balanced parentheses around its operands.

• Examples of fully parenthesized:

  • ((3 * (5 + 7)) – 9)

  • Not fully-parenthesized: 3 * (5 + 7) – 9

General Strategy

• First operation is within the innermost parentheses.

• Use two stacks: one for operands and one for operators.

• Upon encountering a right parenthesis, perform the operation on popped operands.

Algorithm for Evaluating Expressions

Token Handling

• Each operand/operator/parenthesis is a token.

• NumStack stores operands; OpStack stores operators.

• For each token:

  • Push operands onto the NumStack.

  • Push operators onto the OpStack.

  • For “)”, pop operands and operator, compute result, and push back onto NumStack.

Translating Infix to Postfix

Notation Types

• Infix: Operators between operands (e.g., 3 + 5).

• Prefix: Operators precede operands (e.g., + 3 5).

• Postfix: Operators follow operands (e.g., 3 5 +).

Precedence of Operators

• Higher precedence: multiplication and division before addition and subtraction.

• Parentheses operators have highest precedence.

• Same precedence operators evaluated left to right.

Example Translations

Given Infix Example

• A + B * (C * D - E / F) / G - H

  • Prefix: + A / * B - * C D / E F G H

  • Postfix: A B C D * E F / - * G / + H -.

Evaluating a Postfix Expression

• For each token:

  • Push operands.

  • Pop for operators, compute and push result.

General Expressions for Infix to Postfix

Steps

1. Define precedence function for operators.

2. Initialize an empty string for postfix.

3. For each token:

   • If operand, append to postfix.

   • If “(“, push onto OpStack.

   • If “)”, pop until “(”.

   • If operator, pop based on precedence.

4. At the end, pop remaining operators.

Trace Example of Translation

• From Infix to Postfix: A + B * (C * D - E / F) / G - H

  • Use stack and string representation to keep track of tokens and build the postfix expression step by step.