#include <stdexcept>
using namespace std;
// logic_error and runtime_error are classes
// that are derived from the exception class
void f(int x) throw(runtime_error)
{
if ( x < 0 ) {
throw runtime_error("f requires argument >=0");
}
// normal processing here
}
Note 1: The throw clause in the function prototype is legal C++ and
serves as documentation that the function may throw the listed
exception(s). If a function can throw more than one exception, they can
all be listed separated by commas.
Note 2: C++ does not require that the throw clause in the
function header. However, if the throw clause is used, the
list should contain all the exception types that the function
may throw.
// 2a: // 2b:
int main() int main()
{ {
try { try {
f(-4); f(-4);
} catch( runtime_error e) { } catch( exception& e) {
cout << e.what() << endl; cout << e.what() << endl;
exit(0); exit(0);
} }
Note 1: Example 2b on the right uses catch by reference
instead of catch by value used by Example 2a. Since
runtime_error is a derived class of exception, the catch block on the
right will also catch exceptions of specific type
runtime_error.
Note 2: If f were to also throw an exception of
specific type logic_error, the catch block in Example 2b would
still catch it, but the catch block of Example 2a would NOT. A
logic_error is a kind of exception, but a
logic_error is NOT a kind of runtime_error.
class exception
{
public:
exception() throw(); // throws no exceptions
exception(const exception&) throw();
exception& operator=(const exception&) throw();
virtual ~exception() throw();
virtual const char* what() const throw();
};
exception
logic_error
length_error
domain_error
out_of_range
invalid_argument
run_time_error
range_error
overflow_error
underflow_error
All of these classes descended from exception have constructors that
take a string. That string will be returned by the what()
method.
#include <iostream>
using namespace std;
template <class T, class S>
void printPair(const pair<T,S>& pr)
{
cout << "(" << pr.first << "," << pr.second << ")" << endl;
}
int main()
{
pair<int, int> p;
p.first = 5;
p.second = 10;
pair<char, string> q('A', "hello");
printPair(p);
printPair(q);
printPair(pair<string, double>("pi", 3.141592));
return 0;
}
Output:
(5,10)
(A,hello)
(pi,3.14159)
When using templates with VisualC++, you may get errors like this: c:\program files\microsoft visual studio\vc98\include\deque(208) : warning C4786: std::reverse_iterator<std::deque<std::pair<Position,Position::Iterator>, std::allocator<std::pair<Position,Position::Iterator> > >::const_iterator,std::pair<Position,Position::Iterator>, std::pair<Position,Position::Iterator> const &,std::pair<Position,Position::Iterator> const *,int> : identifier was truncated to '255' characters in the debug information c:\program files\microsoft visual studio\vc98\include\deque(207) : while compiling class-template member function __thiscall std::deque<std::pair<Position,Position::Iterator>,std::allocator<std::pair<Position,Position::Iterator> > >::~std:: deque<std::pair<Position,Position::Iterator>,std::allocator<std::pair<Position,Position::Iterator> > >(void) c:\program files\microsoft visual studio\vc98\include\deque(208) : <b>warning C4786:</b> 'std::reverse_iterator<std::deque<std::pair<Position,Position::Iterator>,std::allocator<std::pair<Position,Position::Iterator> > >::iterator,std::pair<Position,Positio n::Iterator>,std::pair<Position,Position::Iterator> &,std::pair<Position,Position::Iterator> *,int>' : identifier was truncated to '255' characters in the debug information c:\program files\microsoft visual studio\vc98\include\deque(207) : while compiling class-template member function '__thiscall std::deque<std::pair<Position,Position::Iterator>,std::allocator<std::pair<Position,Position::Iterator> > >::~std:: deque<std::pair<Position,Position::Iterator>,std::allocator<std::pair<Position,Position::Iterator> > >(void)' Maze.cpp c:\program files\microsoft visual studio\vc98\include\stack(22) : warning C4786: 'std::stack<std::pair<Position,Position::Iterator>, std::deque<std::pair<Position,Position::Iterator>, std::allocator<std::pair<Position, Position::Iterator> > > >::stack< std::pair<Position, Position::Iterator>,std::deque<std::pair<Position, Position::Iterator>,std::allocator<std::pair<Position,Position::Iterator> > > >' : identifier was truncated to '255' characters in the debug information MazeApp.cpp Linking... knight.exe - 0 error(s), 3 warning(s)
#include <stack>
using namespace std;
int main()
{
stack< pair<int,int> > s;
for(int i = 1; i <= 5; i++) {
s.push( pair<int,int>(i, i * i) );
}
while( !s.empty() ) {
cout << s.top().first << " squared is " << s.top().second << endl;
s.pop();
}
return 0;
}
Output
5 squared is 25
4 squared is 16
3 squared is 9
2 squared is 4
1 squared is 1
This is the application is mentioned on pages 165-166 of the text as an application using a stack. The C++ STL stack class may be used for this problem.
Write a class ParseBP and a main method that will parse an input file to check that it has properly balanced curly braces, square brackets, and parentheses - '{', '}', '[', ']', '(', and ')'.
Your program should prompt for the input file name.
If the file test1.txt contains:
This file has balanced curly braces, square brackets
and parentheses: {}, [] and (). Note that these
characters are not required to balance inside
quoted strings. E.g., "){[[]".
a sample run might be:
ParseBP
Input file name: test1.txt
01. This file has balanced curly braces, square brackets
02. and parentheses: {}, [] and (). Note that these
03. characters are not required to balance inside
04. quoted strings. E.g., "){[[]".
Input is balanced.
In addition to reporting a valid input file like the one above, your program should check for and report the following errors:
File test2.txt:
[This ({line} is balanced) ],
but this character ] is not.
--------------------------------
ParseBP
Input filename: test2.txt
01. [This ({line} is balanced) ],
02. but this character ]
Error: Line 2. Closing character ']', with no matching opening character.
File test3.txt:
(This left parenthesis
is not "closed"! [Balanced
square brackets], then a }
at the end.
-----------------------------
ParseBP
Input filename: test3.txt
01. (This left parenthesis
02. is not "closed"! [Balanced
03. square brackets], then a }
Error: Line 3. Symbol '}' is the wrong closing symbol for char = '(', line 1
File test4.txt: Opening square bracket, [, is not matched when end of file reached. -------------------------- ParseBP Input filename: test4.txt 01. Opening square 02. bracket, [, is not matched 03. when end of file reached. Error: At end of file, no closing symbol found for char = '[', line 2
- You will probably want to use a istream method. However, instead of using the cin.getline(buf, N), it will probably be better to use the get() method. This method returns the int -1 at end of file. Otherwise, the return value can be cast to a char.
- Use a stack to keep track of the opening symbols - '{', '[', '('. You might want to push an object that has both the opening symbol and the line number where it occurred.
- When a character is read, it can also be printed to the output.
- When the characer '\n' is read, a line count can be incremented.
7 13 0 0 0 -1 0 0 -1 -1 -1 0 0 0 0 0 -1 0 0 0 -1 0 0 0 0 0 -1 0 0 -1 -1 -1 0 -1 0 -1 0 -1 0 -1 0 0 -1 -1 -1 0 0 0 -1 0 -1 0 0 0 0 0 0 0 0 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0
1 2 3 X 0 0 X X X 0 0 0 0 0 X 4 5 6 X 0 0 0 0 0 X 0 0 X X X 7 X 0 X 0 X 0 X 0 0 X X X 8 0 0 X 0 X 0 0 0 0 0 0 0 9 X X X X 0 X X X X X X X 10 X X X X X X X X X X X X 11 12 13 14 15 16 17 18 19
The book discusses backtracking and gives some framework code in section 4.5 where recursion is being discussed.
However, the main part of the algorithm can be written without recursion by using a stack instead.
Backtracking is appropriate when a solution to a problem is made up of incremental steps where at each step there may be several choices to be made. Backtracking is a systematic way of exploring all possibilities until a solution is found or else having exhausted all the possibilities, discovering that no solution exists.
#ifndef MAZE_H
#define MAZE_H
#ifdef WIN32
#pragma warning( disable: 4786)
#endif
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdlib>
#include <string>
#include <stdexcept>
using namespace std;
#include "Position.h"
using namespace std;
class Maze
{
int **grid;
int rows;
int cols;
int move;
public:
static const int TRIED;
static const int FREE;
static const int WALL;
Maze() : rows(0), cols(0), move(0) {}
Position generateInitialState();
void readData(istream& is);
void setData(int m[], int r, int c) {
grid = new int *[r];
for(int i = 0; i < r; i++) {
grid[i] = new int[c];
for(int j = 0; j < c; j++) {
grid[i][j] = m[c*i + j];
}
}
rows = r;
cols = c;
}
bool valid(const Position& pos);
void record(const Position& pos);
bool done(const Position& pos);
void undo(const Position& pos);
string toString() const;
};
ostream& operator<<(ostream& os, const Maze& a);
#endif
#ifndef POSITION_H
#define POSITION_H
#ifdef WIN32
#pragma warning( disable: 4786)
#endif
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <stdexcept>
using namespace std;
class Position
{
int row;
int col;
public:
class Iterator
{
friend class Position;
const Position *basepos;
int dir;
public:
Iterator() : basepos(0), dir(0) {}
Iterator operator++(int); //Exercise
Position operator*() const;
bool operator!=(const Iterator& p) const;
private:
Iterator(const Position* p, int d = 0) : basepos(p), dir(d) {}
};
Position() : row(-1), col(-1) {}
Position(int r, int c) : row(r), col(c) {}
Iterator begin() const;
Iterator end() const;
void setPosition(int r, int c);
int getRow() const;
int getCol() const;
};
#endif
#ifndef BACKTRACK_H
#define BACKTRACK_H
#ifdef WIN32
#pragma warning( disable: 4786)
#endif
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <stdexcept>
#include <stack>
#include "Maze.h"
#include "Position.h"
using namespace std;
class BackTrack
{
public:
BackTrack(const Maze& a) : app(a) {}
bool tryToSolve(Position pos);
protected:
Maze app;
};
#endif
#include "BackTrack.h"
#ifdef WIN32
#pragma warning( disable: 4786)
#endif
using namespace std;
bool BackTrack::tryToSolve(Position pos)
{
bool success = false;
stack< pair<Position, Position::Iterator> > s;
Position::Iterator p;
if (!app.valid(pos)) {
return false;
} else {
app.record(pos);
}
s.push(pair<Position, Position::Iterator>(pos, pos.begin()));
while( !success && !s.empty() ) {
pos = s.top().first;
p = s.top().second;
if ( app.done(pos) ) {
success = true;
} else if ( p != pos.end() ) {
if ( app.valid(*p) ) {
pos = *p;
app.record(pos);
s.push(pair<Position, Position::Iterator>(pos, pos.begin()));
} else {
s.top().second++;
}
} else {
app.undo(pos);
s.pop();
}
}
return success;
}
#include "Position.h"
#ifdef WIN32
#pragma warning( disable: 4786)
#endif
Position::Iterator Position::Iterator::operator++(int) //Exercise
{
Position::Iterator it(*this);
if ( dir == 4 ) {
throw invalid_argument("Operator++ is invalid; Iterator is at end");
}
dir++;
return it;
}
Position Position::Iterator::operator*() const
{
int r, c;
r = basepos->getRow();
c = basepos->getCol();
switch(dir) {
case 0: // up
r--;
break;
case 1: // right
c++;
break;
case 2: // down
r++;
break;
case 3: // left
c--;
break;
default:
throw out_of_range("Direction has out of range value");
}
return Position(r,c);
}
bool Position::Iterator::operator!=(const Position::Iterator& p) const
{
return basepos != p.basepos || dir != p.dir;
}
Position::Iterator Position::begin() const
{
return Position::Iterator(this);
}
Position::Iterator Position::end() const
{
return Position::Iterator(this, 4);
}
void Position::setPosition(int r, int c)
{
row = r;
col = c;
}
int Position::getRow() const
{
return row;
}
int Position::getCol() const
{
return col;
}
#include "Maze.h"
#ifdef WIN32
#pragma warning( disable: 4786)
#endif
const int Maze::TRIED = -2;
const int Maze::FREE = 0;
const int Maze::WALL = -1;
Position Maze::generateInitialState()
{
return Position(0,0);
}
void Maze::readData(istream& is)
{
int r, c;
is >> r >> c;
grid = new int *[r];
for(int i = 0; i < r; i++) {
grid[i] = new int[c];
for(int j = 0; j < c; j++) {
is >> grid[i][j];
}
}
rows = r;
cols = c;
}
bool Maze::valid(const Position& pos)
{
int r = pos.getRow();
int c = pos.getCol();
return ( 0 <= r && r < rows && 0 <= c && c < cols &&
grid[r][c] == Maze::FREE );
}
void Maze::record(const Position& pos)
{
int r = pos.getRow();
int c = pos.getCol();
grid[r][c] = ++move;
}
bool Maze::done(const Position& pos)
{
int r = pos.getRow();
int c = pos.getCol();
return (r == rows - 1) && (c == cols - 1);
}
void Maze::undo(const Position& pos)
{
move--;
grid[pos.getRow()][pos.getCol()] = Maze::TRIED;
}
string Maze::toString() const
{
stringstream s;
for (int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
s.width(3);
if ( grid[i][j] == Maze::TRIED ) {
s << 0;
} else if ( grid[i][j] == Maze::WALL ) {
s << 'X';
} else {
s << grid[i][j];
}
}
s << endl;
}
return s.str();
}
ostream& operator<<(ostream& os, const Maze& a)
{
os << a.toString();
return os;
}
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <stdexcept>
#include "Maze.h"
#include "BackTrack.h"
using namespace std;
#ifdef WIN32
#pragma warning( disable: 4786)
#endif
int main()
{
int g[4*6] =
{
0, 0, 0, -1, 0, 0 ,
0, -1, -1, 0, 0, 0 ,
0, -1, 0, 0, -1, 0 ,
0, 0, 0, -1, -1, 0
};
Maze m;
m.setData(g, 4, 6);
BackTrack bt(m);
Position pos = m.generateInitialState();
if ( bt.tryToSolve(pos) ) {
cout << m << endl;
} else {
cout << "No solution" << endl;
}
ifstream ifs;
ifs.open("m1.txt");
if (!ifs) {
cout << "Can't open m1.txt" << endl;
}
m.readData(ifs);
BackTrack bt2(m);
pos = m.generateInitialState();
if ( bt2.tryToSolve(pos) ) {
cout << m << endl;
} else {
cout << "No solution" << endl;
}
return 0;
}