Using a Stack

10/17/97

Click here to start

Table of Contents

Programming Assignment 4

Stacks--Chapter 7

Example: Reversing a Word

An Exercise (p.311 text)

Exercise--Answer

Another Exercise (p.311 text)

Exercise--Solution

Exercise--Example

A Stack Application: Balanced Parentheses in Arithmetic Expressions

Balanced Parentheses, ctd.

Balancing Parentheses in Your Head

Balancing in Your Head, ctd.

Balanced Parentheses, ctd.

Balanced Parentheses--Quiz

Basic Calculator Program--p.311ff.

Basic Calculator, ctd.

Basic Calculator, ctd.

Basic Calculator, ctd.

Basic Calculator ctd.,

Finding the Leftmost Innermost Expression

Use of Stacks in Evaluating Arithmetic Expressions

Time Analysis--Just Once!

Array Implementation of the Stack ADT

Linked List Implementation of the Stack ADT

Quiz (Array Implementation)

Evaluating Postfix Expressions

Examples (ctd.)

Algorithm to Evaluate Postfix

Converting Infix to Postfix--Fully Parenthesized Expressions

Converting Infix to Postfix

Fully Parenthesized Expressions

Prefix to Postfix, General Case

Prefix to Postfix, General Case

Prefix to Postfix, Correctness

The N-Queens Problem

The N-Queens Problem

The N-Queens Problem

The N-Queens Problem

The N-Queens Problem

The N-Queens Problem

The N-Queens Problem

How the program works

How the program works

How the program works

How the program works

How the program works

How the program works

How the program works

How the program works

How the program works

How the program works

How the program works

How the program works

How the program works

How the program works

How the program works

How the program works

Pseudocode for N-Queens

Pseudocode for N-Queens

Pseudocode for N-Queens

Pseudocode for N-Queens

Pseudocode for N-Queens

Watching the program work

Author: Michael Main and Walter Savitch

Email: mgv@cs.sc.edu

Home Page: www.cs.sc.edu/~mgv

Other information:
These slides are modifications of slides provided by the authors of the textbook.