Transcript Case Study 3

ADT Stack & Queue
- Case Studies
TCP1201: 2013/2014
ADT Stack: Checking for Balanced Braces

A stack can be used to verify whether a program
contains balanced braces
o An example of balanced braces
- abc{defg{ijk}{l{mn}}op}qr
o An example of unbalanced braces
- abc{def}}{ghij{kl}m
Copyright © 2007 Pearson Education, Inc. Publishing as Pearson Addison-Wesley. Ver 5.0.
ADT Stack: Checking for Balanced Braces

Requirements for balanced braces
Each time you encounter a “}”, it matches an already
encountered “{”
 When you reach the end of the string, you have matched
each “{”
Every time we see a start ‘{', push onto the stack.
Every time we see an end ‘}', pop off the stack.
So the parentheses are not balanced if:
1. We try to pop, but the stack is empty.
2. When we are done, the stack is not empty




Copyright © 2007 Pearson Education, Inc. Publishing as Pearson Addison-Wesley. Ver 5.0.
ADT Stack: Checking for Balanced Braces
Figure 6-3
Traces of the algorithm that checks for balanced braces
Copyright © 2007 Pearson Education, Inc. Publishing as Pearson Addison-Wesley. Ver 5.0.
ADT Stack: Checking for Balanced Braces
bool isBalanced (string expression) {
Stack<char> s;
char temp;
for (int i=0; i<expression.length(); i++) {
if ( expression[i] == '{' )
s.push (expression[i]);
if ( expression[i] == '}' )
if ( s.isEmpty() )
return false;
else
s.pop(temp);
}
if ( !s.isEmpty() )
return false;
return true;
}
ADT Stack: Checking for Balanced Braces
int main() {
string expression;
cout << "Enter a string: ";
cin >> expression;
if (isBalanced(expression))
cout << "Expression is BALANCED!" << endl;
else
cout << "Expression is NOT BALANCED!" << endl;
}
OUTPUT:
ADT Stack: Evaluating Postfix Expressions

In Postfix Notation (RPN), mathematical expressions can
be written without parentheses.




1 2 + 4 + 3 * = ((1+2)+4)*3
Some programming languages such as Postscript use
Postfix Notation.
C++ is built to interpret the standard Infix Notation.
We can get C++ to interpret Postfix Notation using a
stack.
ADT Stack: Evaluating Postfix Expressions

A postfix calculator

When an operand is entered, the calculator


Pushes it onto a stack
When an operator is entered, the calculator



Applies it to the top two operands of the stack
Pops the operands from the stack
Pushes the result of the operation onto the stack
Copyright © 2007 Pearson Education, Inc. Publishing as Pearson Addison-Wesley. Ver 5.0.
8
ADT Stack: Evaluating Postfix Expressions
Figure 6-8
The action of a postfix calculator when evaluating the expression 2 * (3 + 4)
Copyright © 2007 Pearson Education, Inc. Publishing as Pearson Addison-Wesley. Ver 5.0.
9
ADT Stack: Evaluating Postfix Expressions

To evaluate a postfix expression entered as a string of
characters


Use the same steps as a postfix calculator
Simplifying assumptions




The string is a syntactically correct postfix expression
No unary operators are present
No exponentiation operators are present
Operands are single lowercase letters that represent integer
values
Take Home Exercise
Implement the postfix calculator using
the ADT Stack.
Copyright © 2007 Pearson Education, Inc. Publishing as Pearson Addison-Wesley. Ver 5.0.
10
ADT Queue: Character Categorization
Write a program that reads a set of characters as input (each
character is separated by a space), and categories the
characters into 4 different groups, namely number, small
letter, capital letter, and others.
Input characters (Press ENTER to stop):
w 1 ^ B A i 2 l _ 3 4 l N i ^ | a | m |
Numbers: 1 2 3 4
Small Letters: w i l l i a m
Capital Letters: B A N
Others: ^ _ ^ | | |
Copyright © 2007 Pearson Education, Inc. Publishing as Pearson Addison-Wesley. Ver 5.0.
ADT Queue: Character Categorization
• Steps of the program:
1.
2.
3.
Enqueue each character into an input queue.
Categorize the input queue into four queues
according to the type of a character: number, small
letter, capital letter, and others.
Display the characters in each queue by performing
dequeue on each queue until it is empty
Copyright © 2007 Pearson Education, Inc. Publishing as Pearson Addison-Wesley. Ver 5.0.
ADT Queue: Character Categorization
int main() {
Queue<char> input;
char temp;
char character = '\0';
// STEP 1: Enqueue each character into an input queue
cout << "Input characters (Press ENTER to stop):" << endl;
while (cin.peek() != '\n')
{
cin >> character;
input.enqueue(character);
}
cout << endl;
ADT Queue: Character Categorization
// STEP 2: Categorise the input queue into four queues
// according to the type of a character
const int NUM_OF_CATEGORY = 4;
Queue<char> category[NUM_OF_CATEGORY];
string caption[] = {"Numbers", "Small Letters",
"Capital Letters", "Others"};
while (!input.isEmpty())
{
input.peek( temp );
if ( temp >= '0' && temp <= '9')
{
category[0].enqueue( temp );
} else if ( temp >= 'a' && temp <= 'z'){
category[1].enqueue(temp);
} else if (temp >= 'A' && temp <= 'Z') {
category[2].enqueue(temp);
} else {
category[3].enqueue(temp);
}
input.dequeue(temp);
}
ADT Queue: Character Categorization
// Display the content of the queue for each category
for (int i = 0; i < NUM_OF_CATEGORY; ++i)
{
cout << caption[i] << ": ";
while (!category[i].isEmpty())
{
category[i].dequeue(temp);
cout << temp << " ";
}
cout << endl;
}
}