■ stack의 응용 : 계산기 프로그램
$$ 1 + (2+3) / 4 $$
스택을 사용하여 계산기를 구현해 보자. 계산기는 아래의 두 가지를 고려해서 연산을 진행할 수 있어야 한다.
- 소괄호를 파악하여 그 부분을 먼저 계산한다.
- 연산자의 우선순위를 근거로 연산의 순위를 결정한다.
물론 스택만 사용해서 구현할 수 있는것은 아니고 별도의 알고리즘이 존재하며 이를 활용해야 계산기 프로그램을 만들 수 있다.
▶ 전위(prefix), 중위(infix), 후위(postfix) 표기법
먼저 수식을 이루는 피연산자가 한자리 숫자로만 이뤄진다고 가정해 보자.
전위, 중위, 후위 표기법은 수학식에서 연산자(operator)를 피연산자(operand) 들 사이 어디에 두느냐에 따른 표기 방식의 차이를 말한다.
중위 표기법 (Infix Notation)
$$ 5+2/7 $$
우리에게 가장 익숙한 형태이다. 사람이 읽고 쓰기 편하지만 계산 순서를 괄호로 명시해야 한다.
- 연산자 + 가 피연산자 사이에 위치
전위 표기법 (Prefix Notation)
$$ +\ 5\ /\ 2\ 7 $$
전위 표기법은 연산자가 피연산자 앞에 오는 방식이다. 오른쪽에서 왼쪽으로 읽으며 계산해야 한다.
- 괄호가 없어도 계산 순서가 명확하다.
전위 표기법 계산 예시)
| 단계 | 읽은 연산자 | 상태 |
| 1 | 7 | [7] |
| 2 | 2 | [7, 2] |
| 3 | / | [(2/7)] |
| 4 | 5 | [(2/7), 5] |
| 5 | + | [5 + (2/7)] |
후위 표기법 (Postfix Notation)
$$ 5\ 2\ 7\ /\ + $$
후위 표기법은 연산자가 피 연산자 뒤에 오는 방식이다.
괄호가 전혀 필요 없고, 스택으로 계산하기 가장 쉬운 형태이다.
만약 연산의 우선순위를 모르는 사람에게 중위 표기법을 보여준다면, 연산의 우선순위를 파악하지 못한다.
하지만 전위, 후위 연산에는 연산의 우선순서에 대한 정보가 들어와 있다.
$$ 5 \ 2 \ 7 \ \mathrm{op1} \ \mathrm{op2} $$
[후위 표기법 예시]
위와 같이 op1과 op2라는 연산자가 있을 때, 연산자가 자리한 위치만 보고서도 다음과 같은 판단이 가능하다.
- op1이 먼저 등장했으니, op1을 먼저 연산하고 op2를 연산한다!
전위 표기법의 수식이나 후위 표기법의 수식은 연산자의 배치순서에 따라서 연산순서가 결정되기 때문에, 이 두 표기법의 수식을 계산하기 위해서 연산자의 우선순위를 알 필요도, 소괄호도 삽입되지 않는다.
물론 사용자에게 후위 표기법이나 전위 표기법으로 계산식을 입력받을 순 없으니, 중위 표기법을 후위 표기법으로 바꾸는 방법에 대해 알아보자.
■ 중위 표기법 → 후위 표기법 (소괄호 고려 X)
- 중위 표기법의 수식을 후위 표기법의 수식으로 바꾼다.
- 후위 표기법으로 바뀐 수식을 계산하여 그 결과를 얻는다.
각각의 과정은 별도의 알고리즘이 필요하다. 먼저 중위 표기법을 후위 표기법으로 변환해 보자.
위의 상황에서 왼쪽에 있는 5가 저장된 피연산자 블록부터 시작하여, 마지막 블록까지 일관된 방식으로 처리를 진행한다.
첫 번째 숫자는 5이므로, 변환된 수식이 놓일 위치에 가져다 놓는다.
- 숫자는 변환된 수식이 놓일 위치에 가져다 놓는다.
연산자가 등장하면 일단 쟁반으로 옮긴다. 다음 칸에는 피연산자가 있으므로 변환된 수식이 위치할 자리로 옮긴다.
/ 연산자를 쟁반으로 옮긴다. 다만 현재 쟁반에 연산자가 있는 관계로 두 연산자 간의 우선순위를 비교해야 한다.
▶ 쟁반에 위치한 연산자의 우선순위가 높다면
- 쟁반에 위치한 연산자를 꺼내서 변환된 수식이 위치할 자리로 옮긴다.
- 새 연산자는 쟁반으로 옮긴다.
▶ 쟁반에 위치한 연산자의 우선순위가 낮다면
- 쟁반에 위치한 연산자의 위에 새 연산자를 쌓는다.
쟁반에 위치한 연산자는 +이고, 새 연산자는 /이니, 위와 같이 연산자를 쌓으면 된다.
- 우선순위가 높은 연산자는 낮은 연산자 위에 올라서서 먼저 위치하지 못하게 만든다고 기억하자.
중위 표기법에 들어있는 상자를 모두 비웠으니, 쟁반 위에 있는 연산자를 수식이 위치할 자리에 넣어주면 된다.
중위 표기법을 후위 표기법으로 변경하는 방법에 대해 정리하자면 아래와 같다.
- 피연산자는 그냥 옮긴다.
- 연산자는 쟁반으로 옮긴다.
- 연산자가 쟁반에 있다면 우선순위를 비교하여 처리방법을 결정한다.
- 마지막까지 쟁반에 남아 있는 연산자들은 하나씩 꺼내서 옮긴다.
동일한 우선순위의 연산자가 이미 존재하는 경우는, +의 연산 순위가 높다고 가정하고 일을 진행해야 한다.
- 사칙연산의 경우 연산자의 우선순위가 동일하다면, 먼저 등장한 연산자를 먼저 진행한다.
- 따라서 기존 쟁반에 있던 연산자를 옮긴 뒤, 다음 연산자를 위치시킨다.
다른 두 연산자가 쌓여있는 상태에서 맨 위에 있는 연산자보다 우선순위가 낮은 연산자가 들어오는 경우이다.
이 경우 쌓여있는 연산자를 모두 옮기고 난 뒤 연산자를 쟁반에 위치시킨다.
■ 중위 표기법 → 후위 표기법 (소괄호 고려 O)
$$ (1+2*3)/4 $$
후위 표기법의 수식에서는 먼저 연산이 이뤄져야 하는 연산자가 뒤에 연산이 이뤄지는 연산자보다 앞에 위치해야 한다.
즉, / 연산자보다 +, * 연산이 먼저 쟁반에서 빠져나가야 한다.
후위 표기법은 소괄호의 정보를 반영해서 배치하기 때문에 후위 표기법으로 변환하면서 소괄호는 소멸된다.
- 소괄호도 연산자이므로 쟁반에 올린다.
( 연산자는 + 연산자가 들어왔다고 해서 쟁반 밖으로 나가면 안 된다. ) 연산자가 들어올 때까지 쟁반에 남아서 경계를 구분해야 한다.
- 따라서, ( 연산자는 사칙연산들보다 연산자 우선순위가 낮다고 간주한다.
숫자 2가 변환된 수식의 자리로 이동하고, * 연산자를 쟁반으로 옮긴다.
- 만약 + 연산자보다 우선순위가 낮은 연산자가 등장했다면, +연산자를 변환된 수식의 자리로 먼저 이동시켜야 한다.
숫자 3을 옮기고 난 뒤, ) 연산자가 쟁반에 옮겨지므로 남아있던 연산자를 꺼내어 변환된 수식의 자리로 옮긴다.
/연산과 숫자 4를 처리하면 최종적으로 위와 같이 후위 표기법으로 변환된다.
■ 중위 → 후위 표기법 프로그램 구현
#pragma once
#include <string>
using namespace std;
// 중위 -> 후위 표기법 변환 함수
string InfixToPostfix(const string& infix);
// 연산자 우선순위 반환 함수
int GetOpePrece(char op);
// 연산자 우선순위 비교 함수
int CompareOpPrec(char op1, char op2);
[InfixToPostfix.h]
중위 표기법의 수식을 저장한 문자열을 인자로 전달하면, 후위 표기법으로 바뀐 수식을 반환한다.
// 연산자 우선순위 반환
int GetOpePrece(char op)
{
switch (op)
{
case '*':
case '/':
return 5;
case '+':
case '-':
return 3;
case '(':
return 1;
default:
return -1;
}
}
위 함수는 인자로 전달된 연산자의 우선순위 정보를 정수의 형태로 반환한다.
- ‘(’ 연산은 ‘)’연산자가 등장할 때까지 쟁반 위에 남아 있어야 하므로 다른 사칙 연산자들보다 우선순위를 낮게 설정한다.
int CompareOpPrec(char op1, char op2)
{
int prec1 = GetOpePrece(op1);
int prec2 = GetOpePrece(op2);
// op1의 우선순위가 더 높다면
if (prec1 > prec2) return 1;
// op2의 우선순위가 더 높다면
if (prec1 < prec2) return -1;
// 우선순위가 같다면
return 0;
}
주석에서 언급하듯이, 첫 번째 인자로 전달된 연산자의 우선순위가 높다면 1, 두 번째 인자로 전달된 연산자가 더 높다면 -1, 같다면 0을 반환한다.
다음으론 핵심이 되는 중위 → 후위 표기법 변환 함수인데, 위에서 설명한 과정을 그대로 코드로 옮긴 것이니 크게 어려운 것은 없다.
// 쟁반
Stack stack;
string InfixToPostfix(const string& infix)
{
string postfix;
LInit(&stack);
for(char ch : infix)
{
// 피연산자(숫자)인 경우
if(isdigit(ch) != 0)
{
//후위 연산자에 저장
postfix += ch;
}
else
{
switch (ch)
{
// 여는 괄호인 경우
case '(':
LPush(&stack, ch);
break;
// 닫는 괄호인 경우
case ')':
while(true)
{
char pop = LPop(&stack);
// 여는 괄호가 나올 때까지 후위 연산자에 저장
if(pop == '(')
break;
postfix += pop;
}
break;
// 나머지 연산자의 경우
case '+': case '-':
case '*': case '/':
// 스택이 비어있지 않고, 스택의 top 연산자의 우선순위가 현재 연산자보다
// 높거나 같다면
while(LIsEmpty(&stack) == false &&
CompareOpPrec(LPeek(&stack), ch) >= 0)
{
postfix += LPop(&stack);
}
// 아니라면 연산자를 스택에 저장
LPush(&stack, ch);
break;
}
}
}
// 남아있는 연산을 모두 후위 연산자에 저장
while (LIsEmpty(&stack) == false)
{
postfix += LPop(&stack);
}
return postfix;
}
[InfixToPostfix()]
전역 변수로 선언된 stack이 앞서 봤던 쟁반 역할을 하고, string으로 선언된 postfix가 변환된 수식을 저장할 변수(후위 표기법)가 된다.
🤔중위 표기법을 하나씩 확인
for(char ch : infix)
{
// 피연산자(숫자)인 경우
if(isdigit(ch) != 0)
{
//후위 연산자에 저장
postfix += ch;
}
}
infix에 저장된 중위 표기법을 한 글자씩 확인한다. 이때, 문자가 숫자(피연산자)라면 후위 표기식에 그대로 저장한다.
- isdigit() 함수는 <cctype> 헤더에 포함된 표준 라이브러리 함수로, 문자가 숫자로 변환이 가능(’ 0~9’)하면 0이 아닌 값을 반환하고 그렇지 않다면 0을 반환한다.
🤔 괄호 확인
else
{
switch (ch)
{
// 여는 괄호인 경우
case '(':
LPush(&stack, ch);
break;
// 닫는 괄호인 경우
case ')':
while(true)
{
char pop = LPop(&stack);
// 여는 괄호가 나올 때까지 후위 연산자에 저장
if(pop == '(')
break;
postfix += pop;
}
break;
}
}
저장된 문자가 여는 괄호라면, 스택에 괄호를 저장한다. 중요한 점은 닫는 괄호를 만났을 때이다.
닫는 괄호가 나오면 여는 괄호가 나올 때까지 스택(쟁반)에 저장된 연산자를 모두 후위 연산자로 보내야 한다.
- 여는 괄호 역시 스택에서 제거되어야 하므로 pop 한 이후에 반복문을 종료시킨다.
🤔 사칙 연산 처리
// 나머지 연산자의 경우
case '+': case '-':
case '*': case '/':
// 스택이 비어있지 않고, 스택의 top 연산자의 우선순위가 현재 연산자보다
// 높거나 같다면
while(LIsEmpty(&stack) == false &&
CompareOpPrec(LPeek(&stack), ch) >= 0)
{
postfix += LPop(&stack);
}
// 아니라면 연산자를 스택에 저장
LPush(&stack, ch);
break;
현재 연산자가 사칙 연산자라면, 먼저 스택에 가장 마지막으로 저장된 연산자와 우선순위를 비교해야 한다.
스택에 저장된 연산자의 우선순위가 더 높다면 이를 후위 표기법으로 옮겨야 하므로, while문을 사용해 위와 같이 처리하였다.
- 현재 연산자의 우선순위가 더 높다면 스택에 저장한다.
🤔 쟁반(스택) 비우기
// 남아있는 연산을 모두 후위 연산자에 저장
while (LIsEmpty(&stack) == false)
{
postfix += LPop(&stack);
}
return postfix;
int main()
{
string infixExp = "(4+8)*(6-5)/((3-2)*(2+2))";
string postfixExp = InfixToPostfix(infixExp);
cout << postfixExp << endl;
return 0;
}
위 처리가 모두 다 끝났다면, 스택에 남아있는 연산자를 차례대로 옮긴 뒤 후위 표기법 수식을 반환한다.
■ 후위 표기법 계산
이제 변환된 후위 표기법의 수식을 계산하여 그 결과를 얻으면 된다. 그러기 위해선 후위 표기법의 계산 방식을 알 필요가 있다.
$$ 3+2*4 \\ 3\ 2\ 4\ * \ + $$
[중위 → 후위 표기법]
후위 표기법에선 먼저 진행되야 하는 연산이 앞에 위치한다. 또한 후위 표기법의 수식에서는 앞에 등장하는 두 개의 숫자가 피연산자이다.
곱셈의 연산이 먼저 진행되고, 곱셈의 피연산자는 2와 4이다. 연산을 하고 난 뒤 결과는 그 자리를 대신하게 된다.
- 이러한 계산 방식을 토대로 후위 표기법을 계산하는 프로그램을 작성해 보자.
1. 후위 표기법 계산 프로그램 작성
후위 표기법 계산 역시 스택을 사용하면 매우 쉽게 구현이 가능하다. 계산 규칙은 아래와 같다.
- 피연산자는 무조건 스택으로 옮긴다.
- 연산자를 만나면 스택에서 2개의 피연산자를 꺼내서 계산한다.
- 연산의 결과는 다시 스택에 저장한다.
int CalculatePostfix(const string& postfix)
{
LinkedStack<int> stack;
for(char ch : postfix)
{
// 피연산자(숫자)인 경우
if(isdigit(ch) != 0)
{
stack.Push(ch - '0');
}
else
{
// 두 개의 피연산자를 꺼냄
char op2 = stack.Pop();
char op1 = stack.Pop();
switch (ch)
{
case '+':
stack.Push(op1 + op2);
break;
case '-':
stack.Push(op1 - op2);
break;
case '*':
stack.Push(op1 * op2);
break;
case '/':
stack.Push(op1 / op2);
break;
}
}
}
return stack.Pop();
}
[후위 표기식 계산 함수]
앞서 설명한 후위 표기식 계산 과정을 그대로 코드로 옮겨 적었다.
현재 연산자가 피연산자(숫자)라면 스택에 저장하고, 연산자라면 스택에서 2개의 피연산자를 꺼내 계산한 뒤, 다시 스택에 저장한다.
스택에서 꺼낼 때는 가장 나중에 들어간 값이 먼저 나온다. 따라서 두 개의 피연산자를 꺼낼 때에는,
// 두 번째 피연산자
char op2 = stack.Pop();
// 첫 번째 피연산자
char op1 = stack.Pop();
처럼 꺼내야 한다.
즉, 식에서 먼저 등장한 피연산자가 op1, 나중에 등장한 피연산자가 op2가 되어야 올바른 순서대로 계산된다.
#include<iostream>
#include "InfixToPostfix.h"
using namespace std;
int main()
{
string infixExp = "(4+8)*(6-5)/((3-2)*(2+2))";
string postfixExp = InfixToPostfix(infixExp);
cout << postfixExp << endl;
cout << CalculatePostfix(postfixExp) << endl;
return 0;
}
■ 연결 리스트 기반 stack 개선
#pragma once
#include <iostream>
template <typename T>
struct Node
{
T data = 0;
Node<T>* next = nullptr;
};
template <typename T>
class LinkedStack
{
public:
LinkedStack()
{
head = new Node<T>();
}
~LinkedStack()
{
if (head->next != nullptr)
{
auto cur = head->next;
while (cur != nullptr)
{
auto next = cur->next;
delete cur;
cur = next;
}
}
delete head;
}
void Push(T data)
{
if (head == nullptr)
{
return;
}
auto newNode = new Node<T>();
newNode->data = data;
// 기존 노드 연결
newNode->next = head->next;
// 헤드 노드와 새 노드 연결
head->next = newNode;
}
T Pop()
{
if (head == nullptr || IsEmpty() == true)
{
std::cout << "스택이 존재하지 않거나 꺼낼 데이터가 없습니다!" << std::endl;
return -1;
}
auto result = head->next->data;
auto delNode = head->next;
head->next = delNode->next;
delete delNode;
return result;
}
T Peek()
{
if (head == nullptr || IsEmpty())
{
std::cout << "스택이 존재하지 않거나 꺼낼 데이터가 없습니다!" << std::endl;
return -1;
}
return head->next->data;
}
bool IsEmpty()
{
return head->next == nullptr;
}
private:
Node<T>* head = nullptr;
};
[ListStack을 템플릿 클래스로 변경]
중위 → 후위 표기식으로 변환할 땐 stack에 저장될 데이터가 char 타입이고, 후위 표기식을 계산할 땐 stack을 int 타입으로 사용한다.
따라서 형식 매개변수를 사용해 유연하게 대처할 수 있도록 코드를 변경하였다.
'C++ > 자료구조' 카테고리의 다른 글
| [C++, 자료구조] 스택(Stack) (1) | 2025.11.11 |
|---|---|
| [C++, 자료구조] 양방향 연결 리스트(Doubly Linked List) (0) | 2025.10.23 |
| [C++, 자료구조] 단일 연결 리스트(Singly Linked List) (0) | 2025.10.23 |
| [C++, 자료구조] 순차 리스트(ArrayList)와 추상 자료형 (0) | 2025.10.23 |