Postfix Calculator(후위 표기식 계산기) 구현

postfix란 뭘까

수식의 종류에는 prefix, infix, postfix 세 가지가 존재한다

이것은 연산자가 피연산자들 사이에서 어느 위치에 존재하느냐에 따라 나뉜다

출처: https://prepinsta.com/wp-content/uploads/2020/06/Postfix-Prefix-and-Infix-1024x1024.png

우리는 일상생활에서 99.999999% Infix 방식을 이용해서 표기한다.

하지만 Infix방식에는 문제점이 존재한다

5+4*3 이라는 수식이 존재할 때, '*' 연산자가 '+' 연산자보다 우선순위가 높기 때문에 해당 수식을 먼저 계산해줘야 한다

하지만 이것은 계산을 하는 사람이 모든 수식을 차례로 읽은 뒤, 연산 순서를 임의로 정해야 한다.

그렇기 때문에 순차적으로 입력을 받고 이를 해결하는 컴퓨터의 계산 방식과는 약간 다르다.

 

컴퓨터는 postfix 연산 방식을 선호한다.

위의 수식을 postfix로 전환하면, 5 4 3 * + 이다.

 

postfix의 연산 방식은

1️⃣ 수식을 한 글자씩 읽어나간다

2️⃣ 연산자를 만나면, 연산자 바로 앞의 피연산자 두 개를 가지고 연산을 진행한다.

따라서 "5 4 3 * +"는, 피연산자를 계속 pass하다가 '*'를 만나서 연산을 진행한 뒤 "5 12 +"가 되고

'+'을 만나서 결과적으로 17이 된다.

그렇기 때문에 계산하는 측에서 연산자의 우선 순위를 따질 필요 없이 순차적으로 계산하기만 하면 된당

 

이러한 postfix calculator는 스택을 이용해서 구현할 수 있다

 

수식을 왼쪽에서 오른쪽으로 순차적으로 읽어들이면서

1️⃣ 현재 글자가 피연산자면 해당 피연산자를 stack에 push

2️⃣ 현재 위치가 연산자이면

- stack에 쌓여 있는 피연산자 두 개를 pop

- 현재 연산자를 이용해 두 피연산자를 계산

- 계산한 결과값을 stack에 push

3️⃣ 수식을 쭉 스캔하면서 1과 2를 반복한 뒤, 스캔이 끝나고 최종적으로 stack에 남아있는 값이 수식의 답

 

출처: 충북대학교 소프트웨어학과 자료구조 강의자료

위의 그림은 stack을 이용한 postfix calculator의 동작 예시이다.

 

후위 표기식의 계산 코드는 아래와 같다 (백준1935번 후위표기식- www.acmicpc.net/problem/1935)

#include <cstdio>
#include <stack>
using namespace std;
stack<double> s;
char c, str[101];
int n, num[27];
double a, b;
int main() {
	scanf("%d ", &n);
	scanf("%s", str);
	for (int i = 0; i < n; i++)
		scanf("%d", &num[i]);

	for (int i = 0; str[i] != NULL; i++) {
		c = str[i];
		if (c == '\n')break;
		if ((c >= 'A') && (c <= 'Z')) {
			s.push(num[c - 'A']);
		}
		else {
			a = s.top(); s.pop();
			b = s.top(); s.pop();
			switch (c) {
			case '+':
				s.push(a + b);
				break;
			case '*':
				s.push(a * b);
				break;
			case '-':
				s.push(b - a);
				break;
			case '/':
				s.push((double)b / a);
				break;
			}
		}
	}

	printf("%.2lf", s.top());

	return 0;
}