[알고리즘] C++을 활용한 후위 표기법의 계산

1. 이론

 

 이 알고리즘은 중위 표기법에서 후위 표기법으로 전환한 후에 후위표기법을 실질적으로 계산하는 알고리즘이다. 이 부분은 전에 포스팅한 중위 표기법의 후위 표기법 변환 알고리즘보다는 훨씬 간단하다. 예외와 구현이 나름 쉬웠다. 이 부분은 학교 수업으로 공부하였다.

 

- 후위표기식의 계산 알고리즘

 

 후위표기식의 계산 알고리즘은 다음과 같다.

---

1. 숫자가 나오면 무조건 스택에 Push
2. 연산자가 나오면 스택에서 두개의 피연산자를 꺼내 계산한다.
   1. 연산자가 뺄셈 혹은 나눗셈인 경우 순서를 생각해야 한다.
   2. 이런 경우를 대비해 스택에서 나중에 꺼내진 연산자로부터 먼저 꺼내진 연산자에 대한 연산을 실행한다
3. 계산된 연산자는 다시 스택에 넣어준다.
4. 후위 표기식이 다 끝났다면 스택에 남아있는 피연산자가 식의 답이다.

---

 이전 포스팅에 만들어진 중위표기식을 보도록 하자. 혹시 전 포스팅을 보지 않은 분들은 한번쯤은 보고오길 바란다.

---

이전 포스팅: apape1225.tistory.com/67

[알고리즘] C++을 활용한 중위 표기법의 후위 표기법 변환

---

 다음은 전 포스팅에서 만들어진 후위표기식이다.

---

---

 이제 알고리즘을 진행해보자.

 

 일단 만나는 두개의 피연산자를 스택에 차례대로 넣어준다. 다음과 같은 그림이 될 것이다.

---

---

 이제 연산자를 만났으니 2번 알고리즘을 실행해보자. 나중에 나온 피연산자 즉 12를 처음 나온 피연산자와 같이 연산을 진행하면 되는것이다.

 

 결과적으로 12 + 5를 계산하고 다시 스택에 넣어준다. 다음과 같은 결과가 될 것이다.

 

---

---

 이제 피연산자를 만났으니 다시 2를 넣어주자. 다음과 같은 상황이 될 것이다.

---

---

 자 드디어 마지막 단계이다. 마지막으로 만난 연산자를 위해 2와 17을 순서로 꺼내 결과값을 다시 넣어주자. 다음과 같은 상황이 될 것이다.

---

---

 이렇게 알고리즘을 실행해보니 결과 값이 스택에 저장되어 있는 것을 볼 수 있다. 다음은 소스코드이다.

 

2. 구현

 

 다음은 Stack코드이다. 이번 스택은 정수를 저장할 수 있는 스택으로 구현하였다.

 

-Int_Stack.h

 

#pragma once

class Int_Stack{
private:
	int* stack;
	int p;
public:
	Int_Stack(int max = 100)
	{
		stack = new int[max]; p = 0;
	}
	~Int_Stack()
	{
		delete stack;
	}
	inline void push(int v)
	{
		stack[p++] = v;
	}
	inline int pop()
	{
		return stack[--p];
	}
	inline int empty()
	{
		return !p;
	}

};

 

- cal_postifx.h

 

 다음은 필요한 메소드를 정의한 헤더파일이다. 메소드가 하나밖에 없기에 매우 간단하다.

 

#pragma once

#include "Int_Stack.h"
#include <iostream>

using namespace std;

int calPostfix(char* posExp);

 

- cal_postifx.cpp

 

 다음은 메소드를 구현한 소스코드이다.

 

 중요한점은 15줄부터 22줄이다. 피연산자가 10의 자리를 넘길경우를 대비해 후위표기식의 피연산자를 그대로 스택에 저장하기 위한 코드이다. 코드를 잘 보면 이해갈 것이다.

 

#pragma once
#include "cal_postfix.h"

int calPostfix(char* posExp) {
	Int_Stack stack(50);

	int x;
	for (int i = 0; posExp[i] != NULL; i++) {
		char token = posExp[i];
		x = 0;

		if (token == ' ')
			continue;

		if ('0' <= token && token <= '9') {
			x = token - '0';
			token = posExp[++i];
			while ('0' <= token && token <= '9') {
				x = x * 10 + (token - '0');
				token = posExp[++i];
			}
			i--;
		}
		else {

			int num1 = stack.pop();
			int num2 = stack.pop();

			switch (token) {	

			case '+': {
				x = num2 + num1;
				break;
			}
			case '-': {
				x = num2 - num1;
				break;
			}
			case '*': {
				x = num2 * num1;
				break;
			}
			case '/':
				x = num2 / num1;
			}
		}
		stack.push(x);
	}

	return stack.pop();
}

 

- main.cpp

 

 마지막으로 결과를 확인하는 main.cpp 파일이다. 저번에 포스팅한 후위표기식 함수를 그대로 가지고 와서 실행하니 참고하길 바란다.

 

#include "pre_to_pos.h"
#include "cal_postfix.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);
	int ans = calPostfix(posExp);

	cout << endl << ans << endl;
	

	cout <<endl << "[postfix]" << endl << posExp << endl;
	return 0;
}