สแตก (Stack)

//  main.c
//  withcsWEEK4
//
//  Created by JihwanLEE on 2017. 5. 9..
//  Copyright ? 2017? jihwanlee. All rights reserved.
//
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
typedef struct node {
	double        dataPtr;
	struct node* link;
} STACK_NODE;
	typedef struct {
	int         count;
	STACK_NODE* top;
} STACK;
STACK*  createStack     (void);
bool    pushStack       (STACK* stack, double dataInPtr);
double   popStack        (STACK* stack);
double   stackTop        (STACK* stack);
bool    emptyStack      (STACK* stack);
bool    fullStack       (STACK* stack);
int     stackCount      (STACK* stack);
STACK*  destroyStack    (STACK* stack);
// 
STACK* createStack (void) {
	STACK* stack;
	stack = (STACK*) malloc (sizeof(STACK));
	if(stack) {
		stack->count = 0;
		stack->top   = NULL;
	}
	printf("Address of stack: %p on createStack\n", &stack);
	return stack;
}
//
bool pushStack (STACK* stack, double dataInPtr) {
	STACK_NODE* newPtr;
	// memory allocation
	newPtr = (STACK_NODE*) malloc (sizeof(STACK_NODE));
	if(!newPtr) return false;
	newPtr->dataPtr = dataInPtr;
	newPtr->link    = stack->top;
	stack->top      = newPtr;
	(stack->count)++;
	return true;
}
//
double popStack (STACK* stack) {
	double       dataOutPtr;
	STACK_NODE* temp;
	if(stack->count == 0) {
		dataOutPtr = -1;
		printf("stack empty : POP\n");
	}
	else {
		temp        = stack->top;
		dataOutPtr  = stack->top->dataPtr;
		stack->top  = stack->top->link;
		free(temp);
		stack->count--;
	}
	return dataOutPtr;
}
//
double stackTop (STACK* stack) {
	if(stack->count == 0) {
		printf("stack empty: stackTOP\n");
		return -1;
	}
	else
		return stack->top->dataPtr;
}
//
bool emptyStack (STACK* stack) {
	return (stack->count == 0);
}
//
bool fullStack (STACK* stack) {
	STACK_NODE* temp;
	printf("Address of temp (New Node): %p\n", &temp);
	printf("Address of stacktop: %p\n", &(stack->top));
	if((temp = (STACK_NODE*) malloc (sizeof(*(stack->top))))) {
		free(temp);
		return false;
	}
	return true;
}
//
int stackCount (STACK* stack) {
	return stack->count;
}
//
STACK* destroyStack (STACK* stack) {
	STACK_NODE* temp;
	if(stack) {
		while(stack->top != NULL) {
			temp       = stack->top;
			stack->top = stack->top->link;
			free(temp);
		}
		free(stack);
	}
	return NULL;
}
//
int main() {
	STACK* stack = createStack();
	char string[100];
	string[0]='h';
	string[1]='e';
	string[2]='l';
	string[3]='l';
	string[4]='o';
	printf("string have %zu chars \n",strlen(string)); // 5
	printf("stackCount = %i \n",stackCount(stack)); // 0
	pushStack(stack,string[0]); // h
	printf("stackCount = %i \n",stackCount(stack)); // 1 = h
	for(int i=0; i<strlen(string); i++) pushStack(stack,string[i]);
	pushStack(stack,string[0]); // hhelloh
	printf("stackCount = %i \n",stackCount(stack)); // 7
	printf("stackTop = %.0f \n",stackTop(stack)); // 104 = h
	printf("%.0f \n",popStack(stack)); // 104 = h
	printf("%.0f \n",popStack(stack)); // 111 = o
	printf("%.0f \n",popStack(stack)); // 108 = l
	printf("%.0f \n",popStack(stack)); // 108 = l
	if(!emptyStack(stack)) printf("emptyStack = false \n"); // false
	if(!fullStack(stack)) printf("fullStack = false \n"); // false
	printf("%.0f \n",popStack(stack)); // 101 = e
	printf("%.0f \n",popStack(stack)); // 104 = h
	printf("%.0f \n",popStack(stack)); // 104 = h
	printf("%.0f \n",popStack(stack)); // stack empty : POP and -1
    printf("sizeof int = %zu bytes\n", sizeof (int)); // 4 bytes
    printf("sizeof string[100] = %zu bytes\n", sizeof string); // 100 bytes
    destroyStack(stack);
    printf("stackCount = %i \n",stackCount(stack)); // -1587399272 
	return 0;
}

โจทย์ให้ฝึกแปลงจาก infix เป็น postfix โดยใช้ stack ตามตัวอย่าง
1. a + b - c * d / e - f + g * h 
2. a * b - c * d + e - f + g * h 
3. a + b * c * d / (e * f) * g + h 
4. a + b - (c * d) - e - f + g - h 
5. a + (b + c) * d / e + f / g * h 
6. a / b * c * d * (e - f) + g ^ h 
7. (a ^ b) / c * d / e - f + g + h 
8. a * b ^ c * ((d - e) - f) * g - h 
9. a + b - c ^ ((d - e) - f) * (g - h) 
10. a / (b + c) * (d + (e + f)) ^ g + h