I am off to a rough start with this program, I have attempted with my best effort, but I am still lost on what I am supposed to do. The program description with sample input and output and my attempt code is below:
Program Specification:
Build a hash table using chaining as the collision resolution technique. Insertions into the hash table will correspond to declarations of variables and values in a program, searches will be requests for the value of a variable. Some variables will be local and have a narrow scope while some variables will be global.
The program will take input from a file, another program written in the omnipotent programming language BORG (Bionicly Omnipotent Resistance Grinders) and generate output from this program.
The BORG language has the following commands (keywords):
- START-FINISH blocks. Indicating different scopes.
- COM - Single line comments: Text should be ignored if on the same line
- VAR varName – Variable Declaration, adds “varName” to the hash table.
- variable = expression – Assignment statements, ie GEORGE = 122. Find GEORGE in the hash table and assign 122 to it.
- ++ - increment operator, syntax: VARIABLE ++
- -- - decrement operator, syntax: VARIABLE --
- expressions, expressions are limited to unary and binary arithmetic, or variable names
- supported operators: + - / * % ^ (plus, minus, divide, multiple, modulo, exponent)
- PRINT – syntax PRINT expression. If the expression is a variable, and this variable is not in scope, then an error message indicating unknown variable x at line number y. The value printed if there is a variable in scope should be the variable with the closest scope.
- Errors – other than the print statements, our interpreter will not be responsible for detecting errors, syntax errors should be disregarded if encountered, assume that the source file is correct.
Our hash function: sum the ordinal values of the characters of the variable multiplied by their position in the string (1-indexing), then taking the modulo by TABLESIZE.
ie. The variable ABC = (65 * 1 + 66 * 2 + 67 * 3) % TABLESIZE
All tokens are separated by one space or a new line.
Output: for this assignment, run your interpreter on this sample source program as well as a program of your own, and turn it the output from both, as well as the source code from your BORG program as well as source code of the assignment and its executable. Zip is good.
Sample program and its output:
Input Output
COM HERE IS OUR FIRST BORG PROGRAM
COM WHAT A ROBUST LANGUAGE IT IS
START
VAR BORAMIR = 25
VAR LEGOLAS = 101
PRINT BORAMIR BORAMIR IS 25
BORAMIR ++
PRINT LEGOLAS LEGOLAS IS 101
PRINT GANDALF GANDALF IS UNDEFINED
PRINT BORAMIR * 2 BOARAMIR * 2 IS 52
COM
COM NESTED BLOCK
COM
START
VAR GANDALF = 49
PRINT GANDALF GANDALF IS 49
PRINT BORAMIR BORAMIR IS 26
FINISH
PRINT GANDALF GANDALF IS UNDEFINED
START
LEGOLAS = 1000
PRINT LEGOLAS LEGOLAS IS 1000
FINISH
PRINT LEGOLAS LEGOLAS IS 1000
LEGOLAS --
PRINT LEGOLAS LEGOLAS IS 999
FINISH
My code:
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <cassert>
#include <utility>
using namespace std;
//! Assumes the data stored has STLVector-like interface
//! (.size(), operator[], ...)
template<class T_>
class HashTable
{
public:
typedef T_ DataType;
class DataWithKey
{
public:
DataWithKey()
{
key = 0;
}
T_ data;
int key;
};
HashTable()
{
m_size = 9;
m_vListIndex.resize(m_size, list<DataWithKey>());
}
size_t hashIntKey(int key) const
{
//Using the division method
return key % m_size;
}
//! Assumes that the data can be interpreted as a string
void print() const
{
int nCollision = 0;
cout<<"HashTable of size "<<m_size<<":"<<endl;
for(size_t i = 0; i < m_vListIndex.size(); ++i)
{
if(m_vListIndex[i].size() > 1)
nCollision += m_vListIndex[i].size() - 1;
for(typename list<DataWithKey>::const_iterator it = m_vListIndex[i].begin();
it != m_vListIndex[i].end();
++it)
{
cout<<"HashTable["<<i<<"]: "<<it->data<<endl;
}
}
// cout<<"N.Hash collisions: "<<nCollision<<endl;
}
void add(int key, const T_& data)
{
size_t posInArray = hashIntKey(key);
DataWithKey dk;
dk.data = data;
dk.key = key;
//Collision resolution by chaining
list<DataWithKey>& lst = m_vListIndex.at(posInArray);
//If key already store, replace data
if(lst.size() != 0)
{
for(typename list<DataWithKey>::iterator it = lst.begin();
it != lst.end();
++it)
{
if(it->key == key)
{
it->data = data;
return;
}
}
}
//No items with that key, store a new one
m_vListIndex[posInArray].push_back(dk);
}
T_& operator[](int key)
{
size_t posInArray = hashIntKey(key);
list<DataWithKey>& lst = m_vListIndex.at(posInArray);
assert( lst.size() != 0 );
for(typename list<DataWithKey>::iterator it = lst.begin();
it != lst.end();
++it)
{
if(it->key == key)
{
return it->data;
}
}
//key not found, user requested invalid data
add(key, "InvalidEntryAdd"); //@note not sure hot to make work with a complete template system
return operator[](key);
}
private:
size_t m_size;
vector< list<DataWithKey> > m_vListIndex;
};
//unsigned int hashString(const string& s)
//{
// unsigned int key = 33;
// for(unsigned int i = 0; i < s.size(); ++i)
// {
// // % 4294967296 not necessary, but there for the example.
// key = (1013904223 + key*1664525) % 4294967296;
// }
// return key % 100;
//}
unsigned int hashString( const string& s)
{
int sum = 0;
for (int k = 0; k < s.length(); k++)
sum = sum + int(s[k]) * (k+1);
return sum % 100;
}
int main()
{
HashTable<string> ht;
ht.add(0, string("HERE IS OUR FIRST BORG PROGRAM"));
ht.add(1, string("WHAT A ROBUST LANGUAGE IT IS"));
ht.print();
cout<<"Start"<<endl;
cout<<" BORAMIR = "<<hashString("Boramir")<<endl;
cout<<" LEGOLAS = "<<hashString("LEGOLAS")<<endl;
cout<<" GANDALF = "<<hashString("GANDALF")<<endl;
cout<<" BORAMIR * 2 = "<<hashString("BORAMIR * 2")<<endl;
cout<<"FINISH"<<endl;
//map <string, int> BORG;
// BORG["BORAMIR"] = 25;
// BORG["LEGOLAS"] = 101;
// BORG.insert(std::pair<string,int>("BORAMIR",25));
// BORG.insert(map<string,int>::value_type("LEGOLAS",7582));
// BORG.insert(std::make_pair(std::string("GANDALF"),5328));
// cout << "Map size: " << BORG.size() << endl;
// for( map<string, int>::iterator ii=BORG.begin(); ii!=BORG.end(); ++ii)
// {
// cout << (*ii).first << ": " << ii->second << endl;
// }
// map<string,int>::iterator it;
// it = BORG.find("Varun");
// cout<<it->second;
cout << endl;
system("pause");
return 0;
}
