주어진 postfix 표기의 식을 입력해서 스택을 사용해서 주어진 식을 연산하는 알고리즘을완성하시오.
#include <iostream>
using namespace std;
class Stack // 스택을 사용하기 위한 클래스다.
{
public:
Stack() // 메인함수에서 선언과 동시에 실행 되게 한다.
{
stack_top = -1; // 스택을 사용하기 위해 스택번호의 초기화
i = 0; // 입력받은 데이터 배열에서 사용하기 위한 인덱스 초기화
cout << "테스트 데이터를 입력하세요. [숫자와 연산자 중간에는 띄어쓰기를 해야 한다.]" << endl << "테스트 데이터 : "; // 입력받을 데이터 출력
cin.getline(test_data, 100, '\n'); // getline 함수를 사용해 띄어쓰기까지 입력받아서 test_data에 넣는다.
}
void Start() // 입력받은 데이터로 실행하는 함수
{
buf_ptr = buf; // buf_ptr를 buf의 시작주소로 초기화
while(test_data[i] != NULL) // test_data의 모든 단어를 읽은 후 반복문 종료
{
if(test_data[i] == ' ') // 띄어쓰기일때 실행
{
if(buf_ptr != buf) // 버퍼에 자료가 들어가 있다면 실행
Push(); // Push()함수를 이용해 test_data를 stack_arr에 넣는다.
while(buf_ptr != buf){ // buf의 데이터와 buf_ptr의 시작주소를 초기화
(*buf_ptr) = NULL;
buf_ptr--;
}
}
else if(test_data[i] < 48) // 유니코드 48아래인 특수기호가 test_data에 들어있을때 실행
Push(test_data[i]); // Push함수를 이용해 연산을 처리한다.
else
{
*buf_ptr = test_data[i]; // test_data의 숫자를 buf_ptr을 이용해 buf에 하나씩 넣는다.
buf_ptr++; // buf_ptr가 가리키는 주소 하나 증가
}
i++; // test_data의 인덱스 하나 증가
}
cout << "입력된 값에 대한 결과 값이 나왔습니다." << endl; // 모든 과정이 나온후 출력된다.
}
void Push()
{
stack_arr[++stack_top] = atoi(buf); // buf에 문자로 저장되어있는 숫자를 숫자로 바꾸어 인덱스 하나 증가하여 stack_arr에 넣는다..
}
void Push(char a)
{
if(a == '*') // 입력받은 문자중 '*'라면 스택에서 숫자 두개를 곱한후 두개중 첫번째 숫자 위치에 수를 저장하고 인덱스 하나 감소
stack_arr[stack_top-1] *= stack_arr[stack_top--];
else if(a == '+') // 입력받은 입력받은 문자중 '+'라면 스택에서 숫자 두개를 더한후 두개중 첫번째 숫자 위치에 수를 저장하고 인덱스 하나 감소
stack_arr[stack_top-1] += stack_arr[stack_top--];
}
void Print_Stack(void)
{
cout << "계산된 결과는 : " << *stack_arr << endl; // 계산된 결과를 출력하는 코드다.
}
private:
char test_data[100], buf[10]; // 클래스에서 사용 될 변수의 선언
char *buf_ptr;
int stack_arr[100];
int stack_top, i;
};
int main()
{
Stack s; // 선언과 동시에 사용자에게 입력을 받는다.
s.Start(); // 입력받은 문자를 이용해 연산
s.Print_Stack(); // 연산후 출력
}
스택을 사용해서 postfix 표기의 식을 입력받아 연산한다. 모든 데이터를 char형으로 입력받아 그것을 buf배열과 atoi함수를 이용해 int 형 배열에 스택으로 넣어놓고 연산기호를 입력 받았을 때 스택에 있는 수를 계산하고 다시 집어넣는 방식으로 구현 하였다.
2. 포인터를 사용하여 데이터구조 스택(STACK2)을 구현하고, 다른 연산( -./ )도 포함된 다음의 data를 처리하는 알고리즘으로 수정하여 실습하시오.
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
class Stack // 스택을 사용하기 위한 클래스다.
{
public:
Stack() // 메인함수에서 선언과 동시에 실행 되게 한다.
{
cout << "테스트 데이터를 입력하세요. [숫자와 연산자 중간에는 띄어쓰기를 해야 한다.]" << endl << "테스트 데이터 : "; // 입력받을 데이터 출력
cin.getline(test_data, 100, '\n'); // getline 함수를 사용해 띄어쓰기까지 입력받아서 test_data에 넣는다.
}
void Start() // 입력받은 데이터로 실행하는 함수
{
buf_ptr = buf; // buf_ptr를 buf의 시작주소로 초기화
stack_ptr = stack_arr; // 스택을 사용하기 위해 변수 대신에 포인터를 사용한다.
stack_ptr--; // 변수로 사용 할 때와 동일한 방식으로 사용하기 위해 주소값을 -1해준다.
i = 0; // test_data의 인덱스 초기화
while(test_data[i] != NULL) // test_data의 모든 단어를 읽은 후 반복문 종료
{
if(test_data[i] == ' ') // 띄어쓰기일때 실행
{
if(buf_ptr != buf) // 버퍼에 자료가 들어가 있다면 실행
Push(); // Push()함수를 이용해 test_data를 stack_arr에 넣는다.
while(buf_ptr != buf){ // buf의 데이터와 buf_ptr의 시작주소를 초기화
(*buf_ptr) = NULL;
buf_ptr--;
}
}
else if(test_data[i] < 48) // 유니코드 48아래인 특수기호가 test_data에 들어있을때 실행
Push(test_data[i]); // Push함수를 이용해 연산을 처리한다.
else
{
*buf_ptr = test_data[i]; // test_data의 숫자를 buf_ptr을 이용해 buf에 하나씩 넣는다.
buf_ptr++; // buf_ptr가 가리키는 주소 하나 증가
}
i++; // test_data의 인덱스 하나 증가
}
cout << "입력된 값에 대한 결과 값이 나왔습니다." << endl; // 모든 과정이 나온후 출력된다.
}
void Push()
{
*++stack_ptr = atoi(buf); // buf에 문자로 저장되어있는 숫자를 숫자로 바꾸어 인덱스 하나 증가하여 stack_arr에 넣는다..
}
void Push(char a)
{
if(a == '*') // 입력받은 문자중 '*'라면 스택에서 숫자 두개를 곱한후 두개중 첫번째 숫자 위치에 수를 저장하고 인덱스 하나 감소
*(--stack_ptr) *= *(stack_ptr+1);
else if(a == '+') // 입력받은 문자중 '+'라면 스택에서 숫자 두개를 더한후 두개중 첫번째 숫자 위치에 수를 저장하고 인덱스 하나 감소
*(--stack_ptr) += *(stack_ptr+1);
else if(a == '/') // 입력받은 문자중 '/'라면 스택에서 숫자 두개를 나눈후 두개중 첫번째 숫자 위치에 수를 저장하고 인덱스 하나 감소
*(--stack_ptr) /= *(stack_ptr+1);
else if(a == '-') // 입력받은 문자중 '-'라면 스택에서 숫자 두개를 뺀후 두개중 첫번째 숫자 위치에 수를 저장하고 인덱스 하나 감소
*(--stack_ptr) -= *(stack_ptr+1);
}
void Print_Stack(void)
{
cout << "계산된 결과는 : " << *stack_ptr << endl; // 계산된 결과를 출력하는 코드다.
}
private:
char test_data[100], buf[10]; // 클래스에서 사용 될 변수의 선언
char *buf_ptr;
int stack_arr[100];
int i;
int *stack_ptr;
};
int main()
{
Stack s; // 선언과 동시에 사용자에게 입력을 받는다.
s.Start(); // 입력받은 문자를 이용해 연산
s.Print_Stack(); // 연산후 출력
}
위에 주어진 실습1과 동일한 방식에서 인덱스를 변수로 사용하지 않고, 포인터를 이용해 가리키게 하였다. 추가로 –와 /연산도 추가하였으며 이 또한 포인터를 이용하여 처리하였다.
3. 다음 주어진 postfix 표기의 수식을 입력하여 스택을 사용해서 이진 parse 트리로 표현하고, 이 트리를 postorder 트래버설한 결과를 출력하시오.
#include <iostream>
using namespace std;
typedef struct treeNode{ //tree를 사용하기위해 구조체 노드를 사용하였다.
char data; // 노드에 들어갈 값
struct treeNode *left; // 트리의 왼쪽을 가르키기 위한 값
struct treeNode *right; // 트리의 오른쪽을 가르키기 위한 값
} treeNode;
class Stack // 스택을 사용하기 위한 클래스다.
{
public:
Stack() // 메인함수에서 선언과 동시에 실행 되게 한다.
{
stack_top = -1; // 스택을 사용하기 위해 스택번호의 초기화
i = 0; // 입력받은 데이터 배열에서 사용하기 위한 인덱스 초기화
cout << "테스트 데이터를 입력하세요. [각 문자 중간에는 띄어쓰기를 해야 한다.]" << endl << "테스트 데이터 : "; // 입력받을 데이터 출력
cin.getline(test_data, 100, '\n'); // getline 함수를 사용해 띄어쓰기까지 입력받아서 test_data에 넣는다.
}
void Start() // 입력받은 데이터로 실행하는 함수
{
while(test_data[i] != NULL) // test_data의 모든 단어를 읽은 후 반복문 종료
{
if(test_data[i] == ' '){} // test_data의 값이 ' '일 때 아무런 처리도 하지않고 넘어간다.
else if(test_data[i] < 48) // 유니코드 48아래인 특수기호가 test_data에 들어있을때 실행
push(test_data[i]);
else // testdata에 문자가 들어 있을 때 그 문자를 push를 이용해 스택에 넣는다.
push();
i++; // test_data의 인덱스 1 증가.
}
cout << "입력된 값에 대한 결과 값이 나왔습니다." << endl << "postorder 트래버설한 결과 : "; // 모든 과정이 나온후 출력된다.
postorder(Node_ptr[0]); // postorder함수를 사용해 만들어진 트리를 postdorder트래버설한 결과를 출력한다.
cout << endl;
}
void push() // 문자를 입력받을 경우 트리의 최하위를 차지하게 되므로 바로 노드를 만들어준다.
{
Node_ptr[++stack_top] = new treeNode; // 노드를 만든다.
Node_ptr[stack_top]->data = test_data[i]; // 데이터에 testdata로 부터 입력받은 값을 넣는다.
Node_ptr[stack_top]->left = NULL; // 최하위 노드이므로 NULL 저장.
Node_ptr[stack_top]->right = NULL; // 최하위 노드이므로 NULL 저장.
}
void push(char a) // 문자가 아닌 특수기호를 입력받을 경우 이미 만들어진 노드를 이용해 트리 구조를 만든다.
{
Node_ptr[++stack_top] = new treeNode; // 노드를 생성한다.
Node_ptr[stack_top]->data = test_data[i]; // testdata로부터 입력 받은 값을 넣는다.
Node_ptr[stack_top]->right = Node_ptr[stack_top-1]; // 스택에 들어있는 상위 2개중 먼저 들어있는 노드를 가리킨다.
Node_ptr[stack_top]->left = Node_ptr[stack_top-2]; // 스택에 들어있는 상위 2개중 나중에 들어있는 노드를 가리킨다.
Node_ptr[stack_top-2] = Node_ptr[stack_top]; // 새로만든 인덱스를 사용한 2개의 노드중 앞에 노드위치에 넣는다.
stack_top -= 2; // stack_top 값도 -2해준다.
}
void postorder(treeNode* root) // postorder 트래버설을 실행하는 함수
{
if(root) {
postorder(root->left); // 먼저 왼쪽노드를 방문하고 두번째 노드를 방문하고 자신의 값을 출력한다.
postorder(root->right); // 왼쪽 노드와 오른쪽 노드가 없다면 최하위 노드이므로 바로 출력한다.
cout << root->data << ' ';
}
}
private: // class에서 사용할 변수 선언
char test_data[100];
int stack_top, i;
struct treeNode *Node_ptr[100];
};
void main()
{
Stack s; // 선언과 동시에 사용자로 부터 입력받는다.
s.Start(); // Start함수를 이용해 입력받은 데이터 처리
}
사용자로부터 문자를 입력받아 그것을 트리로 구현하였다. 문자는 자식노드가 없는 하위 노드이고 연산자를 만났을땐 연산자가 상위노드가 되고 문자가 그 연산자의 하위노드가 되는 형식을 취한다. 기본적인 트리구조와 스택구조를 사용하여 스택구조를 이용하여 문자를 받는 동시에 트리를 완성할 수 있도록 처리하였다.
4. 앞 문제에서 만들어진 트리에 대해서 큐를 정의하고, 이것을 사용하여 level order로 트래버설한 결과를 출력하는 프로그램을 완성하고 실습하시오.
#include <iostream>
using namespace std;
typedef struct treeNode{ //tree를 사용하기위해 구조체 노드를 사용하였다.
char data; // 노드에 들어갈 값
struct treeNode *left; // 트리의 왼쪽을 가르키기 위한 값
struct treeNode *right; // 트리의 오른쪽을 가르키기 위한 값
} treeNode;
class Stack // 스택을 사용하기 위한 클래스다.
{
public:
Stack() // 메인함수에서 선언과 동시에 실행 되게 한다.
{
init_queue(); // 큐를 사용하기 위해 큐를 초기화 하는 함수
init_stack(); // 스택을 사용하기 위해 스택을 초기화 하는 함수
cout << "테스트 데이터를 입력하세요. [각 문자 중간에는 띄어쓰기를 해야 한다.]" << endl << "테스트 데이터 : "; // 입력받을 데이터 출력
cin.getline(test_data, 100, '\n'); // getline 함수를 사용해 띄어쓰기까지 입력받아서 test_data에 넣는다.
}
void Start() // 입력받은 데이터로 실행하는 함수
{
while(test_data[i] != NULL) // test_data의 모든 단어를 읽은 후 반복문 종료
{
if(test_data[i] == ' '){} // test_data의 값이 ' '일 때 아무런 처리도 하지않고 넘어간다.
else if(test_data[i] < 48) // 유니코드 48아래인 특수기호가 test_data에 들어있을때 실행
push(test_data[i]);
else // testdata에 문자가 들어 있을 때 그 문자를 push를 이용해 스택에 넣는다.
push();
i++; // test_data의 인덱스 1 증가.
}
cout << "입력된 값에 대한 결과 값이 나왔습니다." << endl; // 모든 과정이 나온후 출력된다.
cout << "postorder : ";
postorder(node_ptr[0]); // postorder함수를 사용해 만들어진 트리를 postdorder트래버설한 결과를 출력한다.
cout << endl;
cout << "levelorder : ";
levelorder(node_ptr[0]); // postorder방식으로 만들어진 함수를 사용해 levelorder트래버설한 결과를 출력한다.
}
void push() // 문자를 입력받을 경우 트리의 최하위를 차지하게 되므로 바로 노드를 만들어준다.
{
node_ptr[++stack_top] = new treeNode; // 노드를 만든다.
node_ptr[stack_top]->data = test_data[i]; // 데이터에 testdata로 부터 입력받은 값을 넣는다.
node_ptr[stack_top]->left = NULL; // 최하위 노드이므로 NULL 저장.
node_ptr[stack_top]->right = NULL; // 최하위 노드이므로 NULL 저장.
}
void push(char a) // 문자가 아닌 특수기호를 입력받을 경우 이미 만들어진 노드를 이용해 트리 구조를 만든다.
{
node_ptr[++stack_top] = new treeNode; // 노드를 생성한다.
node_ptr[stack_top]->data = test_data[i]; // testdata로부터 입력 받은 값을 넣는다.
node_ptr[stack_top]->right = node_ptr[stack_top-1]; // 스택에 들어있는 상위 2개중 먼저 들어있는 노드를 가리킨다.
node_ptr[stack_top]->left = node_ptr[stack_top-2]; // 스택에 들어있는 상위 2개중 나중에 들어있는 노드를 가리킨다.
node_ptr[stack_top-2] = node_ptr[stack_top]; // 새로만든 인덱스를 사용한 2개의 노드중 앞에 노드위치에 넣는다.
stack_top -= 2; // stack_top 값도 -2해준다.
}
void postorder(treeNode* root) // postorder 트래버설을 실행하는 함수
{
if(root) {
postorder(root->left); // 먼저 왼쪽노드를 방문하고 두번째 노드를 방문하고 자신의 값을 출력한다.
postorder(root->right); // 왼쪽 노드와 오른쪽 노드가 없다면 최하위 노드이므로 바로 출력한다.
cout << root->data << ' ';
}
}
void init_stack() // 스택에 사용할 변수를 초기화 하는 함수
{
stack_top = -1;
i = 0;
}
void init_queue() // 큐에서 사용할 변수를 초기화 하는 함수
{
front = rear = 0;
}
void put_queue(treeNode *p) // 큐에 노드를 저장하고 rear를 1증가한다.
{
queue_ptr[rear++] = p;
}
treeNode *get_queue() // 현재위치의 큐를 반납하고 front를 1증가한다.
{
return queue_ptr[front++];
}
void levelorder(treeNode* Q)
{
put_queue(Q); // 시작할때 트리의 최상위 노드를 큐에 넣어준다.
while(notsame()){ // notsame()는 큐의 시작위치와 마지막위치가 같은경우 0을 반납한다.
Q = get_queue(); // get_queue함수로부터 반납받은 노드를 Q에 넣어준다
cout << Q->data << ' '; // 그 노드의 값을 출력한다.
if(Q->left != NULL) // 그리고 왼쪽노드의 자식이있으면 큐에 넣어주고 오른쪽도 자식이 있으면 큐에 넣어준다.
put_queue(Q->left); // 큐에 레벨 별로 저장하고 다음 반복문에서 그 레벨의 값을 출력하고 자식이 있다면 넣어주는
if(Q->right != NULL) // 방식을 반복한다.
put_queue(Q->right);
}
cout << endl;
}
int notsame() // 큐의 시작 위치와 마지막위치가 같으면 0을 반납하여 while을 종료하게 된다.
{
if(queue_ptr[front] == queue_ptr[rear])
return 0;
else
return 1;
}
private: // class에서 사용할 변수 선언
char test_data[100];
int stack_top, i;
struct treeNode *node_ptr[100];
struct treeNode *queue_ptr[100];
int front, rear;
};
void main()
{
Stack s;
s.Start();
}
위에 3번 문제에서 완성한 트리를 이용하고 큐를 정의하여 levelorder 트래버설한 결과를 출력한 것이다. 자신의 레벨에서 출력을 한 후 자식 노드를 큐에 넣어두고 다음 반복문에서 실행하게 함으로써 레벨 별로 출력이 가능하도록 했다.
