queue: 1개의 글

알고리즘(Algorithm) 실습3

Posted by Patchman
2010.02.15 14:34 Univ Study/알고리즘과 실습

3-1. 다음에 주어진 postfix 표기의 수식을 입력하여 스택을 사용해서 이진 parse 트리로 표현하고, 이 트리를 INORDER 트래버설한 결과를 출력하시오.

 

#include<iostream>

using namespace std;

 

typedef struct node* itemType; // node 구조체 선언

 

void traverse(struct node *t); // inorder traverse 함수 선언

void visit(struct node *t); // 출력 함수

 

class Stack // 트리 자료의 저장을 위한 스택 Class

{

private:

itemType *stack;

int p;

 

public:

 

Stack(int max=100) // Stack Class의 생성자

{stack = new itemType[max]; p=0;}

 

~Stack() // Stack Class의 소멸자

{delete stack;}

 

inline void push(itemType v) // 스택에 Data를 Push 한다

{stack[p++] = v;}

 

inline itemType pop() // 가장 최근에 Push된 Data를 Pup한다.

{return stack[--p];}

 

inline int empty() // 스택의 empty 체크

{return !p;}

 

};

 

struct node // node 구조체 함수 (Data가 저장될 info와, 트리의 left, right 노드)

{

char info; struct node *l, *r;

};struct node *x, *z;

void main()

{

char c; // Data가 입력된 문자형 변수 선언

 

Stack stack(50); // Stack Class 선언

 

z = new node; // x노드 출력시 하위노드 유무 상태파악을 위한 z노드 생성

z->l = z;

z->r = z;

 

while((c = cin.get()) != '\n') // 사용자의 엔터(next line)키가 입력되기 전까지

반복문 실행

{

while(c == ' ') cin.get(c); // 공백(스페이스)으로 다음input을 구분

 

x = new node; // 스택에 저장될 x 노드 생성

x->info = c; // x노드에 입력된 값을 넣는다

x->l = z; // 하위노드 유무 확인를 위하여 z노드를 가르키게 한다

x->r = z; // 하위노드 유무 확인를 위하여 z노드를 가르키게 한다

 

if(c=='+' || c=='*') // ‘+’,‘*’연산자의 경우 스택에 저장된 값을 꺼내

{ 오른쪽과, 왼쪽노드에 위치 시킨다(트리)

x->r = stack.pop();

x->l = stack.pop();

}

stack.push(x); // 스택에 x노드를 push한다.

}

traverse(x); // 스택에 저장이 완료된 x노드 트리를 traverse함수로 보낸다

}

 

void traverse(struct node *t)

{

if(t != z) // z노드와 비교하여 하위노드 유무를 확인한다

{

traverse(t->l); // left노드를 다시 taverse() 재귀호출한다.

visit(t); // 출력을 위하여 visit() 함수 호출

traverse(t->r); // right노드를 다시 taverse() 재귀호출한다.

}

}

void visit(struct node *t)

{

cout << t->info << " " // 전달받은 노드의 값(info)을 출력

}

 

 

▣ 결과 출력


- Input Data : A B C + D E * * F + *

- Output Data : A * B + C * D * E + F

 

 

 

 

 

 

3-2. 3-1에서 만들어진 트리에 대해서 큐를 사용하여 lever order로 트래버설한 결과를 출력하는 프로그램을 완성하고 실습하시오.

 

#include<iostream>

using namespace std;

 

typedef struct node* itemType; // node 구조체 선언

 

void levelOrderTraverse(struct node *t) // leverOrderTraverse 함수 선언

void visit(struct node *t); // 출력 함수

 

class Stack // 트리 자료의 저장을 위한 스택 Class

{

private:

itemType *stack;

int p;

 

public:

 

Stack(int max=100) // Stack Class의 생성자

{stack = new itemType[max]; p=0;}

 

~Stack() // Stack Class의 소멸자

{delete stack;}

 

inline void push(itemType v) // 스택에 Data를 Push 한다

{stack[p++] = v;}

 

inline itemType pop() // 가장 최근에 Push된 Data를 Pup한다.

{return stack[--p];}

 

inline int empty() // 스택의 empty 체크

{return !p;}

 

};

class Queue // leverOrderTraverse 출력을 위한 Queue Class

{

private:

 

itemType *queue;

int head; // Queue의 위치를 위한 head, tail 변수와, 원형구조를 위한 size 변수선언

int tail;

int size;

 

public:

 

Queue::Queue(int max=100) // Queue Class의 생성자

{

size = max; // 원형 구조를 위한 size변수에 max값 대입

queue = new itemType[size];

head = 0;

tail = 0;

}

 

Queue::~Queue() // Queue Class의 소멸자

{delete queue;}

 

void Queue::put(itemType v) // Queue에 데이터 입력

{

queue[tail++] = v;

if(tail > size) tail = 0;

}

 

itemType Queue::get() // Queue에 저장된 데이터 출력

{

itemType t = queue[head++];

if(head > size) head = 0;

return t;

}

 

int Queue::empty()

{return head == tail;}

 

};

struct node // node 구조체 함수 (Data가 저장될 info와, 트리의 left, right 노드)

{

char info; struct node *l, *r;

};struct node *x, *z;

void main()

{

char c; // Data가 입력된 문자형 변수 선언

 

Stack stack(50); // Stack Class 선언

 

z = new node; // x노드 출력시 하위노드 유무 상태파악을 위한 z노드 생성

z->l = z;

z->r = z;

 

while((c = cin.get()) != '\n') // 사용자의 엔터(next line)키가 입력되기 전까지

반복문 실행

{

while(c == ' ') cin.get(c); // 공백(스페이스)으로 다음input을 구분

 

x = new node; // 스택에 저장될 x 노드 생성

x->info = c; // x노드에 입력된 값을 넣는다

x->l = z; // 하위노드 유무 확인를 위하여 z노드를 가르키게 한다

x->r = z; // 하위노드 유무 확인를 위하여 z노드를 가르키게 한다

 

if(c=='+' || c=='*') // ‘+’,‘*’연산자의 경우 스택에 저장된 값을 꺼내

{ 오른쪽과, 왼쪽노드에 위치 시킨다(트리)

x->r = stack.pop();

x->l = stack.pop();

}

stack.push(x); // 스택에 x노드를 push한다.

}

 

levelOrderTraverse(x); // 스택에 저장이 완료된 x노드 트리를

} leverOrderTraverse함수로 보낸다

 

void levelOrderTraverse(struct node *t)

{

Queue queue(50); // Queue Class 선언

queue.put(t); // 스택에 저장된 노드를 큐에 다시 입력한다.

while(!queue.empty()) // Queue의 empty 체크

{

t = queue.get(); // Queue의 노드를 꺼내 t에 저장

visit(t); // 출력을 위하여 visit() 함수 호출

if(t->l != z) queue.put(t->l); //하위노드(l)가 있다면 큐에 다시 입력

if(t->r != z) queue.put(t->r); //하위노드(r)가 있다면 큐에 다시 입력

}

}

void visit(struct node *t)

{

cout << t->info << " " // 전달받은 노드의 값(info)을 출력

}

 

 

▣ 결과 출력


- Input Data : A B C + D E * * F + *

- Output Data : * A + * F + * B C D E

'Univ Study > 알고리즘과 실습' 카테고리의 다른 글

알고리즘(Algorithm) 실습6  (0) 2010.02.15
알고리즘(Algorithm) 실습5  (0) 2010.02.15
알고리즘(Algorithm) 실습4  (0) 2010.02.15
알고리즘(Algorithm) 실습3  (0) 2010.02.15
알고리즘(Algorithm) 실습2  (0) 2010.02.15
알고리즘(Algorithm) 실습1  (0) 2009.05.05