1. 이론
작년쯤에 공부했던 알고리즘을 교내 수업에서 만났고, 내가 얼마나 공부를 부실하게 했는지도 알게 되었다. 대충 이론만 기억나는 상태여서 처음부터 다시 손으로 쓰면서 공부했다. 많은 책과 인터넷 자료들을 참고 하였으며 최대한 예외를 예상하여 작성하여 알고리즘을 써내려 갔다.
- 중위 표기법
중위 표기법이란 이름 그대로 피연산자들 사이에 연산자가 있는 표기법을 말한다. 우리가 기존에 알고있는 수식이 전부 중위 표기법이다. 다음 식을 보자.
17 + 5
위의 간단한 식을 보면 두개의 피연산자 (숫자) 사이에 연산자 (계산 기호) 가 있다. 연산자 옆의 두개의 피연산자로 계산을 하는 방식이 중위 표기법이다.
- 후위 표기법
후위 표기법은 중위 표기법과는 다르게 피연산자들 뒤에 연산자가 있는 표기법을 말한다. 우리가 아는 식과는 달라서 조금 어색할 수는 있지만 원리만 알면 간단하다. 다음 수식을 보자.
17 8 * 21 7 + -
이 식이 바로 중위 표기법으로 작성한 식이다. 계산하는 방법은 간단하다. 첫 순서의 연산자를 기준으로 잡고 이 기준의 왼쪽에서 가장 인접해 있는 두개의 피연산자를 기준 연산자로 계산해주면 된다.
다음식에서 처음으로 나오는 연산자는 * 이다. 그리고 가장 왼쪽의 두 피연산자인 17과 8을 기준 연산자인 *대로 곱해주면 된다. 그럼 다음과 같은 모습이 된다.
136 21 7 + -
17 * 8의 결과 값인 136이 (17 8 *) 자리를 대신 하였다. 계속 계산을 진행해보자.
처음으로 나오는 연산자는 이제 + 이다. 그리고 + 왼쪽에 나오는 피연산자 두개는 21과 7이므로 21 + 7의 결과 값을 (21 7 +) 자리에 넣어주면 된다. 다음과 같은 모습이 될 것이다.
136 28 -
이제 계산을 마무리해보자.
처음으로 나오는 연산자인 -에 대해 나머지 두개의 피연산자들을 가지고 계산을 진행해주면 된다. 결과 값은 최종적으로 다음과 같을 것이다.
108
- 중위위표기법에서 하위표기법으로 바꾸는 알고리즘
이제 중위표기법에서 하위표기법으로 바꾸는 알고리즘을 알아보자. 책은 두권 그리고 사이트는 세곳을 참고 하였다. 나올 수 있는 경우의 수를 있는데로 적었기 때문에 다른 곳에서 본 알고리즘보다 조금 길 수는 있다.
1. 숫자가 나오면 출력
2. 여는 괄호는 push
3. 연산자가 나왔을 때 Stack에 있는 연산자와 새로운 연산자의 우선순위를 비교
- Stack에 있는 연산자가 새로운 연산자보다 우선순위가 높거나 같다면 출력 후 새로운 연산자를 push
- 반대 상황이라면 아무 동작 없이 새로운 연산자를 push (Stack에 있는 연산자가 새로운 연산자보다 우선순위가 낮다면)
- 어떤 연산자라도 ‘(‘와 비교되면 즉 stack에 있던 연산자가 ‘(‘라면 새로운 연산자를 push
- 스택이 비어있다면 무조건 새로운 연산자 push
4. 닫는 괄호를 만나면 stack에서 여는 괄호를 만날 때까지 출력 단, 여는 괄호는 출력하지 않는다
5. 피연산자를 다 출력하면 stack이 비어있을 때까지 출력
그러면 예시를 통해 다음 식을 중위표기법으로 만들어보자. 아래의 간단한 수식을 중위표기법으로 만들어보겠다.
( 12 + 5 ) * 2
이렇게 수식이 있다면, 처음부터 수식을 읽어가면서 만나는 문자열을 위의 알고리즘대로 처리하면 된다.
위의 수식에서 가장 먼저 만나는 문자는 여는 괄호이다. 그리고 이는 2번 괄호대로 이 여는 괄호를 다음과 같이 스택에 push해주자. 그럼 스택과 결과는 다음과 같은 상태이다.
이제 다음에 만나는 데이터는 '12' 즉, 피연산자이다. 알고리즘대로 숫자는 다음과 같이 그대로 출력해주자.
다음에 만나는 데이터는 연산자이다. 알고리즘을 보면 연산자를 만났을 때 기존 stack에 있는 연산자와 비교해야하는데, 3 - 3을 보면 기존에 있는 연산자가 여는 괄호이면 무조건 새로운 연산자를 push해주라고 되어있다. '+'를 그대로 stack에 push해주자
다음에 만나는 데이터는 피연산자인 '5'이다. 그대로 push 해주자. 다음과 같은 상태가 될 것이다.
다음에 만나는 연산자는 닫는 괄호이다. 알고리즘대로 여는 괄호를 만날 때 까지 stack에 있는 데이터들을 다 출력해주자. 다음과 같이 stack은 비어있고, 수식에는 '+'가 추가된 상태일 것이다.
다음에 만난는 데이터는 연산자 '*'이다. 알고리즘대로 stack에 넣어주자.
마지막으로 숫자 2를 만나면서 우리가 탐색할 데이터는 끝이난다. 다음과 같은 상태가 될 것이다.
하지만 중요한 점이 있다. stack에 아직 데이터가 남아있는 것을 볼 수 있다. 알고리즘 5번대로 stack이 빌 때까지 출력해주자. 그러면 다음과 같이 후위표기식이 만들어지면서 알고리즘이 마무리 된다.
2. 구현
- Char_Stack.h
다음은 stack코드이다. 간단하게 필요한 기능만 구현하였다.
#pragma once
class Char_Stack {
private:
char* stack;
int p;
public:
Char_Stack(int max = 100)
{
stack = new char[max]; p = 0;
}
~Char_Stack()
{
delete stack;
}
inline void push(char v)
{
stack[p++] = v;
}
inline char pop()
{
return stack[--p];
}
inline int empty()
{
return !p;
}
inline char getData() {
return stack[p - 1];
}
};
- pre_to_pos.h
다음은 필요한 헤더와 함수를 정의한 pre_to_pos.h 헤더파일이다.
#pragma once
#include <iostream>
#include"Char_Stack.h"
using namespace std;
void pre_to_pos(char* preExp, char* posExp);
bool getOrder(char stackOp, char newOp);
pre_to_pos() 함수는 preExp변수에 중위표기법 변수를 받아와 posExp에 후위표기법으로 저장해주는 함수이다. getOrder() 함수는 두 연산자들의 우선순위를 가려주는 기능을 하는 함수이다.
- pre_to_pos.cpp
#include "pre_to_pos.h"
void pre_to_pos(char* preExp, char* posExp) {
Char_Stack stack(50);
int index = 0; // index for posExp
for (int i = 0; preExp[i] != NULL; i++) {
char token = preExp[i];
if (token == ' ')
continue;
if ('0' <= token && token <= '9') {
posExp[index++] = token;
if (preExp[i+1] == NULL) {
posExp[index++] = ' ';
}
else if ('0' > preExp[i+1] || preExp[i+1] > '9') {
posExp[index++] = ' ';
}
continue;
}
if (token == '(') {
stack.push(token);
}
if (token == '*') {
if (stack.empty()) {
stack.push(token);
}
else {
char buff = stack.getData();
if (getOrder(buff, token)) {
posExp[index++] = stack.pop();
posExp[index++] = ' ';
}
stack.push(token);
}
}
if (token == '/') {
if (stack.empty()) {
stack.push(token);
}
else {
char buff = stack.getData();
if (getOrder(buff, token)) {
posExp[index++] = stack.pop();
posExp[index++] = ' ';
}
stack.push(token);
}
}
if (token == '+') {
if (stack.empty()) {
stack.push(token);
}
else {
char buff = stack.getData();
if (getOrder(buff, token)) {
posExp[index++] = stack.pop();
posExp[index++] = ' ';
}
stack.push(token);
}
}
if (token == '-') {
if (stack.empty()) {
stack.push(token);
}
else {
char buff = stack.getData();
if (getOrder(buff, token)) {
posExp[index++] = stack.pop();
posExp[index++] = ' ';
}
stack.push(token);
}
}
if (token == ')') {
int buff = stack.pop();
while (buff != '(') {
posExp[index++] = buff;
posExp[index++] = ' ';
buff = stack.pop();
}
}
}
while (!stack.empty()) {
int buff = stack.pop();
if(buff != '(')
posExp[index++] = buff;
}
posExp[index] = NULL;
}
bool getOrder(char stackOp, char newOp) {
if (stackOp == '(')
return false;
if (newOp == '+' || newOp == '-')
return true;
else {
if (stackOp == '*' || stackOp == '/')
return true;
else
return false;
}
}
- 마지막으로 함수를 확인하는 main.cpp이다.
#include "pre_to_pos.h"
#define SIZE 50
int main(void) {
char preExp[SIZE];
char posExp[SIZE];
cout << "[prefix]" << endl;
cin.getline(preExp, 50);
pre_to_pos(preExp, posExp);
cout <<endl << "[postfix]" << endl << posExp << endl;
return 0;
}
- 실행결과
다음은 실행결과이다.
'programming > 알고리즘' 카테고리의 다른 글
| [programmers] 250136번 - PCCP 기출문제 2번(BFS, PCCP 기출문제) (0) | 2023.11.26 |
|---|---|
| [알고리즘] C++을 활용한 후위 표기법의 계산 (2) | 2021.04.17 |
| [알고리즘] C++ vector을 활용한 정렬 구현(버블, 삽입, 퀵) (0) | 2020.07.30 |
