|
a finite list with zero or more elements
LIFO insert, delete all take place at head
S = ( a0, a1, .... ,an-1 ) ai is on top of i-1 an-1 -- top element e.g. ( A, B, C, D, E ) Adaptors
stack <list<double> > s2; stack <string> s3; default is deque |
|
infix arithmetic
-
operator is always between 2 numbers ( operands )
postfix arithmetic
-
operator follows operands
| infix | postfix |
|---|---|
| 7 - 2 | 7, 2, - |
| 7 - 2 * 3 | 7, 2, 3, *, - |
| 4 * 2 - 7 | 4, 2, *, 7, - |
| ( 3 + 4 / 2 ) * ( 5 * 3 - 6 ) - 8 | 3, 4, 2, /, +, 5, 3, *, 6, -, *, 8, - |
Evaluate a postfix expression
- postfix stack stores all tokens ( numbers and operators )
- evaluation stack stores numbers for evaluation
- perform operation
- save result in evaluation stack
e.g. 13, 4, -, 2, 3, *, +
|
|
|
|
|
|
|
|
|
|
FIFO ( first in first out )
insertions at one end -- rear ( tail )
deletions at another end -- front ( head )
Q = ( a0, a1, .... ,an-1 )
ai+1 is behind ai
an-1 -- rear element
Array
Circular Queue
head ( front ) at N - 1, tail ( rear ) at 0
Linked List
How to convert from infix to postfix?
Observations:
( ( ( A - ( B * C ) ) + ( D * E ) ) - ( A / C ) )
( ( ( A- ( B * C ) ) + ( D * E ) ) - ( A / C ) )
( B * C ) is translated to B C *
( ( ( A B C * - ( D E * + ( A C / -
A B C * - D E * + A C / -
which is the required postfix expression
Since orders of operands of infix and postfix are the same, we can
scan the infix expression and form postfix expression by parsing
the operands and use a queue to hold them
on the other hand we can use an stack to hold the operators
e.g. A + B * C
|
|
|
|
||||||||||||||||||||||||
|
|
|
So the postfix expression is :
|
||||||||||||||||||||||||
e.g. A /( B + C ) * D
|
|
|
|
|
|||||||||||||||||||||||||||
|
|
|
|
|
|||||||||||||||||||||||||||
|
|
Infix stack empty.
So done! postfix: A B C + / D * |
|||||||||||||||||||||||||||||
//token.h
#ifndef TOKEN_H
#define TOKEN_H
#include <string>
#include <stack>
#include <queue>
#include <ctype.h>
#include <stdio.h>
typedef double dataType; //could be int or double
enum whatKind { operate, number };
class TOKEN {
public:
whatKind kind;
dataType num;
char op;
};
void in2post ( stack<TOKEN> &infix, queue<TOKEN> &postq );
dataType evaluate ( queue<TOKEN> &post );
#endif
|
//util.h #ifndef UTIL_H #define UTIL_H void q2stack( queue<TOKEN> &q, stack<TOKEN> &s ); void reverse_stack( stack<TOKEN> &s, stack<TOKEN> &sr ); bool c_is_an_operator( char c ); void print_queue( queue<TOKEN> q ); void print_stack( stack<TOKEN> s ); #endif |
//in2postd.cpp
#include "token.h"
int precedence ( char c )
{
switch ( c ) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
}
return 0; //lowest
}
void transfer ( stack<TOKEN> &s, queue<TOKEN> &q )
{
q.push( s.top() );
s.pop(); //remove top element of stack
}
void in2post ( stack<TOKEN> &infix, queue<TOKEN> &postq )
{
stack <TOKEN> opstack; //operator stack
TOKEN a;
while ( !infix.empty() ) {
a = infix.top(); //get a Token from infix stack
infix.pop(); //remove token at top
if ( a.kind == number )
postq.push( a ); //enter a to postfix queue
else if ( opstack.empty() )
opstack.push( a ); //put token in operator stack
else if ( a.op == '(' ) //'(' has lowest precedence, always put it in op stack
opstack.push( a );
else if ( a.op == ')' ){ //encounters right parenthesis, so transfer everything enclosed by ( .. )
while ( opstack.top().op != '(' )
transfer ( opstack, postq );
opstack.pop(); //remove '(' after the transfer
} else {
while ( !opstack.empty() &&
precedence( a.op ) <= precedence( opstack.top().op ) )
transfer ( opstack, postq );
opstack.push( a );
}
} //while
while ( !opstack.empty() )
transfer ( opstack, postq );
}
|
//evaluate.cpp
#include "token.h"
//evaluates postfix expression represented as a queue of tokens
//assumes that postfix expression is correctly formed
dataType evaluate ( queue<TOKEN> &post )
{
stack<TOKEN> eval;
dataType first, second, ans;
char bin_op;
TOKEN tp, te;
while ( !post.empty() ) {
tp = post.front();
post.pop();
if ( tp.kind == number ) //number
eval.push( tp ); //save the number on evaluation stack
else { //its an operator
te = eval.top(); //get a 'number' from eval stack
first = te.num;
eval.pop();
te = eval.top(); //get a second 'number'
second = te.num;
eval.pop();
bin_op = tp.op;
switch ( bin_op ) {
case '+' :
ans = second + first;
break;
case '-' :
ans = second - first;
break;
case '*' :
ans = second * first;
break;
case '/' :
ans = second / first;
break;
} //switch
te.num = ans; //save the result
eval.push ( te );
} //else
} //while
te = eval.top();
return te.num;
}
|
e.g. nonattacking queens
| Q | |||||||
| Q | |||||||
| Q | |||||||
| Q | |||||||
| Q | |||||||
| Q | |||||||
| Q | |||||||
| Q |
Brute force
 |
64 8 |
 |
= 4,426,165,368 |
Only one queen in each row
Rejects position whose column or diagonals are guarded
To solve the problem, when we place a queen on a square, we check if is under attack; if no, proceed; if yes, remove the queen and back track
| ↑ r1 row r2 ↓ |
|
//queen8.cpp
#include <iostream.h>
class queen8
{
public:
queen8();
void clearBoard();
void displayBoard();
void placeQueen( int col, bool &done );
private:
enum square{QUEEN, EMPTY};
square board[8][8];
void setQueen( int row, int col ); //set to square( row, col) to QUEEN
void removeQueen( int row, int col ); //set to EMPTY
bool isUnderAttack( int row, int col );
//determines whether ( row, col ) is under attack by any
// queens 1 through col-1
// int index( int n );
};
queen8::queen8()
{
int i, j;
for ( i = 0; i < 8; ++i )
for( j = 0; j < 8; ++j )
board[i][j] = EMPTY;
}
void queen8::placeQueen( int col, bool & done )
{
if ( col > 7 )
done = true;
else {
done = false;
int row = 0;
while ( !done && ( row < 8 ) ) {
if ( isUnderAttack( row, col ) )
++row;
else { //place queen and consider next column
setQueen( row, col );
placeQueen( col+1, done );
if ( !done ) { //if no queen is possible in next col
//backtrack
removeQueen( row, col );
++row;
}
} //else
}//while
} //else
} //queen8
void queen8::setQueen( int row, int col )
{
board[row][col] = QUEEN;
}
void queen8::removeQueen( int row, int col )
{
board[row][col] = EMPTY;
}
bool queen8::isUnderAttack( int row, int col )
//precondition : each column between 0 and col-1
//has a queen placed in it
{
int r1, r2, c;
r1 = row-1;
r2 = row+1;
for ( c = col-1; c >= 0 ; --c ) {
if ( board[row][c] == QUEEN )
return true;
if ( r1 >= 0 ) {
if ( board[r1][c] == QUEEN )
return true;
--r1;
}
if ( r2 < 8 ) {
if ( board[r2][c] == QUEEN )
return true;
++r2;
}
} //for
return false;
}
void queen8::displayBoard()
{
int row, col;
cout << endl;
for ( row = 0; row < 8; ++row ) {
for ( col = 0; col < 8; ++col ) {
if ( board[row][col] == QUEEN )
cout << "Q ";
else
cout << "X ";
}
cout << endl;
}
}
void main()
{
queen8 q8;
bool done = false;
q8.placeQueen( 0, done );
q8.displayBoard();
}
|
|
|