#include <string>
#include <vector>
#include <cstdlib>
#include "genericLinkedListStack.h"

using namespace std;

vector<string> convert2Vec(string line) //done
{
    //convert the string to put into a vector
    vector<string> equation;
    for(int i=0; i<line.size(); i++){
        if(line[i] != ' '){
            if((equation.size() != 0)  && (line[i] >= '0') && (line[i] <= '9') ){
                if(line[i-1] >= '0' && line[i-1] <= '9'){
                    equation[equation.size()-1] += line[i];
                } else {
                    equation.push_back(string(1,line[i]));
                }
            } else {
                equation.push_back(string(1,line[i]));
            }
        }
    }
    return equation;
}

/*
returns:
    0 = has no addition or subtraction, but has multiplication or division
    1 = has addition or subtraction
    2 = has parenthesis at the start and end of the array
*/
int hasAddSub(vector<string> equation, int start, int end)
{
    int bracket =0, count =0;
    for(int i=0; i<equation.size(); i++){
        if(equation[i] == "("){
            bracket++;
        }else if(equation[i] == ")" ){
            bracket--;
        }else if(bracket == 0){
            if((equation[i] == "+")||(equation[i] == "-")) return 1;
            if((equation[i] == "*")||(equation[i] == "/")) count++;
        }
    }

    if(count != 0){
        return 0;
    }
    return 2;
}

int isOp(string val)
{
    if((val == "+")||(val == "-")) return 1;
    if((val == "*") || (val == "/")) return 2;
    return 0;
}

void recPostfix(string& posfix, const vector<string>& equation, int start, int end)
{
    //base case:
    if(start == end){
        posfix = equation[start] + posfix;
        return;
    }

    int bracket = 0, index = 0;
    int addSub = hasAddSub(equation, start, end);

    //if there are parenthesis around the whole equation
    if(addSub == 2){
        start++;
        end--;
        addSub = hasAddSub(equation, start, end);
    }

    //finds a middle operator
    for(int i=end; i>=start; i--){
        if(equation[i] == "("){
            bracket++;
        }else if(equation[i] == ")" ){
            bracket--;
        } else if( bracket == 0 && isOp(equation[i])!=0){
            if(addSub == 1){
                if(isOp(equation[i]) == 1){
                    index = i;
                    break;
                }
            }else{ //theres no addition/subtraction
                index = i;
                break;
            }
        }
    }

    posfix = equation[index] + posfix;
    //recurse towards the end of the array:
    recPostfix(posfix, equation, index+1, end);
    //recurse towards the front of the array:
    recPostfix(posfix, equation, start, index-1);
}

string getPostfix(string line)
{
    //do not have to use genericLinkedList Stack
    vector<string> equation = convert2Vec(line);
    string posfix = "";
    recPostfix(posfix, equation, 0, equation.size()-1);
    return posfix;
}

int main(int argc, char** argv)
{
    //vector<string> equation = convert2Vec(argv[1]);

    /*int bracket = 0, index = 0, start = 0, end = equation.size()-1;
    int addSub = hasAddSub(equation, start, end);

    //if there are parenthesis around the whole equation
    if(addSub == 2){
        start++;
        end--;
        addSub = hasAddSub(equation, start, end);
    }

    //finds a middle operator
    for(int i=end; i>=start; i--){
        if(equation[i] == "("){
            bracket++;
        }else if(equation[i] == ")" ){
            bracket--;
        } else if( bracket == 0 && isOp(equation[i])!=0){
            if(addSub == 1){
                if(isOp(equation[i]) == 1){
                    index = i;
                    break;
                }
            }else{ //theres no addition/subtraction
                index = i;
                break;
            }
        }
    }*/
    cout << getPostfix(argv[1]) << endl;

    return 0;
}

#include #include using namespace std; int main (int argc, char** argv) { int mins = 0, hr; char hours[2]; int len = strlen(argv[1]); for(int i =0; i=5 && hr <12){ cout<< "Good morning"<< endl; } if(hr >= 12 && hr <= 19){ cout << "Good afternoon"<< endl; } if(hr >= 19 || hr < 5){ cout << "Good night" << endl; } return 0; }

CMPT 255 course outline

At the end of CMPT 225 course, a student will be able to:
1. Software Development:
   • convert specifications into high-level design, apply software engineering and design concepts, and express OO design in UML class diagrams
   • write C++ code
   • encapsulate methods and variables for an ADT into a C++ class
   • develop, compile and test their programs using the standard unix/linux tool set (e.g., make/g++)
   • differentiate between memory declared globally, on the stack, and on the heap
   • implement functions/algorithms that pass pointers as parameters, perform pointer arithmetic and manipulate pointers
   • manage memory in C++, allocate and free arrays and individual elements in heap
   • design and use test cases
2. Abstract Data Types (ADTs):
   • define "abstract data type" and "data structure" and differentiate between the two
   • define the following ADTs in terms of their data and their operations (their public interface): stack, queue, priority queue
   • give examples of real-life applications of the above ADTs
   • define the following data structures, and demonstrate, simulate, and trace operations on them:
     • static array
     • dynamic array
     • circular array
     • linked list (singly/doubly headed, singly/doubly linked, etc...)
     • binary heap
     • [balanced] binary search tree (for example: AVL and B-trees)
     • [chained / open addressed] hash table
     • discuss tradeoffs in designing hash functions and describe collisions
   • given a set of requirements, select the most appropriate data collection ADT class, taking into account its time and space efficiency
   • implement and analyze basic sorting algorithms: insertion sort, selection sort, merge sort, quick sort, heap sort, tree sort, ...
3. Recursion:
   • describe tradeoffs between recursive and iterative solutions to problems
   • write recursive solutions to non-trivial problems, such as binary search tree traversals and recursive sorts
   • write recursive definitions of binary heap and BST
4. Complexity Analysis:
   • analyze the best, worst, and average case running time of various ADT operations implemented by various data structures
   • analyze the best, worst, and average case running time of basic sorting algorithms above
   • describe alternatives for measuring the performance of an algorithm implementation such as empirical measurement of running time, by counting the elementary operations and/or O notation
5. External Storage:
   • perform operations on data that are too large to fit in memory, e.g.:external mergesort, index files and data files

stack.cpp

#include"stack.h"

Stack::Stack()
{
  LinkedList* list = new LinkedList();
}

Stack::~Stack()
{
  removeAll();
}

int Stack::empty()
{
  return list->empty();
}

void Stack::push(int num)
{
  list->prepend(num);
}

int Stack::pop()
{
  return list->removeHead();
}

stack.h

#include"LinkedList.h"

class Stack{
private:
  LinkedList* list;
public:
  Stack();
  ~Stack();
  int empty();
  void push(int num);
  int pop();
};

lel

int LLcycle(list_t* list)
{
  element_t* el1 = list->head;
  element_t* el2 = list->head->next;
  while(1){
    // NULL is detected - no cycle
    if(el1->next == NULL || el2->next == NULL){
      return 0;
    }
    if(el1 == el2){ //el2 is the same address as el1
      return 1;
    }
    el1 = el1->next;
    el2 = el2->next->next;
  }
}

cycle

void cycle(LL_t* list, int n, int m)
{
  element_t* elN = list->head;
  element_t* elM = list->head;
  unsigned int i= 0;
  unsigned int j =0;

  while(i < n){ //iterates through the list for n
    if(i == n-1){ // this is the index of the nth node that you want
      while(j < m){
        if(j == m-1){ // finds the mth node
          elN->next = elM; //the next pointer of the nth node is the address of m
        }
        j++;
        elM = elM->next;
      }
    }
    i++;
    elN = elN->next;
  }
}

reverse

void LLreverse(LL_t* list)
{
  //creates a new head
  LL_t* l = malloc (sizeof(LL_t));
  if(l){
    l->head = list->head;
  }
  if(l && list->head){
    list->head = list->head->next; //moves the list head to the next element
    l->head->next = NULL; //this is the last element of the new list

    //reverses the list
    node_t* el = list->head;
    while(el){
      list->head = list->head->next;
      el->next = l->head;
      l->head = el;
      el = list->head;
    }
    // makes the list->head point to new list
    list->head = l->head;
    //destroys the list
    l->head = NULL;
    free(l);
  }
}

part

#include<stdio.h>
#include"list.h"
#include<stdlib.h>

void LLreverse(list_t* list)
{
  //count the number of elements in list
  int count =0;
  for(element_t*el = list->head; el; el = el->next){
    count++;
  }
//  printf("%d",count );

}

int main(){
  list_t* list =list_create();
  for(int i =0; i<5; i++){
    list_append(list,i);
  }
  LLreverse(list);
  list_destroy(list);
  return 0;
}

partition

void swap(int a[], int i, int j) //swaps values using their indices
{
  int x = a[i];
  a[i] = a[j];
  a[j] = x;
}

int partition(int list[], int len)
{
  int pivot = list[0];
  int pi = 0; //pivot starting index
  int i = 0; int j = len-1;
  while(i!=j){
    if(pi == i){
      if(list[j] < pivot){
        swap(list,i,j);
        pi = j;
        i++;
      } else { //when the j->val is greater than pivot
        j--;
      }
    }else{//when the pivot index is at the j value instead
      if(list[i] > pivot){
        swap(list, i, j);
        pi = i;
        j--;
      } else {
        i++;
      }
    }
  }
  return pi;
}

int main ()
{
    int arr[8] = {6,1,7,5,8,9,3,2};
    int len = 8;
    int first = arr[0];
    int count = 0;
    partition(arr, len);

    for(int i=0; i<len; i++){
        printf("%d", arr[i]);
    }
    return 0;
}