[스택 & 큐] 백준 1935번 (C언어) - 후위 표기식2

문제는 간단히 말해 후위 표기식을 연산하는 문제이다.

후위표기식은 스택으로 구현하는 경우가 있다는 것을 알기 때문에 스택으로 구현하는 것을 생각해 보았다.

후위표기식은 연결 리스트로 만들어줄 이유가 없기 때문에 간단하게 배열로 짜도 상관이 없을 것 같았다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

double stack[100];
int top = -1;

void push(double x) {
	stack[++top] = x;
}

double pop() {
	return stack[top--];
}

int main(void) {
	int n;
	char str[101];

	scanf("%d", &n);
	int* value = (int*)malloc(sizeof(int) * n);

	scanf("%s", str);

	for (int i = 0; i < n; i++) {
		scanf("%d", &value[i]);
	}

	for (int i = 0; i < strlen(str); i++) {
		if ('A' <= str[i] && str[i] <= 'Z') {
			push(value[str[i] - 'A']);
		}
		else if (str[i] == '+') {
			double b = pop();
			double a = pop();
			push(a + b);
		}
		else if (str[i] == '-') {
			double b = pop();
			double a = pop();
			push(a - b);
		}
		else if (str[i] == '*') {
			double b = pop();
			double a = pop();
			push(a * b);
		}
		else if (str[i] == '/') {
			double b = pop();
			double a = pop();
			push(a / b);
		}
	}
	printf("%.2lf", pop());
}

먼저 스택에 해당하는 배열을 설정하고, 현재 가리키는 커서에 해당하는 top 변수를 생성한다.

애초에 배열의 크기를 지정했기 때문에 push와 pop은 매우 간단하게 구현했다. push는 삽입연산이기 때문에 현재 top보다 1 더 큰 인덱스에 인수로 준 값을 배열에 넣어주고, pop은 삭제 연산이기 때문에 현재 top이 가리키는 인덱스의 값을 return 하고 -1을 해준다.

 

main함수에서는 일단 문제에서의 입력과 순서대로 먼저 변수의 개수, 후위 표기식과 각 변수들의 값을 순서대로 입력받아준다. 

그다음 후위 표기식에 해당하는 문자열의 길이만큼 for문을 돌려준다. 후위 표기식에서는 변수를 스택에 넣어주고 연산자가 나올 때마다 가장 앞의 두 값을 pop 하고 연산한 값을 다시 스택에 넣기 때문에 배열에는 연산자가 아닌 변수가 들어간다. 

for문 안에서는 연산자가 나올 때마다 가장 최근에 push 된 두 개의 값을 pop 하여 연산을 하고 다시 연산된 값을 push 해준다.