bdfgdfg

스택 - 6장 본문

CS/자료구조 알고리즘

스택 - 6장

marmelo12 2021. 7. 3. 21:52
반응형

스택

LIFO(Last In First Out). 후입 선출방식의 자료구조이다.

 

앞서 재귀함수를 공부할 때도 자기 자신을 호출하면서 빠져나올 땐 역순으로 빠져나오는 스택의 방식.

 

간단하게 설명하면 쌓여있는 상자를 생각하면 쉽다. 상자를 밑에서부터 위로 하나하나 차곡차곡 쌓고 뺄 때는 위에서부터 아래로 하나하나씩 뺀다. 이것이 스택의 구조

 

간단하니 바로 코드를 통해 확인한다.

#pragma once
template<typename T>
class Stack
{
public:
	Stack();
	~Stack();
	inline T GetTop() const;
	inline bool Push(const T& item);
	inline bool Pop();
	inline bool Empty() const;
private:
	enum { MAX = 100 };
	int m_top; // 스택의 데이터가 저장된 최상위인덱스를 가리킨다.
	T* m_arr;
	int m_size;
};

중요한것은 스택은 거의 대부분 배열 기반으로 구현이 돼있으며 배열의 최상위 데이터를 top멤버 변수가 가리키고 있다.

(다른 인덱스 접근 불가능)

 

cpp코드

template<typename T>
Stack<T>::Stack() : m_size(0), m_top(-1),m_arr(new T[MAX]())
{
	
}

template<typename T>
Stack<T>::~Stack()
{
	delete[] m_arr;
}
template<typename T>
T Stack<T>::GetTop() const
{
	return m_arr[m_top];
}
template<typename T>
bool Stack<T>::Push(const T& item)
{
	++m_top;
	if (m_top >= MAX)
	{
		m_top = MAX - 1;
		return false;
	}
	m_arr[m_top] = item;
	++m_size;
	return true;
}
template<typename T>
bool Stack<T>::Pop()
{
	--m_size;
	--m_top;
	if (m_top < 0)
	{
		m_top = -1;
		return false;
	}
	return true;
}
template<typename T>
bool Stack<T>::Empty() const
{
	return (m_size != 0) ? true : false;
}

 

스택을 이용한 계산기 프로그램 구현

스택을 이용한 계산기 프로그램을 구현하기전 세 가지 수식 표기법을 알아야 한다.

 

1. 중위(infix) 표기법 - 5 + 2 / 7

2. 전위(prefix) 표기법 - + 5 / 2 7

3. 후위(postfix) 표기법 - 5 2 7 / +

(참고로 이진트리의 순회 방법에서도 중위 순회, 전위 순회, 후위 순회라는 말이 반복해서 나온다)

 

우리가 흔히 사용하는 표기법은 중위 표기법이다.

이 중위 표기법은 우리가 나눗셈 연산이 덧셈보다 우선순위가 더 높다는 것을 알고 있기에 연산 순서에 대한 정보를 알 수 있다.

 

하지만 전위 표기법과 후위 표기법은 배치 순서를 근거로 한 연산 순서의 정보가 담기기 때문에 이를 대상으로 한 연산에는 연산자의 우선순위가 필요하지 않다.

(소괄호 포함)

그렇기에 후위 표기법을 통해 계산기 프로그램을 구현하기 전에 후위 표기법 수식으로 바꾸는 과정을 본다.

 

출처 - 윤성우 열혈자료구조

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

2. 연산자는 스택에 담는다.

3. 연산자가 스택에 있다면 우선순위를 비교하여 처리방법을 결정한다

-> 스택에 +연산자가 있고 그 뒤에 *연산자가 들어오면 그대로 쌓는다. 만약 *연산자가 존재했고 우선순위가 더 낮은 +연산자가 들어오면 스택에 위치한 연산자를 변환된 수식이 위치할 자리로 옮긴다.

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

 

하지만 몇 가지 위의 사항이 지켜지지 않는 예외사항이 존재한다.

 

1. 우선순위가 같은 경우. 

-> 즉 스택에 +연산자가 올려져 있는데 그 뒤에 -연산자가 들어오는 경우. 두 연산자의 우선순위는 같다.

-> 이럴 경우 +연산자를 변환된 수식으로 옮기고 -연산자를 스택에 담는다.

-> 실제 사칙연산의 경우에도 연산자의 우선순위가 동일하면 먼저 등장한(왼쪽) 연산자를 먼저 진행한다.

 

2. 둘 이상의 연산자가 쌓여있는 경우.

-> +연산자가 밑에 / 연산자가 그 위에 쌓인 스택이 존재할 때, - 연산자가 들어올 경우.

-> 이 경우에는 / 연산자와 + 연산자를 변환된 수식으로 옮기고 - 연산자를 스택에 담는다.

-> 왜냐하면 둘 다 - 연산자보다 먼저 진행되어야 하는 연산자들이기 때문.

 

3. 소괄호 고려

-> ( 연산자는 ) 연산자가 들어오기 전까지 스택에 남아서 소괄호의 경계를 구분한다.

-> 그렇기에 다른 연산자들보다 우선순위가 낮다.

-> 소괄호의 끝을 의미하는 ) 연산자는 ( 연산자 이후에 쌓인 연산자들을 변환된 수식의 자리로 옮긴다.

-> ) 연산자는 소괄호의 끝을 의미하므로 스택에 담지 않고 하나의 끝이라는 메시지로 간주한다.

 

위의 사항을 모두 지킨다면 밑의

( ( 4 + 2 ) / 4 ) - ( 3 + 2 / ( 7 * 5 ) )와 같은 수식도 변환이 가능하다.

 

이제 중위 표기법을 후위 표기법으로 바꾸는 코드를 구현해본다.

 

#pragma once
class Calculator
{
public:
	static void ConvToRPNExp(char exp[]);
private:
	static int GetOpPrec(char op);
	static int WhoPrecOp(char op1, char op2);
};

 

 

개체를 생성할 필요가없기에 정적멤버함수로 만들었다. ( 클래스명::함수로 바로 접근가능)

 

private영역에 선언된 정적멤버함수는 연산자의 우선순위 비교와 연산자 우선순위 값을 얻어오는 함수들이다.

 

public영역에 선언된 정적멤버함수는 위의 두 함수를 이용해 후위표기식으로 변환한다.

 

cpp코드

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <cstring>
#include "Calculator.h"
#include "Stack.h"

int Calculator::WhoPrecOp(char op1, char op2)
{
	int op1Prec = GetOpPrec(op1);
	int op2Prec = GetOpPrec(op2);

	if (op1Prec > op2Prec)
		return 1;
	else if (op1Prec < op2Prec)
		return -1;
	else // 같다면
		return 0;
}

int Calculator::GetOpPrec(char op)
{
	switch (op)
	{
	case '*':
	case '/':
		return 5;
	case '+':
	case '-':
		return 3;
	case '(':
		return 1;
	default:
		return -1; // 등록되지 않은 연산자
	}
	
}

void Calculator::ConvToRPNExp(char exp[])
{
	Stack<char> stack;
	int expLen = strlen(exp);
	char* convExp = new char[expLen + 1]();

	int i, idx = 0;
	char tok, popOp;
	memset(convExp, 0, expLen + 1);

	for (i = 0; i < expLen; ++i)
	{
		tok = exp[i]; // 하나씩 가져온다.
		if (std::isdigit(tok))
		{
			// 피연산자라면 바로 담는다.
			convExp[idx++] = tok;
		}
		else // 연산자라면 비교.
		{
			switch (tok)
			{
			case '(':
				stack.Push(tok);
				break;
			case ')': // 소괄호 종료 메시지
				while (true) // (를 만나기전까지 계속뽑는다.
				{
					popOp = stack.GetTop();
					stack.Pop();
					if (popOp == '(')
						break;
					convExp[idx++] = popOp;
				}
				break;
			case '+': case '-':
			case '*': case '/':
				while (!stack.Empty() && WhoPrecOp(stack.GetTop(), tok) >= 0)
				{ // 스택의 담긴연산자와 넣을려는 연산자를 비교
				  // 스택에 담긴 연산자의 우선순위가 더 크다면 스택에서 꺼낸다.
					convExp[idx++] = stack.GetTop();
					stack.Pop();
				}
				stack.Push(tok);
				break;
			}
		
		}
	}
	// 배열에담긴 문자를 다 옮긴 후.
	
	while (!stack.Empty()) // 스택에 연산자가 남아있다면
	{
		convExp[idx++] = stack.GetTop();
		stack.Pop();
	}

	strcpy(exp, convExp);
	delete[] convExp;

}

 

이제 중위 표기법을 후위 표기법으로 변환한 수식을 계산하는 프로그램을 구현한다.

 

계산기 프로그램의 규칙은 다음과 같다.

 

1. 피연산자는 무조건 스택으로 옮긴다. 

2. 연산자를 만나면 스택에서 두 개의 피연산자를 꺼내 계산을 한다.

3. 계산결과는 다시 스택에 넣는다.

 

예를들어 324*+ 라는 후위 표기식을 위의 규칙대로 적용해보면

 

324까지 모두 스택에 쌓는다 순서는 3->2->4

 

그리고 *연산자를 만나면 4와 2를 꺼내 계산을 한다.

이 때 4 * 2가 아닌 2 * 4로 계산을 한다.

즉 먼저 꺼낸 피연산자는 오른쪽 피연산자. 나중에 꺼낸 피연산자는 왼쪽 피연산자.

 

그리고 계산한 결과는 다시 스택에 집어넣는다. 3->8순으로 다시 쌓임.

그리고 + 연산을 만나 3 + 8을 수행한다.

 

이제 후위 표기식의 수식을 계산하는 코드를 확인해보자.

#pragma once
class Calculator
{
public:
	static void ConvToRPNExp(char exp[]);
	static int EvalRPNExp(char exp[]); //추가. 후위표기법의 수식을 계산
private:
	static int GetOpPrec(char op);
	static int WhoPrecOp(char op1, char op2);
};

 

cpp코드.

int Calculator::EvalRPNExp(char exp[])
{
	Stack<char> stack;
	int expLen = strlen(exp);
	int i,a,b;
	char tok, op1, op2;

	for (i = 0; i < expLen; ++i)
	{
		tok = exp[i]; // 하나 꺼낸다.
		if (std::isdigit(tok)) // 피연산자라면 스택에 담는다.
		{
			stack.Push(tok);
		}
		else
		{
			op2 = stack.GetTop();
			stack.Pop();
			op1 = stack.GetTop();
			stack.Pop();
			a = op1 - '0';
			b = op2 - '0';
			switch (tok)
			{
			case '*':
				a *= b;
				stack.Push(a + '0');
				break;
			case '/':
				a /= b;
				stack.Push(a + '0');
				break;
			case '+':
				a += b;
				stack.Push(a + '0');
				break;
			case '-':
				a -= b;
				stack.Push(a + '0');
				break;
			default:
				return -1;
			}
		}
	}

	int retData = stack.GetTop() - '0';
	stack.Pop();
	return retData;
	
}

 

 

참고로

숫자->문자로 바꿀때 정수형변수 + '0'

문자->숫자로 바꿀때 정수형변수 - '0'.

 

결과.

 

반응형

'CS > 자료구조 알고리즘' 카테고리의 다른 글

트리의 개념과 설명 - 8장  (0) 2021.07.04
큐(Queue)와 덱(Deque) - 7장  (0) 2021.07.03
연결리스트 - 원형, 양방향(이중) 5장  (0) 2021.07.03
연결리스트 - 3장,4장  (0) 2021.07.03
재귀함수 - 2장  (1) 2021.07.02
Comments