Build a hash table using chaining as the collision resolution technique. Inserti
ID: 3823010 • Letter: B
Question
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.
Please write in C++. Thumbs up if everything is correct. Thanks.
Explanation / Answer
Answer:
C++ code:
#include <iostream>
#include <string>
#include <sstream>
#include <ctype.h>
#include <fstream>
#include <math.h>
using namespace std;
class NodeHash
{
/* variables, member functions and constructor */
public:
NodeHash();
NodeHash* Nexth;
string NameGet();
int NumbersGet();
int ScopesGet();
void NameSet(string);
void NumberSet(int);
void ScopeSet(int);
private:
string hName;
int hNumber;
int hScope;
};
/* constructor */
NodeHash::NodeHash()
{
Nexth = 0;
hName = "";
hNumber = 0;
hScope = 0;
}
/* getter for names */
string NodeHash::NameGet()
{
return hName;
}
/* getter for numbers */
int NodeHash::NumbersGet()
{
return hNumber;
}
/* getter for scopes */
int NodeHash::ScopesGet()
{
return hScope;
}
/* setter for names */
void NodeHash::NameSet(string n1)
{
hName = n1;
}
/* setter for scopes */
void NodeHash::ScopeSet(int s1)
{
hScope = s1;
}
/* getter for numbers */
void NodeHash::NumberSet(int s1)
{
hNumber = s1;
}
/* hashString */
int hashString(string n1)
{
int hashVal=0,hSize = n1.size();
for(int inc1= 0;inc1<hSize+1;inc1++)
{
hashVal += (int) n1[inc1] * inc1;
}
return hashVal % 7;
}
/* main */
int main()
{
/* variables */
int CurrScope=0,LinesNum=0;
NodeHash hTable[10];
/* input file */
ifstream fileIn ("InputFile.txt");
if (fileIn.is_open())
{
string num;
while (getline (fileIn,num))
{
LinesNum++;
stringstream Lineff(num);
Lineff >> num;
/* if input equals to START */
if(num == "START")
{
CurrScope++;
while(Lineff >> num);
}
/* if input equals to FINISH */
else if(num == "FINISH")
{
CurrScope--;
while(Lineff >> num);
}
/* if input equals to COM */
else if(num == "COM")
{
while(Lineff >> num);
}
/* if input equals to VAR */
else if(num == "VAR")
{
/* temp */
NodeHash tab;
Lineff >> num;
cout << num << endl;
tab.NameSet(num);
Lineff >> num;
/* if input equals to "=" */
if(num == "=")
{
Lineff >> num;
cout << "IS ";
cout << num << endl;
tab.NumberSet(atoi(num.c_str()));
tab.ScopeSet(CurrScope);
tab.Nexth = &hTable[hashString(tab.NameGet())];
hTable[hashString(tab.NameGet())] = tab;
while(Lineff >> num);
}
}
/* if input equals to PRINT */
else if(num == "PRINT")
{
Lineff >> num;
NodeHash tab = hTable[hashString(num)];
if(tab.ScopesGet() == CurrScope)
{
if(Lineff >> num)
{
/* if encounters "++" */
if(num == "++")
{
cout<<tab.NumbersGet();
cout << tab.NameGet() << " IS " << tab.NumbersGet() + 1 << endl;
while(Lineff >> num);
}
/* if encounters "--" */
else if(num == "--")
{
cout << tab.NameGet() << " IS " << tab.NumbersGet() - 1 << endl;
while(Lineff >> num);
}
/* if encounters "+" */
else if(num == "+")
{
Lineff >> num;
cout << tab.NameGet() << " IS " << tab.NumbersGet() + atoi(num.c_str()) << endl;
while(Lineff >> num);
}
/* if encounters "-" */
else if(num == "-")
{
Lineff >> num;
cout << tab.NameGet() << " IS " << tab.NumbersGet() - atoi(num.c_str()) << endl;
while(Lineff >> num);
}
/* if encounters "/" */
else if(num == "/")
{
Lineff >> num;
cout << tab.NameGet() << " IS " << tab.NumbersGet() / atoi(num.c_str()) << endl;
while(Lineff >> num);
}
/* if encounters "*" */
else if(num == "*")
{
Lineff >> num;
cout << tab.NameGet() << " IS " << tab.NumbersGet() * atoi(num.c_str()) << endl;
while(Lineff >> num);
}
/* if encounters "%" */
else if(num == "%")
{
Lineff >> num;
cout << tab.NameGet() << " IS " << tab.NumbersGet() % atoi(num.c_str()) << endl;
while(Lineff >> num);
}
/* if encounters "^" */
else if(num == "^")
{
Lineff >> num;
cout << tab.NameGet() << " IS " << pow(static_cast<double>(tab.NumbersGet()),atoi(num.c_str())) << endl;
while(Lineff >> num);
}
}
}
/* if it encounters other than this */
else
{
cout << num << "IS UNDEFINED" << endl;
cout << "ERROR HAS OCCURED ON LINE " << LinesNum << endl;
while(Lineff >> num);
}
}
else
{
if(hTable[hashString(num)].NameGet() == num)
{
NodeHash tab = hTable[hashString(num)];
Lineff >> num;
/* if encounters "=" */
if(num == "=")
{
if(tab.ScopesGet() == CurrScope)
{
Lineff >> num;
tab.NumberSet(atoi(num.c_str()));
while(Lineff >> num);
}
}
/* if encounters "++" */
else if(num == "++")
{
while(Lineff >> num);
}
/* if encounters "--" */
else if(num == "--")
{
while(Lineff >> num);
}
}
else
cout << num << " IS UNDEFINED" << endl;
}
}
fileIn.close();
}
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.