마이실피르넷

//다항식의 덧셈 연결리스트로 구현

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

typedef struct ListNode { //리스트 노드 구조
	int coef; //계수
	int exp; //지수
	struct ListNode *link;
} ListNode;

typedef struct ListHeader { //리스트 헤더 노드 구조
	int length;
	ListNode *head;
	ListNode *tail;
} ListHeader;

void init(ListHeader *plist) // 초기화, 공백 헤더 노드
{
	plist->length = 0; //length를 0으로
	plist->head = plist->tail = NULL; // head와 tail을 NULL으로
}

// 연결 리스트에 삽입
// plist는 헤더를 가리키는 포인터, coef는 계수, exp는 지수
void insert_node_last(ListHeader *plist, int coef, int exp)
{
	//공백 연결리스트 생성
	ListNode *temp = (ListNode *)malloc(sizeof(ListNode));
	if(temp == NULL){
		exit(1);
	}
	temp->coef=coef;
	temp->exp=exp;
	temp->link=NULL;
	if(plist->tail == NULL){
		plist->head = plist->tail = temp;
	}
	else {
		plist->tail->link = temp;
		plist->tail = temp;
	}
	plist->length++; //length 증가
}

// 다항식 덧셈
// 다항식3 = 다항식1 + 다항식2
void poly_add(ListHeader *plist1, ListHeader *plist2, ListHeader *plist3)
{
	ListNode *a = plist1->head;
	ListNode *b = plist2->head;
	int sum; //계수를 담을 변수

	while(a && b){
		if(a->exp == b->exp){ //지수가 같을경우
			sum = a->coef + b-> coef;
			if( sum != 0 ) insert_node_last(plist3, sum, a->exp);
			a=a->link; b=b->link; 
		}
		else if(a->exp > b->exp){ //다항식1의 지수가 클경우
			insert_node_last(plist3, a->coef, a->exp);
			a=a->link;
		}
		else {
			insert_node_last(plist3, b->coef, b->exp);
			b=b->link; 
		}
	}
	//남아있는 항들을 모두 다항식3으로 복사
	for(; a != NULL; a=a->link) 
		insert_node_last(plist3, a->coef, a->exp);
	for(; b != NULL; b=b->link) 
		insert_node_last(plist3, b->coef, b->exp);
}

//다항식 출력
void poly_print(ListHeader *plist)
{
	ListNode *p=plist->head;
	for(;p;p=p->link){
		if (p->coef == 0 || p->exp == 0){
			printf(""); //계수 or 지수가 0이면 표시하지 않음
		}else if (p->exp == 1){
			printf("%d",p->coef); //지수가 1이면 계수만 표시
		}else{
			printf("%dx^%d", p->coef, p->exp);
			//계수 or 지수가 0이 아니면 계수x^지수 형태로 표시
			if (p->link == NULL)
			{
				printf("");
			}else{
				printf(" + ");
			}
		}
	}
	printf("\n");
}

void main()
{
	ListHeader list1, list2, list3; //다항식 입력받을 변수 선언

	init(&list1);//init 함수 호출로 공백 리스트
	init(&list2);
	init(&list3);

	int a,b; //항의 계수와 지수를 입력받기 위한 변수

	//다항식1을 입력받는 부분
	printf("다항식1의 항(계수,지수)을 입력하세요. (0 0 이면 입력종료)\n");
	while (1)
	{
		scanf("%d %d",&a,&b);
		if (a==0 && b==0)
		{
			break;
		}
		insert_node_last(&list1, a, b);
	}
	printf("다항식1 : ");
	poly_print(&list1); //다항식1 출력
	printf("\n");

	//다항식2을 입력받는 부분
	printf("다항식2의 항(계수,지수)을 입력하세요. (0 0 이면 입력종료)\n");
	while (1)
	{
		scanf("%d %d",&a,&b);
		if (a==0 && b==0)
		{
			break;
		}
		insert_node_last(&list2, a, b);
	}
	printf("다항식2 : ");
	poly_print(&list2); //다항식2 출력
	printf("\n");

	// 다항식3 = 다항식1 + 다항식2
	poly_add(&list1, &list2, &list3);

	printf("결과 : ");
	poly_print(&list3); //다항식3 출력
}

PolyAdd_list.cpp

#include <stdio.h>
#include <string.h>

#define MAX_STACK_SIZE 100
#define MAX_EXPR_SIZE 100

typedef enum {lparen, rparen, plus, minus, times, divide, mod, eos, operand} precedence;

int eval(void);
void push(int *, int);
int pop(int *);
void print_token(int);
void infix_to_postfix(void);
precedence get_token(char *, int *);

int stack[MAX_STACK_SIZE];
char expr[MAX_EXPR_SIZE];
char str[MAX_STACK_SIZE];
int Num[50];
int num = 0;

void main()
{
	printf("Input string : \n");
	scanf("%s", expr);
	printf("postfix : \n");
	infix_to_postfix();
	printf("result:\n");
	printf("%d\n", eval());
}

int eval()
{
	precedence token;
	char symbol;
	int op1, op2;
	int n = 0, m = 0, k = 0;
	int top = -1, j=0;

	token = get_token(&symbol, &n);

	while(token != eos)
	{
		if(token == operand)
		{
			m = m*10 + symbol-'0';
			k++;
			if(Num[j] == k)
			{
				push(&top, m);	
				j++;
				m = 0;
				k = 0;
			}
		}	
		else
		{
			op2 = pop(&top);
			op1 = pop(&top);
			switch(token)
			{
			case plus:
				push(&top, op1+op2);
				break;
			case minus:
				push(&top, op1-op2);
				break;
			case times:
				push(&top, op1*op2);
				break;
			case divide:
				push(&top, op1/op2);
				break;
			case mod:
				push(&top, op1%op2);
				break;
			}
		}
		token = get_token(&symbol, &n);
	}
	return pop(&top);
}

precedence get_token(char *psymbol, int *pn)
{
	*psymbol = expr[(*pn)++];

	switch(*psymbol)
	{
	case '(': return lparen;
	case ')': return rparen;
	case '+': return plus;
	case '-': return minus;
	case '*': return times;
	case '/': return divide;
	case '%': return mod;
	case '\0': return eos;
	default : return operand;
	}
}

void push(int *top, int op)
{
	(*top)++;
	stack[*top] = op;
}

int pop(int *top)
{
	int n;

	n = stack[*top];
	(*top)--;
	return n;
}

void infix_to_postfix()
{
	char symbol;
	int token;
	int n = 0, m = 0, i = 0;
	int top = 0;
	static int isp[] = { 0, 19, 12, 12, 13, 13, 13, 0};
	static int icp[] = {20, 19, 12, 12, 13, 13, 13, 0};

	stack[0] = eos;

	for(token = get_token(&symbol, &n); token != eos; token = get_token(&symbol, &n))
	{
		if(token == operand)
		{
			str[num] = symbol;
			num++;
			m++;
			Num[i] = m;
		}
		else if(token == rparen)
		{
			while(stack[top] != lparen)
				print_token(pop(&top));
			pop(&top);
		}
		else
		{
			if(token != lparen)
			{
				i++;
				m=0;
			}
			while(isp[stack[top]] >= icp[token])
				print_token(pop(&top));
			push(&top, token);
		}
	}
	while((token = pop(&top)) != eos)
		print_token(token);
	printf("%s\n", str);
	strcpy(expr, str);
}

void print_token(int token)
{
	switch(token)
	{
	case minus:
		str[num] = '-';
		break;
	case plus:
		str[num] = '+';
		break;
	case times:
		str[num] = '*';
		break;
	case divide:
		str[num] = '/';
		break;
	case mod:
		str[num] = '%';
		break;
	}
	num++;
}

stack_evalPostfix.cpp

#include <stdio.h>
#include <stdlib.h>
#define STACK_SIZE 100 // 스택의 최대 크기

char stack[STACK_SIZE];
char expr[STACK_SIZE];
int stackSize=0;

int isEmpty()
{
	if (!stackSize)
	{
		return 1;
	}
	return 0;
}

void push(char item)
{
	stack[stackSize] = item; // top은 top+1로
	stackSize++;
}

char pop()
{
	if (isEmpty())
	{
		return -1;
	}
	stackSize--;
	return stack[stackSize];
}


int chSymbol(char *psymbol)
{

	char temp;
	int cnt = 0;

	while (1)
	{
		temp = *(psymbol+cnt);
		if (temp == '\0') break;

		switch(temp) {
			case '(': case '[': case '{':
				push(temp);
				break;
			case ')': 
				if (isEmpty() || pop() != '(')
				{
					return 0;
				}
				break;
			case ']': 
				if (isEmpty() || pop() != '[')
				{
					return 0;
				}
				break;
			case '}':
				if (isEmpty() || pop() != '{')
				{
					return 0;
				}
				break;
		}
		cnt++;
	}
	if (!isEmpty())
		return 0;

	return 1;
}

void main()
{
	printf("수식을 입력하세요.\n");
	scanf("%s",expr);

	printf("괄호검사 결과 : ");
	if (chSymbol(expr) == 1)
	{
		printf("true\n");
	}else{
		printf("false\n");
	}
}

stack_parenTest.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct //스택 원소 구조
{
	int id;
	char name[10];
	char grade;
}element;

typedef struct stackNode // 리스트 노드 구조
{
	element data;
	struct stackNode *link;
}stackNode;

void push(stackNode **top, element data) 
{
	// 스택의 탑에 원소를 삽입
	stackNode* temp;
	temp = (stackNode*)malloc(sizeof(stackNode));
	temp->data = data;
	temp->link = *top;
	*top = temp;
}

element pop(stackNode **top)
{
	// 스택의 탑 원소를 반환하고 노드는 삭제
	stackNode* temp;
	element data;
	temp = *top;
	if (temp == NULL) // 스택이 공백이면
	{
		printf("Stack is empty\n");
		exit(1);
	}else{
		data = temp->data;
		*top = temp->link;
		free(temp); // 연결 리스트에서 노드를 삭제
		return data;
	}
}

element peek(stackNode *top)
{
	// 스택의 탑 원소를 검색
	element data;
	if (top == NULL)
	{
		printf("Stack is empty\n");
		exit(1);
	}else{
		data = top->data;
		return data;
	}
}

void Delete(stackNode **top)
{
	// 스택의 탑 원소를 삭제
	stackNode* temp;
	if (*top == NULL) // 스택이 공백이면
	{
		printf("Stack is empty\n");
		exit(1);
	}else{
		temp = *top;
		*top = (*top)->link;
		free(temp);
	}
}

void main()
{
	stackNode *top = NULL; // 공백 연결 스택으로 탑을 선언
	element data1, data2, data3, data4;

	data1.id = 1;
	strcpy(data1.name, "Lee");
	data1.grade = 'A';
	data2.id = 2;
	strcpy(data2.name, "Park");
	data2.grade = 'B';

	printf("push data1 : (%d %s %d)\n", data1.id, data1.name, data1.grade);
	push(&top, data1);
	printf("push data2 : (%d %s %d)\n", data2.id, data2.name, data2.grade);
	push(&top, data2);

	data3 = peek(top);
	printf("peek data2 : (%d %s %d)\n", data3.id, data3.name, data3.grade);
	Delete(&top);
	printf("Delete data2\n");
	data4 = pop(&top);
	printf("pop data1 : (%d %s %d)\n", data4.id, data4.name, data4.grade);
}

list_stack.cpp

#include <stdio.h>
#include <stdlib.h>
#define STACK_SIZE 100 // 스택의 최대 크기

typedef int element; // element를 int 타입으로 정의
element stack[STACK_SIZE];

void push(int *top, element item)
{
	if (*top >= STACK_SIZE - 1) // 스택이 만원인 경우
	{
		printf("Stack is full\n");
		return;
	}
	stack[++(*top)] = item; // top은 top+1로
}

element pop(int *top)
{
	if (*top == -1) // 스택이 공백인 경우
	{
		printf("Stack is empty\n");
		exit(1);
	}else{
		return stack[(*top)--];
	}
}

int isEmpty(int *top)
{
	if (*top == -1)
	{
		return 1; // 공백이면 1
	}else{
		return 0; // 공백이 아니면 0
	}
}

void Delete(int *top)
{
	if (*top == -1) // 스택이 공백인 경우
	{
		printf("Stack is empty\n");
		exit(1);
	}else{
		(*top)--;
	}
}

element peek(int top)
{
	if (top == -1) // 스택이 공백인 경우
	{
		printf("Stack is empty\n");
		exit(1);
	}else{
		return stack[top];
	}
}

int main(void)
{
	int top = -1;
	element data1, data2;
	printf("push data1 : %d\n", 1);
	push(&top,1);
	printf("push data2 : %d\n", 2);
	push(&top,2);
	data2 = peek(top);
	printf("peek data2 : %d\n", data2);
	Delete(&top);
	printf("Delete data2\n");
	data1 = pop(&top);
	printf("pop data1 : %d\n", data1);
	return 0;
}

array_stack.cpp

/*
[두 다항식의 덧셈 프로그램]
지수와 계수를 모두 저장하기 위해 1차원 배열을
두개 만들어 구조체로 만들고 계수와 지수를 저장하는 방법으로 구현
*/

#include <stdio.h>
#define SIZE 32 // p의 배열 갯수 설정

typedef struct
{
	int exp; //지수
	int coef; //계수
}poly; // 지수 1개, 계수 1개 넣을 수 있는 타입으로 생성

typedef struct
{
  int count; //항 갯수 카운트
  poly p[SIZE]; // poly형 타입의 배열
} polys;


int isZeroP(polys* ps) //남은 항이 있는지 확인
{
	int result=0; //항이 있을경우 0 (flase)
	if (ps->count==0) {
		result=1; //항이 없을경우 1 (true)
	}
	return result;
}

int coef(polys* ps, int e) //e와 같은 계수
{
	int result = 0; //e와 같은 계수가 없으면 "0"
	for (int i=0; i<ps->count; i++) // e와 같은 계수가 있으면 "해당 계수" 리턴
	{
		if (ps->p[i].exp == e)
		{
			result = ps->p[i].coef;
			break;
		}
	}
	return result;
}

int maxExp(polys* ps) //지수가 가장 큰 항의 지수
{
	int result = ps->p[0].exp; //첫번째 번지에 있는 지수를 기본값으로 주고
	for (int i=0; i<ps->count; i++) //각 항의 지수비교해서 "최고 지수"를 리턴
	{
		if (ps->p[i].exp > result)
		{
			result = ps->p[i].exp;
		}
	}
	return result;
}

void addTerm(polys* ps, int coef, int exp) //항을 추가
{
	ps->p[ps->count].exp = exp; //받아온 항과 지수를 각각 polys 타입에 저장
	ps->p[ps->count].coef = coef;
	ps->count++;
}

void delTerm(polys* ps, int e) //항을 제거
{
	int i;
	int flag = 0;
	if (isZeroP(ps)) return;
	for (i=0;i<ps->count;i++) {
		if (ps->p[i].exp == e)
			flag = 1;
		if (flag)
			ps->p[i] = ps->p[i+1];
	}

	if (flag)
		ps->count--;
}

char compare(int a, int b) // 지수 비교
{
	// a와 b를 비교하여  =, <, > 리턴
	if (a == b) return '=';
	else if (a < b) return '<';
	else return '>';
}

polys polyAdd(polys* p1, polys* p2) // p3다항식 = p1다항식 + p2다항식
{
	polys p3;
	p3.count = 0;
	int sum;

	while(!isZeroP(p1) && !isZeroP(p2)) { //p1,p2에 다항식이 있을경우
		switch (compare(maxExp(p1), maxExp(p2))) //최고지수 비교
		{
			case '<' : //p1의 지수가 p2의 지수보다 작으면
				addTerm(&p3,coef(p2,maxExp(p2)),maxExp(p2));
				delTerm(p2,maxExp(p2));
				break;

			case '=' : //p1,p2의 지수가 같으면
				sum = coef(p1,maxExp(p1)) + coef(p2,maxExp(p2));
				if (sum != 0)
				addTerm(&p3,sum,maxExp(p1));
				delTerm(p1,maxExp(p1));
				delTerm(p2,maxExp(p2));
				break;

			case '>' : //p1의 지수가 p2 지수보다 크면
				addTerm(&p3,coef(p1,maxExp(p1)),maxExp(p1));
				delTerm(p1,maxExp(p1));
				break;
		}
	}

	while(!isZeroP(p1)) { // p1의 나머지 항들을 p3로 복사
		addTerm(&p3,coef(p1,maxExp(p1)),maxExp(p1));
		delTerm(p1,maxExp(p1));
	}

	while(!isZeroP(p2)) { // p2의 나머지 항들을 p3로 복사
		addTerm(&p3,coef(p2,maxExp(p2)),maxExp(p2));
		delTerm(p2,maxExp(p2));
	}

	return p3;
}

void printPolys(polys* ps) { //다항식 출력
	int i;
	for (i=0;i<ps->count;i++) {

		if (ps->p[i].coef == 0){
			printf(""); //계수 0이면 표시 안함
		}else if (ps->p[i].exp == 1){
			printf("%d",ps->p[i].coef); //지수가 1이면 계수만 표시
		}else{
			printf("%dx^%d",ps->p[i].coef,ps->p[i].exp);
			printf(" + ");
			//지수가 0이 아니면 계수x^지수 형태로 출력
		}

		//if (i != ps->count-1)
		//	printf(" + ");
	}
	printf("\n");
}

void main()
{
	polys p1; //p1 다항식을 입력받을 polys타입의 변수
	polys p2; //p1 다항식을 입력받을 polys타입의 변수
	polys p3; //p1+p2다항식의 결과 p3를 저장할 polys타입의 변수

	p1.count = 0; //항 개수 카운트 초기값 0
	p2.count = 0;

	int a,b; //항의 계수와 지수를 입력받기 위한 변수

	//P1항 입력받아서 보여주는 부분
	printf("P1의 항(계수,지수)을 입력하세요. (0 0 이면 입력종료)\n");
	while (1)
	{
		scanf("%d %d",&a,&b);
		if (a==0 && b==0)
		{
			break;
		}
		addTerm(&p1,a,b);
	}
	printf("P1 다항식 : ");
	printPolys(&p1);
	printf("\n");

	//P2항 입력받아서 보여주는 부분
	printf("P2의 항(계수,지수)을 입력\n");
	while (1)
	{
		scanf("%d %d",&a,&b);
		if (a==0 && b==0)
		{
			break;
		}
		addTerm(&p2,a,b);
	}
	printf("P2 다항식 : ");
	printPolys(&p2);
	printf("\n");

	//P1+P2 다항식을 더한 결과 P3를 보여주는 부분
	printf("P3 다항식(P1+P2) : ");
	p3 = polyAdd(&p1,&p2);
	printPolys(&p3);
}

PolyAdd_type.cpp

/*
[두 다항식의 덧셈 프로그램]
1차원 배열에 계수만을 저장하고
원소의 개수를 지수로 하여 구하는 방식을 사용하여 구현
*/

#include <stdio.h>
#define SIZE 6 //다항식의 계수를 입력받을 배열 원소 개수 지정 (SIZE는 지수로 사용)

int p3[12]; //결과가 저장될 p3다항식 넉넉하게 배열 12개 지정

int isZeroP(int *p) //항이 있는지 여부
{
	int result=1;
	for (int i=0; i<SIZE; i++)
	{
		if (p[i] > 0)
		{
			result=0;
		}
	}
	return result;
}

void polyAdd(int *p1, int *p2) // p3다항식 = p1다항식 + p2다항식
{
	if (!isZeroP(p1) || !isZeroP(p2)) //p1,p2 한쪽에라도 항이 있으면
	{
		for (int i=0; i<SIZE; i++)
		{
			p3[i] = p1[i] + p2[i]; //p1,p2 다항식을 더한값을 p3에 넣어줌
		}
	}else{
		printf("항이 없습니다.\n\n");
	}
}

void polyPrint(int *p) //다항식 출력
{
	if (!isZeroP(p))
	{
		for (int i=0; i<SIZE; i++)
		{
			if (p[i] == 0){ //계수가 0이면 출력하지 않음
				printf("");
			}else if (i == SIZE-1){ //^1은 지수를 표시하지 않음
				printf("%d",p[i]);
			}else{
				printf("%dx^%d",p[i],SIZE-i); //계수x^지수 형태로 표시
				printf(" + ");
			}
		}
	}else{
		printf("항이 없습니다.\n");
	}
}

void main()
{
	int p1[SIZE]; //p1 다항식의 계수를 입력받을 배열
	int p2[SIZE]; //p2 다항식의 계수를 입력받을 배열

	int i; //반복문을 위한 변수
	
	printf("P1다항식의 계수를 입력하시오.\n");
	for (i=0; i<SIZE; i++)
	{
		printf("^%d 의 계수 : ",SIZE-i);
		scanf("%d",&p1[i]);
	}

	printf("P1 다항식 : ");
	polyPrint(p1); //p1 다항식 출력
	printf("\n");

	printf("P2다항식의 계수를 입력하시오.\n");
	for (i=0; i<SIZE; i++)
	{
		printf("^%d 의 계수 : ",SIZE-i);
		scanf("%d",&p2[i]);
	}
	printf("P2 다항식 : ");
	polyPrint(p2); //p2 다항식 출력
	printf("\n");
	
	polyAdd(p1,p2); // polyAdd 함수 호출 = p1,p2 다항식의 값을 넘겨줌

	printf("P3 다항식(결과) : ");
	polyPrint(p3); //p3 다항식 출력
	printf("\n");
}

PolyAdd_coef.cpp

3차원 배열

1) 행우선 순서
저장 순서 : 1행의 요소 → 2행의 요소 → 3행의 요소 → 4행의 요소, …

각 요소의 주소 계산 (단, 각 요소의 길이는 고려하지 않는다.)
--→ 다음과 같이 3차원 배열이 선언되었다면  

예) 기준 주소가 1000이고 3차원 배열이 다음과 같이 선언되었다면

int  Array [3][4][5]
Array [2][3][4]의 주소 = 1000 + (2-1) * 4 * 5 + (3-1) * 5 + (4-1) => 1033

2) 열우선 순서
저장 순서 : 1열의 요소 → 2열의 요소 → 3열의 요소 → 4열의 요소, …

각 요소의 주소 계산 (단, 각 요소의 길이는 고려하지 않는다.)
--→ 다음과 같이 3차원 배열이 선언되었다면

 예) 기준 주소가 1000이고 3차원 배열이 다음과 같이 선언되었다면

int  Array [3][4][5]
Array [2][3][4]의 주소 = 1000 + (2-1) * 4 * 5 + (4-1) * 4 + (3-1) => 1034