I have recently been trying to build a parser. After a month of trying and getting nowhere fast I decided, like I should have at begining, to research how parsers work and what they do.
After a little research, I learned that parsers create a tree like structure of the language grammar, official called a abstract syntax tree. After researching more, I then learned that I could create a AST using stacks.
I figured I could create a stack using a linked list in C++. Yes I know that their some standard library containers that could probably(more efficiently as well) do the same thing. I decided however, that since I'm still learning C++, I should make my own. It didn't seem to hard, and looked like a fun project.
To get the basics of what I needed to do, I followed this tutorial series. After getting the basic framework from the tutorial, I added several more functions to my linked list class that do some basic operations. I'll try to give a brief overview of the functions, although there pretty self-explanatory.
add_node(). Adds an element.delete_node(). Removes an element.print_stack(). Prints the entire stack.pop(). Deletes the first element from the stack.push(). Deletes the last element from the stack.size(). Gets the size(as in the number of elements) of the stack.last(). Gets the last element in the stack.at(). Gets the element at the given index.get_next(). Gets the element at the index after the index the given index.
And here's what everyone really wants; the code dump:
stack.h
#ifndef STACK_H
#define STACK_H
#include <iostream>
using std::cout;
using std::endl;
#include<string>
template <typename T>
class Stack {
private:
typedef struct node {
T data;
node *next;
} *node_ptr;
node_ptr head;
node_ptr curr;
node_ptr temp;
public:
Stack();
void add_node(T add_data);
void delete_node(T del_data);
void pop();
void push();
void print_stack();
int size();
T last();
T at(int index);
T get_next(int index);
};
#endif
stack.cpp
#include "stack.h"
template <typename T>
Stack<T>::Stack() {
head = NULL;
curr = NULL;
temp = NULL;
}
template <typename T>
void Stack<T>::add_node(T add_data) {
node_ptr n = new node;
n->next = NULL;
n->data = add_data;
if (head != NULL) {
curr = head;
while (curr->next != NULL) {
curr = curr->next;
}
curr->next = n;
}
else {
head = n;
}
}
template <typename T>
void Stack<T>::delete_node(T del_data) {
node_ptr del_ptr = NULL;
temp = head;
curr = head;
while (curr != NULL && curr->data != del_data) {
temp = curr;
curr = curr->next;
}
if (curr == NULL) {
cout << "Error: [" << del_data << "] was not in the stack" << endl;
delete del_ptr;
}
else {
del_ptr = curr;
curr = curr->next;
temp->next = curr;
if (del_ptr == head) {
head = head->next;
temp = NULL;
}
delete del_ptr;
cout << "The value [" << del_data << "] was deleted" << endl;
}
}
template <typename T>
void Stack<T>::pop() {
temp = head;
head = head->next;
delete temp;
}
template <typename T>
void Stack<T>::push() {
if (head->next == NULL) {
delete head;
head = NULL;
}
else {
node_ptr next_to_end = head;
node_ptr end = head->next;
while (end->next != NULL) {
next_to_end = end;
end = end->next;
}
delete end;
next_to_end->next = NULL;
}
}
template <typename T>
void Stack<T>::print_stack() {
curr = head;
while (curr != NULL) {
cout << curr->data << endl;
curr = curr->next;
}
}
template <typename T>
int Stack<T>::size() {
node_ptr p = head;
int count;
while (p != NULL) {
count++;
// this is used to increment p to the next node
// in the linked list. Once be equals NULL
// the while loop will break
p = p->next;
}
return count;
}
template <typename T>
T Stack<T>::last() {
if (head == NULL) {
return head->data;
}
else {
node_ptr end = head;
while (end->next != NULL) {
end = end->next;
}
return end->data;
}
}
template <typename T>
T Stack<T>::at(int index) {
curr = head;
int count = 0;
while (curr != NULL){
if (count == index){
return curr->data;
}
count++;
curr = curr->next;
}
if (curr == NULL) {
cout << "Error: [" << index << "] does not exist" << endl;
}
}
template <typename T>
T Stack<T>::get_next(int index) {
curr = head;
int count = 0;
while (curr != NULL){
if (count == index){
return curr->next->data;
}
count++;
curr = curr->next;
}
if (curr == NULL) {
cout << "Error: [" << index << "] does not exist" << endl;
}
}
template class Stack<int>;
template class Stack<float>;
template class Stack<char>;
template class Stack<std::string>;
stddata structures? There'sstd::stackalready there. \$\endgroup\$