[자료구조] C++로 쉽게 풀어쓴 자료구조 : 3장, stack

내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다.

1) 3장. stack

stack의 ADT

데이터 : 후입선출(LIFO)의 접근 방법을 유지하는 요소들의 모음

연산:

- push(x): 주어진 인자 x를 stack의 맨위에 추가한다.

- pop(): stack이 비어있지 않으면 맨 위의 요소를 삭제하고 반환한다.

- isEmpty(): stack이 비어있는지의 유무를 bool값으로 반환

- isFull(): stack이 가득 차있는지의 유무를 bool값으로 반환

- peek(): stack이 비어있지 않으면 맨 위의 요소를 확인해본다.

- size(): stack내의 모든 요소들의 개수를 반환

- display(): stack 내의 모든 요소를 출력

 

이를 활용한 간단한 Stack을 구현하였다. list를 활용한 구성이다.

 

ArrayStack.h

#pragma once
#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;
const int MAX_STACK_SIZE = 20;

inline void error(const char* message) {
	printf("%s\n", message);
	exit(1);
}

template <typename T>
class ArrayStack
{
	int top;
	T data[MAX_STACK_SIZE];
public:
	ArrayStack() { top = -1; } // stack constructor
	~ArrayStack() {}
	bool isEmpty() { return top == -1; }
	bool isFull() { return top == MAX_STACK_SIZE - 1; }
	void push(const T& e);
	T pop();
	T peek();
	void display();
};

template <typename T>
void ArrayStack<T>::push(const T& e)
{
	if (isFull()) error("스택이 가득참.");
	data[++top] = e;
}

template <typename T>
T ArrayStack<T>::pop()
{
	if (isEmpty()) error("스택이 비어있습니다.");
	return data[top--];
}

template <typename T>
T ArrayStack<T>::peek()
{
	if (isEmpty()) error("스택이 비어있습니다.");
	return data[top];
}

template <typename T>
void ArrayStack<T>::display()
{
	printf("[스택에 들어있는 원소의 수 = %2d] : ", top + 1);
	for (int i = 0; i <= top; i++)
		cout << "<" << data[i] << "> ";
	printf("\n");
}

 

main.cpp

#include "ArrayStack.h"

int main()
{
	ArrayStack<float> stack;
	for (float i = 0.5; i < 10; i++) {
		stack.push(i);
	}

	stack.display();
	stack.pop();
	stack.pop();
	stack.display();

	cout << "peek: " << stack.peek();
               
	return 0;
}

 

결과는 다음과 같이 나왔다.

아주 간단한 구조라 금방 이해할수 있다.

 

괄호 검사 프로그램

이 예제는 제가 자료구조를 공부할때 자주 들어가는 GeeksforGeeks에도 있는 내용이라 혼합하여 공부하였습니다.

 

 

바로 직전 예제를 변경하여 괄호 검사 프로그램을 구현해 보자. 우선 괄호 검사 프로그램의 logic을 생각해보면

- 조건 1 : 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다.

- 조건 2 : 같은 타입의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.

- 조건 3 : 서로 다른 타입의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차하면 안된다.

출처 -  GeeksforGeeks

소스코드는 위의 ArrayStack.h를 재사용 합니다. template화 시켰기 때문에 char type에 대해서도 적용시킬 수 있습니다.

 

main.cpp

#include "ArrayStack.h"
using namespace std;

bool checkMatching(const char* filename) {
	FILE* fp = fopen(filename, "r"); // 읽기모드로 파일 오픈
	if (fp == NULL) error("파일이 없다!");

	int nLine = 1; // 읽은 라인의 수
	int nChar = 0; // 읽은 문자 개수
	ArrayStack<char> stack;
	char ch;

	while ((ch = getc(fp)) != EOF) {
		if (ch == '\n') nLine++;
		nChar++;
		if (ch == '[' || ch == '{' || ch == '(')
			stack.push(ch);
		else if (ch == ']' || ch == '}' || ch == ')') {
			switch (ch) {
				char temp;
			case ']':
				temp = stack.pop();
				if (temp == '}' || temp == ')')
					return false;
				break;
			case '}':
				temp = stack.pop();
				if (temp == ']' || temp == ')')
					return false;
				break;
			case ')':
				temp = stack.pop();
				if (temp == ']' || temp == '}')
					return false;
				break;
			}
		}
	}
	fclose(fp);
	cout << "파일 검사 결과" << endl;
	if (!stack.isEmpty())
		cout << "문제발견!(라인수 = " << nLine << ", 문자수 = " << nChar << ")" << endl;
	else
		cout << "정상" << endl;
	return stack.isEmpty();
}

int main()
{
	checkMatching("ArrayStack.h");
               
	return 0;
}

 

ArrayStack.h를 대상으로 파일을 열어서 괄호 검사를 수행하였습니다. 결과로는 정상이라고 출력되었습니다.

 

수식의 계산

컴퓨터는 사람과 달리 주로 후위 표기법을 사용한다고 한다.

- 이는 괄호를 사용하지 않고도 계산의 순서를 알수 있다.

- 식 자체에 이미 우선순위가 포함되어 있다.

- 수식을 읽으면서 바로 계산할 수 있다.

 

이번 수식 계산 또한 위의 ArrayStack.h를 사용하면 된다. 다시한번 template의 위력을 몸소 느끼고 있다.

 

한가지 문제가 있다면, 만약 7 - 3.4 와 같은 식이 있다면 상황이 복잡해진다. 후위 표기법을 이용하면 7을 stack 에 담고 3.4가 아닌 3을 stack에담을 것 이다. 한 문자씩 받아서 읽어들이기 때문에 3을 하나의 문자로 인식하기 때문이다. 따라서 문자를 하나씩 읽어오는데 그 문자가 숫자라면 ungetc로 다시 버퍼에 되돌리고, scanf()로 한번에 3.5를 읽어온다.

 

#include "ArrayStack.h"
using namespace std;

double calcPostfixExpt(FILE* fp = stdin) {
	char c;
	ArrayStack<double> stack;

	while ((c = getc(fp)) != '\n') {
		if (c == '+' || c == '-' || c == '*' || c == '/') {
			double temp2 = stack.pop();
			double temp1 = stack.pop();
			switch (c) {
			case '+':
				stack.push(temp1 + temp2);
				break;
			case '-':
				stack.push(temp1 - temp2);
				break;
			case '*':
				stack.push(temp1 * temp2);
				break;
			case '/':
				stack.push(temp1 / temp2);
				break;
			}
		}
		else if (c >= '0' && c <= '9') {
			ungetc(c, fp); // 입력버퍼로 되돌림
			double value;
			fscanf(fp, "%lf", &value); // 다시 읽음
			stack.push(value); // 읽은 값 stack에 저장
		}
	}
	return stack.pop();
}

int main()
{
	cout << "수식 입력 (후위표기)=> ";
	double res = calcPostfixExpt();
	cout << "계산 결과 =>" << res << endl;
               
	return 0;
}

 

결과는 다음과 같다.

결과가 정상적으로 나오고 있다.

중위 표기 수식의 후위 표기 변환

지난 2학기때 열혈 자료구조를 이미 공부한적이 있다. 그 책에서도 봤었던 문제이기에 반가운 동시에 풀이가 명확히 기억나지 않아 책을 둘다 살펴보았다. 블로그에는 간단하게 요약하겠다.

 

1) 피연산자는 그냥 옮긴다.

2) 연산자는 stack으로 옮긴다.

3) 다른 연산자가 쟁반에 이미 있다면 우선순위를 비교하여 처리한다.

3.1) 기존의 stack에 들어있는 연산자가 새로 삽입되는 연산자보다 우선순위가 높거나 같다면 출력한다.

4) 마지막까지 쟁반에 남아있는 연산자들은 하나씩 꺼내서 옮긴다.