prefix: 1개의 글

알고리즘(Algorithm) 실습2

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

 

1-1. 주어진 postfix 표기의 식을 입력해서 스택을 사용해서 주어진 식을 연산하 는 알고리즘을 완성하고, 실습하시오

#include<iostream>

 

using namespace std;

typedef int itemType; // typedef를 사용해 itemType의 데이터형을 지정한다

 

class Stack1

{

private:

itemType *stack;

int p;

public:

Stack1(int max=100){ // Stack1 class 생성자

stack=new itemType[max];

p=0;

}

 

~Stack1(){ // Stack1 class 소멸자

delete stack;

}

 

inline void push(itemType v){ // 스택의 데이터 삽입

stack[p++]=v;

}

 

inline itemType pop(){ // 스택의 데이터 삭제

return stack[--p];

}

 

inline int empty(){

return !p;

}

};

 

int main()

{

char c;

Stack1 acc(50);

int x;

while ((c=cin.get()) != '\n') // 엔터(next line)가 입력되기 전까지의 문자열을 변수 c에 담는다.

{

x=0;

 

while(c==' '){ // 공백으로 다음 input을 구분

 

cin.get(c);

}

 

if(c=='+') x = acc.pop() + acc.pop();

// 변수 c에 ‘+’ 문자가 있을 시 스택에 있는 두 데이터를 꺼내 더한다.

 

if(c=='*') x = acc.pop() * acc.pop();

// 변수 c에 ‘*’ 문자가 있을 시 스택에 있는 두 데이터를 꺼내 곱한다.

 

while(c>='0' && c<='9') // 2자리수를 입력받기위한 연산

{

x=10*x+(c-'0');

cin.get(c);

}

 

acc.push(x); // +,* 연산 혹은 두 자리수 입력을 받은 후 다시 스택에 저장

}

cout << acc.pop() << '\n'; // 최종 연산결과 출력

 

return 0;

}

 

▣ 결과 출력


- Input Data : 20 30 * 45 3 * + 10 * 9 +

- Output Data : 7359



2_2. 포인터를 사용하여 데이터구조 스택(STACK2)를 구현하고, 다른 연산(-,/)도 포함된 다음의 data를 처리하는 알고리즘으로 수정하여 실습하시오.

 

#include<iostream>

using namespace std;

 

typedef int itemType; // typedef를 사용해 itemType의 데이터형을 지정한다

class Stack2

{

private:

struct node{ // 리스트를 이용한 스택 연산을 구현

itemType key;

struct node *next;

};

struct node *head, *z;

public:

Stack2(){ // Stack2 Class의 생성자

head = new node; // 스택의 top을 나타내는 리스트의 head

head->next = NULL; // head의 link field인 next를 NULL로 초기화

}

~Stack2(){ // Stack2 Class의 소멸자

delete head;

}

inline void push(itemType v){ // 스택의 데이터 삽입

 

z = new node; // 신규 노드 생생

 

head->key = v; // head가 가르키는 key에 데이터 삽입

z->next = head; // 신규노드의 link field가 이전 삽입된 노드를 가르키게 한다

head = z; // head가 신규노드를 가르키게 한다

}

inline itemType pop(){ // 스택의 데이터 삭제

itemType v = head->next->key;

// 스택의 가장 윗부분에 있는 데이터를 변수 v에 저장

 

head = head->next; // pop되는 다음 노드를 head가 가르키게 한다

return v; // 가장늦게 저장된, 스택의 가장 위에 있는 데이터 리턴 pop

}

inline int empty(){

return 0;

}

};

int main()

{

char c;

Stack2 acc;

int x, op1, op2; // 사칙연산을 위한 변수

 

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

{

x=0;

while(c==' '){ // 공백으로 다음input을 구분

cin.get(c);

}

 

if(c=='+' || c=='-' || c=='*' || c=='/'){

// 숫자가 아닌 사칙연산 데이터 입력 시 스택의 데이터 pop 후사칙연산 수행

op2 = acc.pop(); /* 사칙연산을 위해 스택의 데이터를

op1 = acc.pop(); 변수 op1,op2에 저장 */

 

switch(c){ // pop된 두 데이터의 사칙연산

 

case '+': x = op1 + op2; break;

case '-': x = op1 - op2; break;

case '*': x = op1 * op2; break;

case '/': x = op1 / op2; break;

 

}

}

while(c>='0' && c<='9'){ // 2자리수를 입력받기위한 연산

x=10*x+(c-'0');

cin.get(c);

}

acc.push(x); 사칙연산 혹은 두 자리수 입력을 받은 후 다시 스택에 저장

}

cout << acc.pop() << ‘\n‘; // 최종 연산결과 출력

return 0;

}

▣ 결과 출력


- Input Data : 20 30 * 45 3 / + 10 * 9 -

- Output Data : 6141




2_3. n개의 양의 정수를 random 함수로 발생한 집단을 X라 할 때 X를 2집단 A와 B로 분할해서 A에 속한 원소들의 합 a와 B에 속한 원소들의 합 b를 구한다. 이 때 a와 b의 차이가 주어진 기준값 T보다 작게 X를 누날 수 있는지를 결정하는 알고리즘을 작성하고 실습하시오. 단, X의 분할은 임의로 하며, n≥10.

#include<stdlib.h>

#include<time.h>

#include<iostream>

using namespace std;

 

void main(void) {

 

int n, t, i, sum=0, a=0, b; //n개의 양의정수 발생과, 기준값 T, 집단 a,b를 위한 변수

int x[100]; // random 발생 양의정수가 들어갈 배열 / 임의값 100으로 초기화 하였다

 

cout << "두 수를 입력하세요 : ";

cin >> n >> t; // n과 기준값 t를 입력받는다.

 

 

srand(time(NULL)); // 현재시간을 가져와 매 초마다 변경한다.

 

// n 까지의 random 수 배열에 저장

for (i=0; i<n; i++){

 

x[i] = rand()%n+1; // rand()의 범위 : 0~n ( n=10 | rand() = 0~10 )

sum += x[i]; // 발생되는 random 수의 총 합을 구한다.

}

 

i=0;

while(a<(sum/2)) a += x[i++];

// n개의 양의 정수를 random 함수로 발생한 집단 X의 총합의 1/2 과 가장 가까운 근사치가

나올 때까지의 합이 집단 A의 속한 원소들의 합인 a로 된다

b = sum - a; // 총합에서 a를 뺀 것이 B에 속한 원소들의 합인 b가 된다.

 

cout << "\n X = " << sum << "\n a = " << a << "\n b = " << b<< "\n\n";

// 집단X의 총합과 A,B집단에 속한 원소들의 합(a,b)을 각각 출력한다.

 

cout << " T = " << t << " a-b = " << a-b << "\n\n\n";

// 처음 입력받은 T의 값과, a-b의 값을 출력한다.

(기준값 T와 a-b의 값 중 djEJsrjt이 더 X를 작게 나눌 수 있다.)

}

▣ 결과 출력


- Input Data : 20 5

- Output Data : T=5 / a-b=2

'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