This assignment is comprised of 3 parts:
All files needed are located at the end of the
directions.
Part 1: Implementation of Dynamic Array, Stack, and
Bag
First, complete the Worksheets 14 (Dynamic Array), 15 (Dynamic
Array Amortized Execution Time Analysis), 16 (Dynamic Array Stack),
and 21 (Dynamic Array Bag). These worksheets will get you started
on the implementations, but you will NOT turn them in. Do
Not Worry about these, they are completed.
Next, complete the dynamic array and the dynamic array-based
implementation of a stack and a bag in dynamicArray.c. The comments
for each function will help you understand what each function
should do.
We have provided the header file for this assignment, DO NOT change
the provided header file (dynArray.h).
You can test your implementation by using the code in
testDynArray.c. This file contains several test cases for the
functions in dynamicArray.c. Try to get all the test cases to pass.
You should also write more test cases on your own, but do not
submit testDynArray.c.
Part 2: Amortized Analysis of the Dynamic Array
(written)
Consider the push() operation for a Dynamic Array Stack. In the
best case, the operation is O(1). This corresponds to the case
where there was room in the space we have already allocated for the
array. However, in the worst case, this operation slows down to
O(n). This corresponds to the case where the allocated space was
full and we must copy each element of the array into a new (larger)
array. This problem is designed to discover runtime bounds on the
average case when various array expansion strategies are used, but
first some information on how to perform an amortized analysis is
necessary.
1. Each time an item is added to the array without requiring
reallocation, count 1 unit of cost. This cost will cover the
assignment which actually puts the item in the array.
2. Each time an item is added and requires reallocation, count X +
1 units of cost, where X is the number of items currently in the
array. This cost will cover the X assignments which are necessary
to copy the contents of the full array into a new (larger) array,
and the additional assignment to put the item which did not fit
originally.
To make this more concrete, if the array has 8 spaces and is
holding 5 items, adding the sixth will cost 1. However, if the
array has 8 spaces and is holding 8 items, adding the ninth will
cost 9 (8 to move the existing items + 1 to assign the ninth item
once space is available).
When we can bound an average cost of an operation in this
fashion, but not bound the worst case execution time, we call it
amortized constant execution time, or average execution time.
Amortized constant execution time is often written as O(1)+, the
plus sign indicating it is not a guaranteed execution time
bound.
In a file called amortizedAnalysis.txt, please provide answers to
the following questions:
1. How many cost units are spent in the entire process of
performing 32 consecutive push operations on an empty array which
starts out at capacity 8, assuming that the array will double in
capacity each time a new item is added to an already full dynamic
array? As N (ie. the number of pushes) grows large, under this
strategy for resizing, what is the big-oh complexity for a
push?
2. How many cost units are spent in the entire process of
performing 32 consecutive push operations on an empty array which
starts out at capacity 8, assuming that the array will grow by a
constant 2 spaces each time a new item is added to an already full
dynamic array? As N (ie. the number of pushes) grows large, under
this strategy for resizing, what is the big-oh complexity for a
push?
Part 3: Application of the Stack -
Note - For this exercise you need to first make the following
change in dynArray.h: Change #define TYPE int to #define TYPE
char
As discussed in the lecture notes, stacks are a very commonly used abstract data type. Applications of stacks include implementation of reverse Polish notation expression evaluation and undo buffers. Stacks can also be used to check whether an expression has balanced paretheses, braces, and brackets (,{,[ or not. For example, expressions with balanced parentheses are (x + y), (x + (y + z)) and with unbalanced are (x+y, (x + (y+ z).
For this part of the assignment, you are to write a function that solves this problem using a stack (no counter integers or string functions are allowed). If you use a counter or string operation of any kind, you will not receive credit for completing this part of the assignment.
The file stackapp.c contains two functions -
char nextChar(char* s) – returns the next character or ‘\0’ if at the end of the string. int isBalanced(char* s) – returns 1 if the string is balanced and 0 if it is not balanced.
You have to implement int isBalanced(char* s) – which should read through the string using ‘nextChar’ and use a stack to do the test. It should return either 1(True) or 0(False).
dynArray.h
/* dynamicArray_a1.h : Dynamic Array implementation. */
#ifndef DYNAMIC_ARRAY_INCLUDED
#define DYNAMIC_ARRAY_INCLUDED 1
#ifndef __TYPE
#define __TYPE
# define TYPE char
# define TYPE_SIZE sizeof(int)
# endif
# ifndef LT
# define LT(A, B) ((A) < (B))
# endif
# ifndef EQ
# define EQ(A, B) ((A) == (B))
# endif
typedef struct DynArr DynArr;
/* Dynamic Array Functions */
void initDynArr(DynArr *v, int capacity);
DynArr *newDynArr(int cap);
void freeDynArr(DynArr *v);
void deleteDynArr(DynArr *v);
int sizeDynArr(DynArr *v);
void addDynArr(DynArr *v, TYPE val);
TYPE getDynArr(DynArr *v, int pos);
void putDynArr(DynArr *v, int pos, TYPE val);
void swapDynArr(DynArr *v, int i, int j);
void removeAtDynArr(DynArr *v, int idx);
/* Stack interface. */
int isEmptyDynArr(DynArr *v);
void pushDynArr(DynArr *v, TYPE val);
TYPE topDynArr(DynArr *v);
void popDynArr(DynArr *v);
/* Bag Interface */
/* Note addDynArr is already declared above*/
int containsDynArr(DynArr *v, TYPE val);
void removeDynArr(DynArr *v, TYPE val);
#endif
dynamicArray.c
/* dynamicArray.c: Dynamic Array implementation. */
#include <assert.h>
#include <stdlib.h>
#include "dynArray.h"
struct DynArr
{
TYPE *data; /* pointer to the data array */
int size; /* Number of elements in the array */
int capacity; /* capacity ofthe array */
};
/*
************************************************************************
Dynamic Array Functions
************************************************************************
*/
/* Initialize (including allocation of data array) dynamic array.
param: v pointer to the dynamic array
param: cap capacity of the dynamic array
pre: v is not null
post: internal data array can hold cap elements
post: v->data is not null
*/
void initDynArr(DynArr *v, int capacity)
{
assert(capacity > 0);
assert(v!= 0);
v->data = (TYPE *) malloc(sizeof(TYPE) * capacity);
assert(v->data != 0);
v->size = 0;
v->capacity = capacity;
}
/* Allocate and initialize dynamic array.
param: cap desired capacity for the dyn array
pre: none
post: none
ret: a non-null pointer to a dynArr of cap capacity
and 0 elements in it.
*/
DynArr* newDynArr(int cap)
{
assert(cap > 0);
DynArr *r = (DynArr *)malloc(sizeof( DynArr));
assert(r != 0);
initDynArr(r,cap);
return r;
}
/* Deallocate data array in dynamic array.
param: v pointer to the dynamic array
pre: none
post: d.data points to null
post: size and capacity are 0
post: the memory used by v->data is freed
*/
void freeDynArr(DynArr *v)
{
if(v->data != 0)
{
free(v->data); /* free the space on the heap
*/
v->data = 0; /* make it point to null
*/
}
v->size = 0;
v->capacity = 0;
}
/* Deallocate data array and the dynamic array ure.
param: v pointer to the dynamic array
pre: none
post: the memory used by v->data is freed
post: the memory used by d is freed
*/
void deleteDynArr(DynArr *v)
{
freeDynArr(v);
free(v);
}
/* Resizes the underlying array to be the size cap
param: v pointer to the dynamic array
param: cap the new desired capacity
pre: v is not null
post: v has capacity newCap
*/
void _dynArrSetCapacity(DynArr *v, int newCap)
{
/* FIXME: You will write this function */
}
/* Get the size of the dynamic array
param: v pointer to the dynamic array
pre: v is not null
post: none
ret: the size of the dynamic array
*/
int sizeDynArr(DynArr *v)
{
return v->size;
}
/* Adds an element to the end of the dynamic array
param: v pointer to the dynamic array
param: val the value to add to the end of the dynamic
array
pre: the dynArry is not null
post: size increases by 1
post: if reached capacity, capacity is doubled
post: val is in the last utilized position in the array
*/
void addDynArr(DynArr *v, TYPE val)
{
/* FIXME: You will write this function */
}
/* Get an element from the dynamic array from a specified
position
param: v pointer to the dynamic array
param: pos integer index to get the element from
pre: v is not null
pre: v is not empty
pre: pos < size of the dyn array and >= 0
post: no changes to the dyn Array
ret: value stored at index pos
*/
TYPE getDynArr(DynArr *v, int pos)
{
/* FIXME: You will write this function */
/* FIXME: you must change this return value
*/
return 1;
}
/* Put an item into the dynamic array at the specified
location,
overwriting the element that was there
param: v pointer to the dynamic array
param: pos the index to put the value into
param: val the value to insert
pre: v is not null
pre: v is not empty
pre: pos >= 0 and pos < size of the array
post: index pos contains new value, val
*/
void putDynArr(DynArr *v, int pos, TYPE val)
{
/* FIXME: You will write this function */
}
/* Swap two specified elements in the dynamic array
param: v pointer to the dynamic array
param: i,j the elements to be swapped
pre: v is not null
pre: v is not empty
pre: i, j >= 0 and i,j < size of the dynamic array
post: index i now holds the value at j and index j now holds the
value at i
*/
void swapDynArr(DynArr *v, int i, int j)
{
/* FIXME: You will write this function */
}
/* Remove the element at the specified location from the
array,
shifts other elements back one to fill the gap
param: v pointer to the dynamic array
param: idx location of element to remove
pre: v is not null
pre: v is not empty
pre: idx < size and idx >= 0
post: the element at idx is removed
post: the elements past idx are moved back one
*/
void removeAtDynArr(DynArr *v, int idx)
{
/* FIXME: You will write this function */
}
/*
************************************************************************
Stack Interface Functions
************************************************************************
*/
/* Returns boolean (encoded in an int) demonstrating whether or
not the
dynamic array stack has an item on it.
param: v pointer to the dynamic array
pre: the dynArr is not null
post: none
ret: 1 if empty, otherwise 0
*/
int isEmptyDynArr(DynArr *v)
{
/* FIXME: You will write this function */
/* FIXME: You will change this return value*/
return 1;
}
/* Push an element onto the top of the stack
param: v pointer to the dynamic array
param: val the value to push onto the stack
pre: v is not null
post: size increases by 1
if reached capacity, capacity is doubled
val is on the top of the stack
*/
void pushDynArr(DynArr *v, TYPE val)
{
/* FIXME: You will write this function */
}
/* Returns the element at the top of the stack
param: v pointer to the dynamic array
pre: v is not null
pre: v is not empty
post: no changes to the stack
*/
TYPE topDynArr(DynArr *v)
{
/* FIXME: You will write this function */
/* FIXME: You will change this return value*/
return 1;
}
/* Removes the element on top of the stack
param: v pointer to the dynamic array
pre: v is not null
pre: v is not empty
post: size is decremented by 1
the top has been removed
*/
void popDynArr(DynArr *v)
{
/* FIXME: You will write this function */
}
/*
************************************************************************
Bag Interface Functions
************************************************************************
*/
/* Returns boolean (encoded as an int) demonstrating whether or
not
the specified value is in the collection
true = 1
false = 0
param: v pointer to the dynamic array
param: val the value to look for in the bag
pre: v is not null
pre: v is not empty
post: no changes to the bag
*/
int containsDynArr(DynArr *v, TYPE val)
{
/* FIXME: You will write this function */
/* FIXME: You will change this return value */
return 1;
}
/* Removes the first occurrence of the specified value from the
collection
if it occurs
param: v pointer to the dynamic array
param: val the value to remove from the array
pre: v is not null
pre: v is not empty
post: val has been removed
post: size of the bag is reduced by 1
*/
void removeDynArr(DynArr *v, TYPE val)
{
/* FIXME: You will write this function */
}
testDynArray.c
/* testDynArray.c
* This file is used for testing the dynamicArray.c file.
* This test suite is by no means complete or thorough.
* More testing is needed on your own.
*/
#include <stdio.h>
#include <stdlib.h>
#include "dynArray.h"
void assertTrue(int predicate, char *message)
{
printf("%s: ", message);
if (predicate)
printf("PASSED\n");
else
printf("FAILED\n");
}
// this main function contains some
int main(int argc, char* argv[]){
DynArr *dyn;
dyn = newDynArr(2);
int i;
printf("\n\nTesting addDynArr...\n");
addDynArr(dyn, 3);
addDynArr(dyn, 4);
addDynArr(dyn, 10);
addDynArr(dyn, 5);
addDynArr(dyn, 6);
printf("The array's content: [3,4,10,5,6]\n");
assertTrue(EQ(getDynArr(dyn, 0), 3), "Test 1st element ==
3");
assertTrue(EQ(getDynArr(dyn, 1), 4), "Test 2nd element ==
4");
assertTrue(EQ(getDynArr(dyn, 2), 10), "Test 3rd element ==
10");
assertTrue(EQ(getDynArr(dyn, 3), 5), "Test 4th element ==
5");
assertTrue(EQ(getDynArr(dyn, 4), 6), "Test 5th element ==
6");
assertTrue(sizeDynArr(dyn) == 5, "Test size = 5");
printf("\n\nTesting putDynArr...\nCalling putDynArr(dyn, 2,
7)\n");
putDynArr(dyn, 2, 7);
printf("The array's content: [3,4,7,5,6]\n");
assertTrue(EQ(getDynArr(dyn, 2), 7), "Test 3rd element ==
7");
assertTrue(sizeDynArr(dyn) == 5, "Test size = 5");
printf("\n\nTesting swapDynArr...\nCalling swapDynArr(dyn, 2,
4)\n");
swapDynArr(dyn, 2, 4);
printf("The array's content: [3,4,6,5,7]\n");
assertTrue(EQ(getDynArr(dyn, 2), 6), "Test 3rd element ==
6");
assertTrue(EQ(getDynArr(dyn, 4), 7), "Test 5th element ==
7");
printf("\n\nTesting removeAtDynArr...\nCalling removeAtDynArr(dyn,
1)\n");
removeAtDynArr(dyn, 1);
printf("The array's content: [3,6,5,7]\n");
assertTrue(EQ(getDynArr(dyn, 0), 3), "Test 1st element ==
3");
assertTrue(EQ(getDynArr(dyn, 3), 7), "Test 4th element ==
7");
assertTrue(sizeDynArr(dyn) == 4, "Test size = 4");
printf("\n\nTesting stack interface...\n");
printf("The stack's content: [3,6,5,7] <- top\n");
assertTrue(!isEmptyDynArr(dyn), "Testing isEmptyDynArr");
assertTrue(EQ(topDynArr(dyn), 7), "Test topDynArr == 7");
popDynArr(dyn);
printf("Poping...\nThe stack's content: [3,6,5] <-
top\n");
assertTrue(EQ(topDynArr(dyn), 5), "Test topDynArr == 5");
pushDynArr(dyn, 9);
printf("Pushing 9...\nThe stack's content: [3,6,5,9] <-
top\n");
assertTrue(EQ(topDynArr(dyn), 9), "Test topDynArr == 9");
printf("\n\nTesting bag interface...\n");
printf("The bag's content: [3,6,5,9]\n");
assertTrue(containsDynArr(dyn, 3), "Test containing 3");
assertTrue(containsDynArr(dyn, 6), "Test containing 6");
assertTrue(containsDynArr(dyn, 5), "Test containing 5");
assertTrue(containsDynArr(dyn, 9), "Test containing 9");
assertTrue(!containsDynArr(dyn, 7), "Test not containing 7");
removeDynArr(dyn, 3);
printf("Removing 3...\nThe stack's content: [6,5,9]\n");
assertTrue(!containsDynArr(dyn, 3), "Test not containing 3");
return 0;
}
stackapp.c
/* stack.c: Stack application. */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "dynArray.h"
/*
***************************************************************
Using stack to check for unbalanced parentheses.
*****************************************************************
*/
/* Returns the next character of the string, once reaches end
return '0' (zero)
param: s pointer to a string
pre: s is not null
*/
char nextChar(char* s)
{
static int i = -1;
char c;
++i;
c = *(s+i);
if ( c == '\0' )
return '\0';
else
return c;
}
/* Checks whether the (), {}, and [] are balanced or not
param: s pointer to a string
pre: s is not null
post:
*/
int isBalanced(char* s)
{
/* FIXME: You will write this function
*/
return 0;
}
int main(int argc, char* argv[]){
char* s=argv[1];
int res;
printf("Assignment 2\n");
res = isBalanced(s);
if (res)
printf("The string %s is balanced\n",s);
else
printf("The string %s is not balanced\n",s);
return 0;
}
calc.c
---------------------------------------
/******************************************************************************************************
Description: This program is a RPN calculator that takes input from
the command line
Input: User inputs numbers and operators to be calculated.
Output: Outputs the value of the calculated numbers based on the
operators used.
******************************************************************************************************/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <math.h>
#include "dynamicArray.h"
/* param: s the string
param: num a pointer to double
returns: true (1) if s is a number else 0 or
false.
postcondition: if it is a number, num will hold
the value of the number
*/
int isNumber(char *s, double *num)
{
char *end;
double returnNum;
if(strcmp(s, "0") == 0)
{
*num = 0;
return 1;
}
else
{
returnNum = strtod(s,
&end);
/* If there's anythin in end, it's
bad */
if((returnNum != 0.0) &&
(strcmp(end, "") == 0))
{
*num =
returnNum;
return 1;
}
}
return 0; //if got here, it was not a number
}
/* param: stack the stack being manipulated
pre: the stack contains at least two elements
post: the top two elements are popped and
their sum is pushed back onto the stack.
*/
void add (struct DynArr *stack)
{
double result = 0;// the final number after
calculation
double firstNum = 0;//first number user input
before + sign
double secondNum = 0;//second number user input
before + sign.
assert(stack != 0);
assert(sizeDynArr(stack) >= 2);
secondNum = topDynArr(stack);
popDynArr(stack);
firstNum = topDynArr(stack);
popDynArr(stack);
result = firstNum + secondNum;
pushDynArr(stack, result);
printf("Adding %.3f + %.3f \n", firstNum,
secondNum);
}
/* param: stack the stack being manipulated
pre: the stack contains at least two elements
post: the top two elements are popped and
their difference is pushed back onto the stack.
*/
void subtract(struct DynArr *stack)
{
double result = 0;// the final number after
calculation
double firstNum = 0;//first number user input
before - sign
double secondNum = 0;//second number user input
before - sign.
assert(stack != 0);
assert(sizeDynArr(stack) >= 2);
secondNum = topDynArr(stack);
popDynArr(stack);
firstNum = topDynArr(stack);
popDynArr(stack);
result = firstNum - secondNum;
pushDynArr(stack, result);
printf("Subtracting %.3f - %.3f \n", firstNum,
secondNum);
}
/* param: stack the stack being manipulated
pre: the stack contains at least two elements
post: the top two elements are popped and
their quotient is pushed back onto the stack.
*/
void divide(struct DynArr *stack)
{
double result = 0;// the final number after
calculation
double firstNum = 0;//first number user input
before / sign
double secondNum = 0;//second number user input
before / sign.
assert(stack != 0);
assert(sizeDynArr(stack) >= 2);
secondNum = topDynArr(stack);
popDynArr(stack);
firstNum = topDynArr(stack);
popDynArr(stack);
result = firstNum / secondNum;
pushDynArr(stack, result);
printf("Dividing %.3f / %.3f \n", firstNum,
secondNum);
}
/* param: stack the stack being manipulated
pre: the stack contains at least two elements
post: the top two elements are popped and
their product is pushed back onto the stack.
*/
void multiply(struct DynArr *stack)
{
double result = 0;// the final number after
calculation
double firstNum = 0;//first number user input
before x sign
double secondNum = 0;//second number user input
before x sign.
assert(stack != 0);
assert(sizeDynArr(stack) >= 2);
secondNum = topDynArr(stack);
popDynArr(stack);
firstNum = topDynArr(stack);
popDynArr(stack);
result = firstNum * secondNum;
pushDynArr(stack, result);
printf("Multiplying %.3f x %.3f \n", firstNum,
secondNum);
}
/* param: stack the stack being manipulated
pre: the stack contains at least two elements
post: the top two elements are popped and
their power is pushed back onto the stack.
*/
void power(struct DynArr *stack)
{
double result = 0;// the final number after
calculation
double firstNum = 0;//first number user input
before ^ sign
double secondNum = 0;//second number user input
before ^ sign.
assert(stack != 0);
assert(sizeDynArr(stack) >= 2);
secondNum = topDynArr(stack);
popDynArr(stack);
firstNum = topDynArr(stack);
popDynArr(stack);
result = pow(firstNum, secondNum);
pushDynArr(stack, result);
printf("Powering %.3f ^ %.3f \n", firstNum,
secondNum);
}
/* param: stack the stack being manipulated
pre: the stack contains at least one element
post: the top element is popped and
the square is pushed back onto the stack.
*/
void square(struct DynArr *stack)
{
double result = 0;// the final number after
calculation
double firstNum = 0;//first number user input
before ^2 sign
assert(stack != 0);
assert(sizeDynArr(stack) >= 1);
firstNum = topDynArr(stack);
popDynArr(stack);
result = pow(firstNum, 2);
pushDynArr(stack, result);
printf("Squaring %.3f ^2 \n", firstNum);
}
/* param: stack the stack being manipulated
pre: the stack contains at least one element
post: the top element is popped and
the cube is pushed back onto the stack.
*/
void cube(struct DynArr *stack)
{
double result = 0;// the final number after
calculation
double firstNum = 0;//first number user input
before ^3 sign
assert(stack != 0);
assert(sizeDynArr(stack) >= 1);
firstNum = topDynArr(stack);
popDynArr(stack);
result = pow(firstNum, 3);
pushDynArr(stack, result);
printf("Cubinging %.3f ^3 \n", firstNum);
}
/* param: stack the stack being manipulated
pre: the stack contains at least one element
post: the top element is popped and
the absolute value is pushed back onto the stack.
*/
void absolute(struct DynArr *stack)
{
double result = 0;// the final number after
calculation
double firstNum = 0;//first number user input
before abs sign
assert(stack != 0);
assert(sizeDynArr(stack) >= 1);
firstNum = topDynArr(stack);
popDynArr(stack);
result = abs(firstNum);
pushDynArr(stack, result);
printf("Absolute value %.3f abs \n",
firstNum);
}
/* param: stack the stack being manipulated
pre: the stack contains at least one element
post: the top element is popped and
the square root is pushed back onto the stack.
*/
void square_root(struct DynArr *stack)
{
double result = 0;// the final number after
calculation
double firstNum = 0;//first number user input
before sqrt sign
assert(stack != 0);
assert(sizeDynArr(stack) >= 1);
firstNum = topDynArr(stack);
popDynArr(stack);
result = sqrt(firstNum);
pushDynArr(stack, result);
printf("Square root %.3f sqrt \n",
firstNum);
}
/* param: stack the stack being manipulated
pre: the stack contains at least one element
post: the top element is popped and
the exponential is pushed back onto the stack.
*/
void exponential(struct DynArr *stack)
{
double result = 0;// the final number after
calculation
double firstNum = 0;//first number user input
before exp sign
assert(stack != 0);
assert(sizeDynArr(stack) >= 1);
firstNum = topDynArr(stack);
popDynArr(stack);
result = exp(firstNum);
pushDynArr(stack, result);
printf("Exponential %.3f exp \n",
firstNum);
}
/* param: stack the stack being manipulated
pre: the stack contains at least one element
post: the top element is popped and
the natural log is pushed back onto the stack.
*/
void natural_log(struct DynArr *stack)
{
double result = 0;// the final number after
calculation
double firstNum = 0;//first number user input
before ln sign
assert(stack != 0);
assert(sizeDynArr(stack) >= 1);
firstNum = topDynArr(stack);
popDynArr(stack);
result = log(firstNum);
pushDynArr(stack, result);
printf("Natural log %.3f ln \n",
firstNum);
}
/* param: stack the stack being manipulated
pre: the stack contains at least one element
post: the top element is popped and
the log is pushed back onto the stack.
*/
void base10log(struct DynArr *stack)
{
double result = 0;// the final number after
calculation
double firstNum = 0;//first number user input
before log sign
assert(stack != 0);
assert(sizeDynArr(stack) >= 1);
firstNum = topDynArr(stack);
popDynArr(stack);
result = log10(firstNum);
pushDynArr(stack, result);
printf("Log %.3f log \n", firstNum);
}
/* param: Check number of numbers
pre: the stack contains at least x(low) number of elements
pre: the stack contains at no greater than x(high) number of
elements
post: Return 0 if error, 1 if no error.
*/
int isValid(struct DynArr *stack, char *s, int high, int low)
{
int i;
int n = sizeDynArr(stack);
if (sizeDynArr(stack) >= high)
{
printf("Too many numbers ");
for (i = 0; i < n; i++)
{
printf("%.1f ",
topDynArr(stack));
popDynArr(stack);
}
printf("%s\n ", s);
return 0;
}
else if (sizeDynArr(stack) < low)
{
printf("Too few numbers ");
for (i = 0; i < n; i++)
{
printf("%.1f ",
topDynArr(stack));
popDynArr(stack);
}
printf("%s\n ", s);
return 0;
}
return 1;
}
/* param: numInputToken argc
param: inputString argv
postcondition: result of calculation
*/
double calculate(int numInputTokens, char **inputString)
{
int i;
int e;//Error, terminate
double k = 0;//Number user input.
double result = 0.0;
char *s;
struct DynArr *stack;
//set up the stack
stack = createDynArr(20);
// start at 1 to skip the name of the calculator
calc
for(i=1;i < numInputTokens;i++)
{
s = inputString[i];
// Hint: General
algorithm:
// (1) Check if the string s is in
the list of operators.
// (1a) If it is,
perform corresponding operations.
// (1b) Otherwise,
check if s is a number.
// (1b - I)
If s is not a number, produce an error.
// (1b -
II) If s is a number, push it onto the stack
if (strcmp(s, "+") == 0)
{
e =
isValid(stack, s, 3, 2);
if (e ==
0)
{
return e;
}
add(stack);
}
else if (strcmp(s, "-") == 0)
{
e =
isValid(stack, s, 3, 2);
if (e ==
0)
{
return e;
}
subtract(stack);
}
else if (strcmp(s, "/") == 0)
{
e =
isValid(stack, s, 3, 2);
if (e ==
0)
{
return e;
}
divide(stack);
}
else if (strcmp(s, "x") == 0)
{
e =
isValid(stack, s, 3, 2);
if (e ==
0)
{
return e;
}
multiply(stack);
}
else if (strcmp(s, "^") == 0)
{
e =
isValid(stack, s, 3, 2);
if (e ==
0)
{
return e;
}
power(stack);
}
else if (strcmp(s, "^2") ==
0)
{
e =
isValid(stack, s, 2, 0);
if (e ==
0)
{
return e;
}
square(stack);
}
else if (strcmp(s, "^3") ==
0)
{
e =
isValid(stack, s, 2, 0);
if (e ==
0)
{
return e;
}
cube(stack);
}
else if (strcmp(s, "abs") ==
0)
{
e =
isValid(stack, s, 2, 0);
if (e ==
0)
{
return e;
}
absolute(stack);
}
else if (strcmp(s, "sqrt") ==
0)
{
e =
isValid(stack, s, 2, 0);
if (e ==
0)
{
return e;
}
square_root(stack);
}
else if (strcmp(s, "exp") ==
0)
{
e =
isValid(stack, s, 2, 0);
if (e ==
0)
{
return e;
}
exponential(stack);
}
else if (strcmp(s, "ln") ==
0)
{
e =
isValid(stack, s, 2, 0);
if (e ==
0)
{
return e;
}
natural_log(stack);
}
else if (strcmp(s, "log") ==
0)
{
e =
isValid(stack, s, 2, 0);
if (e ==
0)
{
return e;
}
base10log(stack);
}
else if (strcmp(s, "pi") == 0)// if
user input pi, push value.
pushDynArr(stack, 3.14159265);
else if (strcmp(s, "e") == 0)// if
user input e, push value.
pushDynArr(stack, 2.7182818);
else
{
if
(isNumber(s, &k))
{
pushDynArr(stack, k);
}
else
{
printf("Unknown Operator %s\n", s);
return 0;
}
}
} //end for
result = topDynArr(stack);
popDynArr(stack);
printf("RESULT = %.3f\n\n", result);
return result;
}
int main(int argc , char** argv)
{
// assume each argument is contained in the argv
array
// argc-1 determines the number of operands +
operators
if (argc == 1)
return 0;
calculate(argc,argv);
return 0;
}
--------------------------------------------------------------------------------------------------
dynamicArray.c
-----------------------------
/******************************************************************************************************
Description: This file contains functions involved with dynamic
arrays, dynamic array-based stack and bag.
Input: No user input
Output: No output.
******************************************************************************************************/
/* dynamicArray.c: Dynamic Array implementation.
*/
#include <assert.h>
#include <stdlib.h>
#include "dynamicArray.h"
struct DynArr
{
TYPE *data; /* pointer
to the data array */
int size; /* Number of
elements in the array */
int capacity; /* capacity ofthe array
*/
};
/*
************************************************************************
Dynamic Array Functions
************************************************************************
*/
/* Initialize (including allocation of data array) dynamic
array.
param: v
pointer to the dynamic array
param: cap capacity of the
dynamic array
pre: v is not null
post: internal data array can hold cap
elements
post: v->data is not null
*/
void initDynArr(DynArr *v, int capacity)
{
assert(capacity > 0);
assert(v!= 0);
v->data = (TYPE *) malloc(sizeof(TYPE) *
capacity);
assert(v->data != 0);
v->size = 0;
v->capacity = capacity;
}
/* Allocate and initialize dynamic array.
param: cap desired capacity
for the dyn array
pre: none
post: none
ret: a non-null pointer to a dynArr of cap
capacity
and 0 elements
in it.
*/
DynArr* createDynArr(int cap)
{
assert(cap > 0);
DynArr *r = (DynArr *)malloc(sizeof( DynArr));
assert(r != 0);
initDynArr(r,cap);
return r;
}
/* Deallocate data array in dynamic array.
param: v
pointer to the dynamic array
pre: none
post: d.data points to null
post: size and capacity are 0
post: the memory used by v->data is
freed
*/
void freeDynArr(DynArr *v)
{
if(v->data != 0)
{
free(v->data); /*
free the space on the heap */
v->data = 0;
/* make it point to null */
}
v->size = 0;
v->capacity = 0;
}
/* Deallocate data array and the dynamic array ure.
param: v
pointer to the dynamic array
pre: none
post: the memory used by v->data is
freed
post: the memory used by d is freed
*/
void deleteDynArr(DynArr *v)
{
freeDynArr(v);
free(v);
}
/* Resizes the underlying array to be the size cap
param: v
pointer to the dynamic array
param: cap
the new desired capacity
pre: v is not null
post: v has capacity newCap
*/
void _dynArrSetCapacity(DynArr *v, int newCap)
{
int i;
TYPE *newData =
(TYPE*)malloc(sizeof(TYPE)*newCap);
assert(newData != 0);
for (i = 0; i < v->size; i++)
{
newData[i] = v->data[i];//copy
data from old array into new array.
}
freeDynArr(v);//free v->data
v->data = newData;
v->capacity = newCap;
v->size = i;
}
/* Get the size of the dynamic array
param: v
pointer to the dynamic array
pre: v is not null
post: none
ret: the size of the dynamic array
*/
int sizeDynArr(DynArr *v)
{
return v->size;
}
/* Adds an element to the end of the dynamic
array
param: v
pointer to the dynamic array
param: val
the value to add to the end of the dynamic array
pre: the dynArry is not null
post: size increases by 1
post: if reached capacity, capacity is
doubled
post: val is in the last utilized position
in the array
*/
void addDynArr(DynArr *v, TYPE val)
{
assert(v != 0);
if (v->size == v->capacity)
{
_dynArrSetCapacity(v, 2 *
v->capacity);
}
v->data[v->size] = val;
v->size++;
}
/* Get an element from the dynamic array from a
specified position
param: v
pointer to the dynamic array
param: pos
integer index to get the element from
pre: v is not null
pre: v is not empty
pre: pos < size of the dyn array and
>= 0
post: no changes to the dyn Array
ret: value stored at index pos
*/
TYPE getDynArr(DynArr *v, int pos)
{
assert(v != 0);
assert(pos < v->size);
assert(pos >= 0);
return v->data[pos];
}
/* Put an item into the dynamic array at the
specified location,
overwriting the element that was there
param: v
pointer to the dynamic array
param: pos
the index to put the value into
param: val
the value to insert
pre: v is not null
pre: v is not empty
pre: pos >= 0 and pos < size of the
array
post: index pos contains new value,
val
*/
void putDynArr(DynArr *v, int pos, TYPE val)
{
assert(v != 0);
assert(pos < v->size);
assert(pos >= 0);
v->data[pos] = val;
}
/* Swap two specified elements in the dynamic
array
param: v
pointer to the dynamic array
param: i,j
the elements to be swapped
pre: v is not null
pre: v is not empty
pre: i, j >= 0 and i,j < size of the
dynamic array
post: index i now holds the value at j and
index j now holds the value at i
*/
void swapDynArr(DynArr *v, int i, int j)
{
TYPE tempValswap;
assert(v != 0);
assert(i < v->size);
assert(j < v->size);
assert(i >= 0);
assert(j >= 0);
tempValswap = v->data[i];
v->data[i] = v->data[j];
v->data[j] = tempValswap;
}
/* Remove the element at the specified location from
the array,
shifts other elements back one to fill the gap
param: v
pointer to the dynamic array
param: idx
location of element to remove
pre: v is not null
pre: v is not empty
pre: idx < size and idx >= 0
post: the element at idx is removed
post: the elements past idx are moved back
one
*/
void removeAtDynArr(DynArr *v, int idx)
{
int i;
assert(v != 0);
assert(idx <= v->size);
assert(idx >= 0);
for (i = 0; i < v->size; i++)
{
v->data[idx+i] =
v->data[idx+i+1];
}
v->size = v->size - 1;
}
/*
************************************************************************
Stack Interface Functions
************************************************************************
*/
/* Returns boolean (encoded in an int) demonstrating
whether or not the
dynamic array stack has an item on it.
param: v
pointer to the dynamic array
pre: the dynArr is not null
post: none
ret: 1 if empty, otherwise 0
*/
int isEmptyDynArr(DynArr *v)
{
assert(v != 0);
if (v->size == 0)
{
return 1; //status is not
empty.
}
return 0;
}
/* Push an element onto the top of the stack
param: v
pointer to the dynamic array
param: val
the value to push onto the stack
pre: v is not null
post: size increases by 1
if reached
capacity, capacity is doubled
val is on the
top of the stack
*/
void pushDynArr(DynArr *v, TYPE val)
{
assert(v != 0);
addDynArr(v, val);
}
/* Returns the element at the top of the stack
param: v
pointer to the dynamic array
pre: v is not null
pre: v is not empty
post: no changes to the stack
*/
TYPE topDynArr(DynArr *v)
{
assert(v != 0);
return v->data[v->size-1];
}
/* Removes the element on top of the stack
param: v
pointer to the dynamic array
pre: v is not null
pre: v is not empty
post: size is decremented by 1
the top has been
removed
*/
void popDynArr(DynArr *v)
{
assert(v != 0);
v->data[v->size-1] = 0;
v->size = v->size - 1;
}
/*
************************************************************************
Bag Interface Functions
************************************************************************
*/
/* Returns boolean (encoded as an int) demonstrating
whether or not
the specified value is in the collection
true = 1
false = 0
param: v
pointer to the dynamic array
param: val
the value to look for in the bag
pre: v is not null
pre: v is not empty
post: no changes to the bag
*/
int containsDynArr(DynArr *v, TYPE val)
{
assert(v != 0);
int i;
for (i = 0; i < v->size; i++)
{
if (EQ(v->data[i],val))
{
return 1;
}
}
return 0;
}
/* Removes the first occurrence of the specified
value from the collection
if it occurs
param: v
pointer to the dynamic array
param: val
the value to remove from the array
pre: v is not null
pre: v is not empty
post: val has been removed
post: size of the bag is reduced by
1
*/
void removeDynArr(DynArr *v, TYPE val)
{
assert(v != 0);
int i;
for (i = 0; i < v->size; i++)
{
if (EQ(val, v->data[i]))
{
removeAtDynArr(v,
i);
return;
}
}
}
-------------------------------------------------------------------------------------------------------------
dynamicArray.h
---------------------------------
/* dynamicArray.h : Dynamic Array implementation.
*/
#include<math.h>
#ifndef DYNAMIC_ARRAY_INCLUDED
#define DYNAMIC_ARRAY_INCLUDED 1
# ifndef TYPE
# define TYPE double
# define TYPE_SIZE sizeof(double)
# endif
# ifndef EQ
# define EQ(A, B) (fabs(A - B) < 10e-7)
# endif
typedef struct DynArr DynArr;
/* Dynamic Array Functions */
DynArr *createDynArr(int cap);
void deleteDynArr(DynArr *v);
int sizeDynArr(DynArr *v);
void addDynArr(DynArr *v, TYPE val);
TYPE getDynArr(DynArr *v, int pos);
void putDynArr(DynArr *v, int pos, TYPE val);
void swapDynArr(DynArr *v, int i, int j);
void removeAtDynArr(DynArr *v, int idx);
/* Stack interface. */
int isEmptyDynArr(DynArr *v);
void pushDynArr(DynArr *v, TYPE val);
TYPE topDynArr(DynArr *v);
void popDynArr(DynArr *v);
/* Bag Interface */
int containsDynArr(DynArr *v, TYPE val);
void removeDynArr(DynArr *v, TYPE val);
#endif
----------------------------------------------------------------------------------------------
testDynArray.c
------------------------------------
/* testDynArray.c
* This file is used for testing the dynamicArray.c file.
* This test suite is by no means complete or thorough.
* More testing is needed on your own.
*/
#include <stdio.h>
#include <stdlib.h>
#include "dynamicArray.h"
void assertTrue(int predicate, char *message)
{
printf("%s: ", message);
if (predicate)
printf("PASSED\n");
else
printf("FAILED\n");
}
// this main function contains some
int main(int argc, char* argv[]){
DynArr *dyn;
dyn = createDynArr(2);
assertTrue(isEmptyDynArr(dyn), "Testing
isEmptyDynArr");
printf("\n\nTesting addDynArr...\n");
addDynArr(dyn, 3);
addDynArr(dyn, 4);
addDynArr(dyn, 10);
addDynArr(dyn, 5);
addDynArr(dyn, 6);
printf("\n");
printf("The array's content:
[3,4,10,5,6]\n");
assertTrue(EQ(getDynArr(dyn, 0), 3), "Test 1st element
== 3");
assertTrue(EQ(getDynArr(dyn, 1), 4), "Test 2nd element
== 4");
assertTrue(EQ(getDynArr(dyn, 2), 10), "Test 3rd
element == 10");
assertTrue(EQ(getDynArr(dyn, 3), 5), "Test 4th element
== 5");
assertTrue(EQ(getDynArr(dyn, 4), 6), "Test 5th element
== 6");
assertTrue(sizeDynArr(dyn) == 5, "Test size =
5");
printf("\n\nTesting putDynArr...\nCalling
putDynArr(dyn, 2, 7)\n");
putDynArr(dyn, 2, 7);
printf("The array's content: [3,4,7,5,6]\n");
assertTrue(EQ(getDynArr(dyn, 2), 7), "Test 3rd element
== 7");
assertTrue(sizeDynArr(dyn) == 5, "Test size =
5");
printf("\n\nTesting swapDynArr...\nCalling
swapDynArr(dyn, 2, 4)\n");
swapDynArr(dyn, 2, 4);
printf("The array's content: [3,4,6,5,7]\n");
assertTrue(EQ(getDynArr(dyn, 2), 6), "Test 3rd element
== 6");
assertTrue(EQ(getDynArr(dyn, 3), 5), "Test 4th element
== 5");
assertTrue(EQ(getDynArr(dyn, 4), 7), "Test 5th element
== 7");
printf("\n\nTesting removeAtDynArr...\nCalling
removeAtDynArr(dyn, 1)\n");
removeAtDynArr(dyn, 1);
printf("The array's content: [3,6,5,7]\n");
assertTrue(EQ(getDynArr(dyn, 0), 3), "Test 1st element
== 3");
assertTrue(EQ(getDynArr(dyn, 1), 6), "Test 2nd element
== 6");
assertTrue(EQ(getDynArr(dyn, 2), 5), "Test 3rd element
== 5");
assertTrue(EQ(getDynArr(dyn, 3), 7), "Test 4th element
== 7");
assertTrue(sizeDynArr(dyn) == 4, "Test size =
4");
printf("\n\nTesting stack interface...\n");
printf("The stack's content: [3,6,5,7] <-
top\n");
assertTrue(!isEmptyDynArr(dyn), "Testing
isEmptyDynArr");
assertTrue(EQ(topDynArr(dyn), 7), "Test topDynArr ==
7");
popDynArr(dyn);
printf("Poping...\nThe stack's content: [3,6,5] <-
top\n");
assertTrue(EQ(topDynArr(dyn), 5), "Test topDynArr ==
5");
assertTrue(sizeDynArr(dyn) == 3, "Test size =
3");
pushDynArr(dyn, 9);
printf("Pushing 9...\nThe stack's content: [3,6,5,9]
<- top\n");
assertTrue(EQ(topDynArr(dyn), 9), "Test topDynArr ==
9");
printf("\n\nTesting bag interface...\n");
printf("The bag's content: [3,6,5,9]\n");
assertTrue(containsDynArr(dyn, 3), "Test containing
3");
assertTrue(containsDynArr(dyn, 6), "Test containing
6");
assertTrue(containsDynArr(dyn, 5), "Test containing
5");
assertTrue(containsDynArr(dyn, 9), "Test containing
9");
assertTrue(!containsDynArr(dyn, 7), "Test not
containing 7");
assertTrue(sizeDynArr(dyn) == 4, "Test size =
4");
removeDynArr(dyn, 3);
printf("Removing 3...\nThe stack's content:
[6,5,9]\n");
assertTrue(!containsDynArr(dyn, 3), "Test not
containing 3");
assertTrue(!containsDynArr(dyn, 6), "Test not
containing 6");
assertTrue(!containsDynArr(dyn, 5), "Test not
containing 5");
assertTrue(!containsDynArr(dyn, 9), "Test not
containing 9");
assertTrue(sizeDynArr(dyn) == 3, "Test size =
3");
return 0;
}
This assignment is comprised of 3 parts: All files needed are located at the end of...
Header file #ifndef DYNAMIC_ARRAY_INCLUDED #define DYNAMIC_ARRAY_INCLUDED 1 #ifndef __TYPE #define __TYPE # define TYPE int # define TYPE_SIZE sizeof(int) # endif # ifndef LT # define LT(A, B) ((A) < (B)) # endif # ifndef EQ # define EQ(A, B) ((A) == (B)) # endif typedef struct DynArr DynArr; /* Dynamic Array Functions */ void initDynArr(DynArr *v, int capacity); DynArr *newDynArr(int cap); void freeDynArr(DynArr *v); void deleteDynArr(DynArr *v); int sizeDynArr(DynArr *v); void addDynArr(DynArr *v, TYPE val); TYPE getDynArr(DynArr *v, int...
All the functions are written and work besides removeLinkedList and contains LinkedList. Please fill those out. 무#ifndef #define LINKEDLIST-H LINKEDLISTH define TYPE /*# define TYPE SIZE sizeof (TYPE) */ double typedef struct ListStack LinkedList; void initLinkedLǐst(LinkedList *1); void freeLinkedList (LinkedList *1) int İsEmptyLinkedList (LinkedList*1); void pushLinkedList (LinkedList #1, TYPE val); TYPE topLinkedList (LinkedList 1) void popLinkedList (LinkedList *1); /* Bag / void addLinkedList (LinkedList *1, TYPE val) ; int containsLinkedList (LinkedList *1, TYPE val) ; void removeLinkedList (LinkedList l, TYPE...
In addition to the base files, three additional files are attached: EmptyCollectionException.java, LinearNode.java, and StackADT.java. These files will need to be added to your Java project. They provide data structure functionality that you will build over. It is suggested that you test if these files have been properly added to your project by confirming that Base_A05Q1.java compiles correctly. Complete the implementation of the ArrayStack class. Specifically, complete the implementations of the isEmpty, size, and toString methods. See Base_A05Q1.java for a...
Can you help with this C programming question. I have provided the skeleton code below along with the Stack/Data/Process Class for you to see/reference. Along with the Stack/Data type definition. **SKELTON CODE** #include #include #include Stack* concat_stack(Stack *s1, Stack *s2) { //your code here return NULL; } **STACK CLASS FOR YOU TO REFERENCE** #include #include #include #include Stack* create_stack(int stack_capacity) { Stack *s = (Stack*) malloc(sizeof(Stack)); if (stack_capacity < 1) { fprintf(stderr, "Error(create_stack): invalid capacity, set to 10\n"); s->capacity =...
Doubly Linked List The assignment is to modify the below code in any way (like changing the method of a function). Time complexity is omitted. Any methods/functions below could be changed into something different. I was thinking of changing the method of getting size of list and maybe change from numbers to letters for nodes. import java.util.Scanner; /* Class Node */ class Node { protected int data; protected Node next, prev; /* Constructor */ public Node() { next = null;...
enum {FALSE=0, TRUE}; #define MAXBUFF 1024 #define SMALLBUFF 10 /* The LinkNode type is used as an element of a linked list ** implementation of a stack of tree nodes. */ typedef struct link_t LinkNode; typedef LinkNode *LinkNodePtr; /* The TreeNode type is used as an element of a binary "parse" tree. ** Tree nodes are created while parsing the RPN expression and ** stored on a stack until it's time to place them. */ typedef struct tree_t TreeNode; typedef...
Please answer problem #5 thank you str.c #include "str.h" #include <stdio.h> int str_len(char *s) { /* this is here so code compiles */ return 0; } /* array version */ /* concantenate t to the end of s; s must be big enough */ void str_cat(char s[], char t[]) { int i, j; i = j = 0; while (s[i] != '\0') /* find end of s */ i++; while ((s[i++] = t[j++]) != '\0') /* copy t */ ;...
Implement the EasyStack interface with the MyStack class. You can use either a linked list or a dynamic array to implement the data structure. A stack is a specialised form of list in which you can only get and remove the element most recently added to the stack. The class should be able to work with the following code: EasyStack stack = new MyStack(); NB: You cannot import anything from the standard library for this task. The data structure must...
Doubly Linked List Is there a way to further modify/simplify/improve this program? I was thinking of maybe changing how to get size. I'm not sure. import java.util.Scanner; /* Class Node */ class Node { protected int data; protected Node next, prev; /* Constructor */ public Node() { next = null; prev = null; data = 0; } /* Constructor */ public Node(int d, Node n, Node p) { data = d; next = n; prev = p; } /* Function...
Use the header and other files listed below for problems 1 and 2. Each problem has 3 files that correspond to the problem. Problem 1, linked list deque and bag implementations. First, complete the linked list implementation of the deque and bag ADTs in C language. To do this, implement all functions with the // FIXME... comments in linkedList.c (File included below). These functions listed are the ones that need to be fixed. init addLinkBefore removeLink linkedListAddFront linkedListAddBack linkedListFront linkedListBack...