bdfgdfg
스택 - 6장 본문
스택
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 |
