#include <iostream>
#include <sstream>
#include <vector>
#include <string>
using namespace std;
class ParserException{
public:
virtual const string& message() = 0;
virtual ~ParserException(){}
};
class BadSyntaxException : public ParserException{
private:
string expected;
string got;
string mess;
int charPosition;
public:
BadSyntaxException(const string& expected, const string& got, int position) :
expected(expected), got(got), charPosition(position){}
virtual ~BadSyntaxException(){}
virtual const string& message(){
ostringstream os;
os << "Syntax error at character position " << charPosition
<< ": expected '" << expected << "' got '" << got << "'";
mess = os.str();
return mess;
}
};
class ParenthesisOutOfBalanceException : public BadSyntaxException{
private:
int numberOfForgottenBrackets;
string mess;
public:
ParenthesisOutOfBalanceException(const string& expected, const string& got, int number, int position) :
BadSyntaxException(expected, got, position), numberOfForgottenBrackets(number){}
const string& message() {
ostringstream os;
os << BadSyntaxException::message() << ", you need to close "
<< numberOfForgottenBrackets << " brackets!";
mess = os.str();
return mess;
}
};
/**
* the data structure which represents the operator tree
*/
template <typename T>class OpTree{
private:
OpTree* right;
OpTree* left;
string value;
static vector<T> value_table;
public:
OpTree(const string& value) : right(NULL), left(NULL), value(value){}
~OpTree(){
if(right != NULL)
delete right;
if(left != NULL)
delete left;
right = NULL;
left = NULL;
}
void setLeftSon(OpTree* left){
this->left = left;
}
void setRightSon(OpTree* right){
this->right = right;
}
void setValues(const vector<T>& table){
value_table = table;
}
/**
* generates the result from the created OpTree
* traverses the tree in postorder
*/
T getResult(){
istringstream is(value);
int index;
is >> index;
if(left == NULL && right == NULL){
return value_table[index];
}
else{
if(value == "|")
return left->getResult() || right->getResult();
else
return left->getResult() && right->getResult();
}
}
};
template <typename T> vector<T> OpTree<T>::value_table;
/**
* creates a syntax tree from the following grammer:
* expressiom ::= term {'|' term}*
* term ::= factor {'&' factor}*
* factor ::= T | '(' expression ')'
*/
template <typename T>class TermParser{
private:
vector<string> to_parse;
OpTree<T>* root;
int numberOfBrackets;
int charPosition;
/**
* creates the non terminal expression according to the grammar rules
*/
void exp() throw (BadSyntaxException){
term();
while(to_parse[0] == "|"){
OpTree<T>* oldRoot = root;
root = new OpTree<T>(to_parse[0]);
root->setLeftSon(oldRoot);
OpTree<T>* oldRoot2 = root;
to_parse.erase(to_parse.begin());
charPosition += 2;
term();
oldRoot2->setRightSon(root);
root = oldRoot2;
}
}
/**
* creates the non terminal term according to the grammar rules
*/
void term(){
factor();
while(to_parse[0] == "&"){
OpTree<T>* oldRoot = root;
root = new OpTree<T>(to_parse[0]);
root->setLeftSon(oldRoot);
to_parse.erase(to_parse.begin());
charPosition+=2;
OpTree<T>* oldRoot2 = root;
factor();
oldRoot2->setRightSon(root);
root = oldRoot2;
}
}
/**
* creates the non terminal factor according to the grammar rules
*/
void factor() throw (ParserException){
if(to_parse[0] == "("){
numberOfBrackets++;
to_parse.erase(to_parse.begin());
charPosition+=2;
exp();
if(to_parse[0] != ")")
throw ParenthesisOutOfBalanceException(")", "missing parenthesis",
numberOfBrackets, charPosition);
numberOfBrackets--;
to_parse.erase(to_parse.begin());
}
else{
for(unsigned int i = 0; i < to_parse[0].size(); i++){
if((to_parse[0])[i] > '9' || (to_parse[0])[i] < '0')
throw BadSyntaxException("[0-9]+", to_parse[0], charPosition);
}
root = new OpTree<T>(to_parse[0]);
to_parse.erase(to_parse.begin());
}
charPosition+=2;
}
public:
TermParser() :
root(NULL), numberOfBrackets(0), charPosition(0){}
~TermParser(){
if(root != NULL)
delete root;
}
/**
* parses the given expression for the given grammar and computes the operator tree
* note: every expression string must be terminated by ;
* note2: the syntaxes must be delimited by a space character (ascii 0x20)
*/
void parse(char* expression) throw (ParserException){
char* token = strtok(expression, " ");
to_parse.push_back(token);
while((token = strtok(NULL, " ")) != NULL)
to_parse.push_back(token);
exp();
if(to_parse.size() == 0 || to_parse[0] != ";"){
throw BadSyntaxException(";", "unknown eof sequence", charPosition);
}
}
/**
* returns the result of the expression after it is parsed
*/
T getResult(){
return root->getResult();
}
void setValues(const vector<T>& table){
root->setValues(table);
}
};
int main(){
//every expression must be terminated by ;
//as delimiter the ' '(whitespace) is used
//e.g. :
char expression[] = "( 0 & 1 & 2 ) | ( 3 & 4 & 5 ) ;";
vector<vector<bool> > truthTable;
//equation1 = (true & false & true) | (true & false & true)
truthTable.push_back(vector<bool>());
truthTable[0].push_back(true);
truthTable[0].push_back(false);
truthTable[0].push_back(true);
truthTable[0].push_back(true);
truthTable[0].push_back(false);
truthTable[0].push_back(true);
//equation2 = (true & false & false) | (true & true & true)
truthTable.push_back(vector<bool>());
truthTable[1].push_back(true);
truthTable[1].push_back(false);
truthTable[1].push_back(false);
truthTable[1].push_back(true);
truthTable[1].push_back(true);
truthTable[1].push_back(true);
TermParser<bool> p;
try{
p.parse(expression);
for(unsigned int i = 0; i < truthTable.size(); i++){
p.setValues(truthTable[i]);
cout << "Equation" << i + 1 << " = " << p.getResult() << endl;
}
}catch(ParserException& e){
cout << "Exception" << endl;
cout << e.message() << endl;
}
}
