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):

  1. START-FINISH blocks. Indicating different scopes.
  2. COM - Single line comments: Text should be ignored if on the same line
  3. VAR varName – Variable Declaration, adds “varName” to the hash table.
  4. variable = expression – Assignment statements, ie GEORGE = 122. Find GEORGE in the hash table and assign 122 to it.
  5. ++ - increment operator, syntax: VARIABLE ++
  6. -- - decrement operator, syntax: VARIABLE --
  7. expressions, expressions are limited to unary and binary arithmetic, or variable names
  8. supported operators: + - / * % ^ (plus, minus, divide, multiple, modulo, exponent)
  9. 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.
  10. 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;
    }

Edited 1 Year Ago by aeck

What you are supposed to do...

1)Read in a given file which contains BORG programs
2)Parse tokens from the read in data.
2.1)If you read in the file data line-by-line, split each token with a white space
3)Add any variables found in the program to your "hash table"
4)If there is any assigned/changed value to any variables, update the value to the variable in "hash table"
5)If found any error, print it out at the line it is found
5.1)Error could be variable out of scope, syntax error (expression), etc.

The hash table in this assignment is a simple table look up for variables and their values at various scopes. You need to keep track of which variables are alive within a certain scope and be able to retrieve/check against your current hash table.

Edited 1 Year Ago by Taywin

I am writing the code in C++ to implement the borg language.

I have an updated piece of code that I have been working on. But I am still having trouble with a few of the lines.

#include <iostream>
#include <string>
#include <sstream>
#include <ctype.h>
#include <fstream>
#include <math.h>

using namespace std;

class node{
public:
    node();
    node* next;
    string getName();
    int getNum();
    int getScope();
    void setName(string);
    void setNum(int);
    void setScope(int);

private:
    string name;
    int num;
    int scope;
};
node::node(){
    next = 0;
    name = "";
    num = 0;
    scope = 0;
}
string node::getName(){
    return name;
}
int node::getNum(){
    return num;
}
int node::getScope(){
    return scope;
}
void node::setName(string s){
    name = s;
}
void node::setScope(int x){
    scope = x;
}
void node::setNum(int x){
    num = x;
}
int hashString(string s){
    int hash=0,size = s.size();
    for(int i= 0;i<size+1;i++)
    {
        hash += (int) s[i] * i;
    }
    return hash % 7;
}


//int hashString(string s);

int main()
{
    int curr_scope=0,num_line=0;

    node ht;

    node table[7];

    //node hashString;

     ifstream myfile ("input.txt");
     if (myfile.is_open()){
    string s;
          while (getline (myfile,s))
          {
            num_line++;
              stringstream line(s);
            line >> s;
            if(s == "START")
            {
                curr_scope++;
                while(line >> s);
            }
            else if(s == "FINISH")
            {
                curr_scope--;
                while(line >> s);
            }
            else if(s == "COM")
            {
                while(line >> s);
            }
            else if(s == "VAR")
            {
                node temp;
                line >> s;
                cout << s << endl;
                temp.setName(s);
                line >> s;
                if(s == "=")
                {
                    line >> s;
                    cout << "IS ";
                    cout << s << endl;
                    temp.setNum(atoi(s.c_str()));
                    temp.setScope(curr_scope);

                   // if(table[hashString(temp.getName())] != 0)
                   // {
                        temp.next = &table[hashString(temp.getName())];
                        table[hashString(temp.getName())] = temp;
                        while(line >> s);
                   // }
                   // else if(table[hashString(temp.getName())] == 0)
                   // {
                     //   table[hashString(temp.getName())] = temp;
                      //  while(line >> s);
                   // }
                    //else
                    //{
                    //    cout << "UNABLE TO ADD " << temp.getName() << "TO THE TABLE" << endl;
                   //     while(line >> s);
                   // }
                }
            }
            else if(s == "PRINT")
            {
                line >> s;

                node temp = table[hashString(s)];
                if(temp.getScope() == curr_scope)
                {
                    if(line >> s)
                    {
                        if(s == "++")
                        {
                            cout << temp.getName() << " IS " << temp.getNum() + 1 << endl;
                            while(line >> s);
                        }
                        else if(s == "--")
                        {
                            cout << temp.getName() << " IS " << temp.getNum() - 1 << endl;
                            while(line >> s);
                        }
                        else if(s == "+")
                        {
                            line >> s;
                            cout << temp.getName() << " IS " << temp.getNum() + atoi(s.c_str()) << endl;
                            while(line >> s);
                        }
                        else if(s == "-")
                        {
                            line >> s;
                            cout << temp.getName() << " IS " << temp.getNum() - atoi(s.c_str()) << endl;
                            while(line >> s);
                        }
                        else if(s == "/")
                        {
                            line >> s;
                            cout << temp.getName() << " IS " << temp.getNum() / atoi(s.c_str()) << endl;
                            while(line >> s);
                        }
                        else if(s == "*")
                        {
                            line >> s;
                            cout << temp.getName() << " IS " << temp.getNum() * atoi(s.c_str()) << endl;
                            while(line >> s);
                        }
                        else if(s == "%")
                        {
                            line >> s;
                            cout << temp.getName() << " IS " << temp.getNum() % atoi(s.c_str()) << endl;
                            while(line >> s);
                        }
                        else if(s == "^")
                        {
                            line >> s;
                            cout << temp.getName() << " IS " << pow(temp.getNum(),atoi(s.c_str())) << endl;
                            while(line >> s);
                        }
                    }
                }
                else
                {
                    cout << s <<  "IS UNDEFINED" << endl;
                    cout << "ERROR HAS OCCURED ON LINE " << num_line << endl;
                    while(line >> s);
                }
            }
            else
            {
                if(table[hashString(s)].getName() == s)
                {
                    node temp = table[hashString(s)];
                    line >> s;
                    if(s == "="){
                        if(temp.getScope() == curr_scope){
                            line >> s;
                            temp.setNum(atoi(s.c_str()));
                            while(line >> s);
                        }
                    }
                    else if(s == "++")
                    {
                        //table[hash(temp)].setNum(table[hash(temp)].getNum()+1);
                        while(line >> s);
                    }
                    else if(s == "--")
                    {
                        //table[hash(temp)].setNum(table[hash(temp)].getNum()-1);
                        while(line >> s);
                    }
                }
                else
                    cout << s << " IS UNDEFINED" << endl;
            }
      }
    myfile.close();
    }

    return 0;
}

My output is below : (It should match the output I pasted above)

BORAMIR
IS 25
LEGOLAS
IS 101
BORAMIR IS UNDEFINED
GANDALFIS UNDEFINED
ERROR HAS OCCURED ON LINE 9
LEGOLAS IS 202
GANDALF
IS 49
BORAMIRIS UNDEFINED
ERROR HAS OCCURED ON LINE 17
GANDALFIS UNDEFINED
ERROR HAS OCCURED ON LINE 19
LEGOLASIS UNDEFINED
ERROR HAS OCCURED ON LINE 22

It should be:

BORAMIR IS 25

LEGOLAS IS 101
GANDALF IS UNDEFINED
BOARAMIR * 2 IS 52





GANDALF IS 49
BORAMIR IS 26

GANDALF IS UNDEFINED


LEGOLAS IS 1000

LEGOLAS IS 1000

LEGOLAS IS 999

Looking at your output and expected output (not at your code), this tells me that you incorrectly deal with variable scopes. When a scope starts, you need to add any variable found inside the scope as a list. When a scope ends, you MUST remove all new varibles created inside the scope. How to keep track of which variables should remain or delete, that's the purpose of this assignment for you -- find a way to keep track of them and their values.

Your current hash table structure is not a table, but rather an object (node). You then overwrite the variable (temp) over and over again. You have a pointer next but never use it. In other words, you need to implement a way to add variable correctly in the way that it creates a table (chain).

Also, you need to REMOVE any variable when it is out of scope. Currently, you don't do that. This will result in variable remains in the table.

Can you please provide me with an example, I am not sure how to create a table(chain)

No, this is my Assignment4 for my CS41 data structure class at IVC. I saw those paid projects as well, I assume other students had difficulty completing the assignment as well.

Maybe this link could help you understand a hash table better :) It also contains algorithm to solve collision as well.

Comments
Good hash there.
This article has been dead for over six months. Start a new discussion instead.